New approaches for solving the convoy movement problem

Hamid Mokhtar*, Mohan Krishnamoorthy, Niraj Dayama, P. N.Ram Kumar

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review


The convoy movement problem (CMP) involves the routing and scheduling of a large number of vehicles and personnel across a network. A convoy is a group of (typically, army) vehicles and personnel that travel together as a group. Given the nature and context of these movements, it is necessary to avoid convoys crossing each other at a node, overtaking, or crossing each other on a road as they travel in the network from their individual origins to their destinations. The lengths and travel speeds are also major factors that determine the optimal travel paths and schedules for these convoys. In this paper, we review different variants of the CMP in the literature. We then propose a generalised problem statement for the CMP that accommodates all common variants. This generalised problem definition addresses several important side constraints that typically occur in real-world problems. We adapt and enhance existing formulations of the CMP in such a way that the generalised version can also be modelled. Further, we propose new approaches for solving large instances of the generalised CMP. Our computational experiments show that the techniques introduced in this paper substantially outperform existing approaches in the literature. We also generate a new dataset for the generalised CMP that provides a framework for the examination of various approaches for the CMP with a wider set of side constraints.

Original languageEnglish
Article number101802
Number of pages18
Early online date21 Nov 2019
Publication statusPublished - 20 Jan 2020
MoE publication typeA1 Journal article-refereed


  • Convoy movement problem
  • Shortest path problem
  • Time-space network


Dive into the research topics of 'New approaches for solving the convoy movement problem'. Together they form a unique fingerprint.

Cite this