Mixed Integer Programming Approaches to Novel Vehicle Routing Problems

This thesis explores two main topics. The first is how to incorporate data on meteorological forecasts, traffic patterns, and road network topology to utilize deicing resources more efficiently. Many municipalities throughout the United States find themselves unable to treat their road networks fully during winter snow events. Further, as the global climate continues to change, it is expected that both the number and severity of extreme winter weather events will increase for large portions of the US. We propose to use network flows, resource allocation, and vehicle routing mixed integer programming approaches to be able to incorporate all of these data in a winter road maintenance framework. We also show that solution approaches which have proved useful in network flows and vehicle routing problems can be adapted to construct high-quality solutions to this new problem quickly. These approaches are validated on both random and real-world instances using data from Knoxville, TN. In addition to showing that these approaches can be used to allocate resources effectively given a certain deicing budget, we also show that these same approaches can be used to help determine a resource budget given some allocation utility score. As before, we validate these approaches using random and real-world instances in Knoxville, TN. The second topic considered is formulating mixed integer programming models which can be used to route automated electric shuttles. We show that these models can also be used to determine fleet composition and optimal vehicle characteristics to accommodate various demand scenarios. We adapt popular vehicle routing solution techniques to these models, showing that these strategies continue to be relevant and robust. Lastly, we validate these techniques by looking at a case study in Greenville, SC, which recently received a grant from the Federal Highway Administration to deploy a fleet of automated electric shuttles in three neighborhoods.