file.pdf (274.7 kB)

Optimal Vehicle Routing and Scheduling with Precedence Constraints and Location Choice

Download (274.7 kB)
journal contribution
posted on 01.05.2010 by G. Ayorkor Korsah, Anthony Stentz, M. Bernardine Dias, Imran Fanaswala

To realize the vision of intelligent transportation systems with fully automated vehicles, there is a need for high-level planning for single vehicles as well as fleets of vehicles. This paper addresses the problem of optimally assigning and scheduling a set of spatially distributed tasks to a fleet of vehicles working together to achieve a high-level goal, in domains where tasks may be related by precedence or synchronization constraints and might have a choice of locations at which they can be performed. Such problems may arise, for example, in disaster preparedness planning, transportation of people, and delivery of supplies. We present a novel mathematical model of the problem and describe how it can be solved optimally in a branch-and-price framework.