Route assignment and scheduling with trajectory coordination

Abstract

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.

Key Words:

• Trajectory planning
• route assignment
• vehicle routing and scheduling
• network optimization

Acknowledgments

We thank the three anonymous reviewers whose suggestions helped improve this manuscript.

Additional information

Funding

This material is based upon work supported by the National Science Foundation under Grant No. 1740042.

Notes on contributors

Navid Matin-Moghaddam

Navid Matin-Moghaddam is a PhD candidate in industrial engineering at Arizona State University. He holds a MSc degree in industrial engineering (2015) from Clemson University and a BSc In industrial engineering (2013) from Sharif University of Technology. His research interests include the development and application of novel operations research and data science methodologies. His interdisciplinary research includes collaborations with researchers from various domains such as computer science, civil engineering, and education.

Jorge A. Sefair

Dr. Jorge A. Sefair is an assistant professor in the School of Computing, Informatics, and Decision Systems Engineering (CIDSE) at Arizona State University, where he also is a Senior Sustainability Scientist at the Julie Ann Wrigley Global institute of Sustainability, and affiliate faculty at the Simon A. Levin Mathematical, Computational, and Modeling Sciences Center (MCMSC), the Center for Biodiversity Outcomes, and the Center for Spatial Reasoning & Policy Analytics (CSRPA). Dr. Sefair holds a PhD degree in industrial and systems engineering from the University of Florida (2015), and an MSc degree in industrial engineering (2008), BSc in industrial engineering (2006), and BA in economics (2005) from Universidad de los Andes (Colombia). His research interests include network optimization, multistage optimization, and integer programming. In particular, he is motivated by applications of operations research in environmental planning, public policy, and urban systems. His research has been interdisciplinary, having published academic works with colleagues from a variety of fields, including civil engineering, public health, ecology, biology, and economics.