Route assignment and scheduling with trajectory coordination

We study the problem of finding optimal routes and schedules for multiple vehicles traveling in a network. Vehicles may have different origins and destinations, and must coordinate their trajectories to keep a minimum distance from each other at any time. We determine a route and a schedule for each vehicle, which possibly requires vehicles to wait at some nodes. Vehicles are heterogeneous in terms of their speed on each arc, which we assume is known and constant once in motion. Applications of this problem include air and maritime routing, where vehicles maintain a steady cruising speed as well as a safety distance to avoid collision. Additional related problems arise in the transportation of hazardous materials and in military operations, where vehicles cannot be too close to each other given the risk posed to the population or the mission in case of a malicious attack. We discuss the hardness of this problem and present an exact formulation for its solution. We devise an exact solution algorithm based on a network decomposition that exploits the sparsity of the optimal solution. We illustrate the performance of our methods on real and randomly generated networks.