Robust convoy movement problem under travel time uncertainty

Byung Jun Ju and Byung Do Chung

Transportation Research Part B: Methodological, 2024, vol. 190, issue C

Abstract: A convoy represents a collection of vehicles traveling with a spacing of 50–100 m between them for tactical purposes. The convoy movement problem is a variant of the vehicle routing problem, an NP-hard problem aimed at determining the paths and schedules of convoys. Given the uncertainties in travel times during wartime, attributable to various factors such as road conditions and enemy threats, it is essential to consider uncertain travel times when determining convoy paths and schedules. Therefore, this study introduces a robust convoy movement problem under travel time uncertainty. A polyhedral set for uncertain travel times is used to derive a robust counterpart for the problem. To solve the proposed problem, we establish an exact algorithm that determines optimal solutions by iteratively generating and integrating multiple paths of convoys. This algorithm involves four steps: generation of k-th robust shortest paths, construction of path combinations, adjustment of departure times, and conduction of optimality check. These steps are iterated sequentially until the optimal solution is obtained. In computational experiments, the exact algorithm demonstrates superior performance and reduced computation time compared with the commercial solver CPLEX on both real instances and randomly generated instances. In addition, we conduct a sensitivity analysis for several parameters related to the problem, providing valuable managerial insights for decision-makers.

Keywords: Convoy movement problem; Robust optimization; Uncertain travel time; Military logistics (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261524002157
Full text for ScienceDirect subscribers only

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:eee:transb:v:190:y:2024:i:c:s0191261524002157

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2024.103091

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().