Route assignment and scheduling with trajectory coordination

Navid Matin-Moghaddam and Jorge A. Sefair

IISE Transactions, 2020, vol. 53, issue 2, 164-181

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.

Date: 2020
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/24725854.2020.1774096 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:uiiexx:v:53:y:2020:i:2:p:164-181

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/uiie20

DOI: 10.1080/24725854.2020.1774096

Access Statistics for this article

IISE Transactions is currently edited by Jianjun Shi

More articles in IISE Transactions from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().