Abstract
Moving men and materials in large numbers and quantities is a long-standing military problem faced by all arms. An important part of this is the routing of convoys so that they reach their correct destinations in the shortest time. The optimization problem at the heart of this problem is referred to as the convoy movement problem. Previous work on the convoy movement problem has made the assumption that the problem is difficult in practice because of the NP-hardness of the problem in combination with the limited success of early approaches based on genetic algorithms. As a result subsequent work has focused on mathematical programming-based methods, principally Lagrangian relaxation. In this paper, we demonstrate that a straightforward reformulation of the problem renders the real-world like instances, used to benchmark previous approaches, amenable to solution by simple heuristics. The main lessons learnt from this work is that analysis of the problem in conjunction with simple algorithms can, in practice, yield surprisingly effective solutions.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
West CL (1996). Combinatorial Algorithms for Military Applications (CALMA). DERA Report DRA/CIS(SE1)/608/08/07/Final_1, DERA.
Chardaire P, McKeown GP, Harrison SA and Richardson SB. (1999). Solving a time-space formulation for the convoy movement problem. Opns Res, to appear.
Lee YN, McKeown GP and Rayward-Smith VJ (1996). The convoy movement problem with initial delays. In: Rayward-Smith VJ, Reeves C, Smith GD (eds). Modern Heuristic Search Methods. John Wiley: New York, pp 215–236.
Iakovou E, Douligeris C, Li H and Yudhbir L (1999). A maritime global route planning model for hazardous materials. Transp Sci 33(1): 34–48.
Chih K, Bodden MP, Hornung MA and Kornhauser AL (1990). Routing and inventory logistics system: a heuristic model for optimally managing intermodal double-stack trains. J Transp Res Forum 31: 56–62.
Florian M, Bushell G and Ferland J (1976). The engine scheduling problem in a rail network. INFOR 14: 121–138.
Kwon OK, Martland CD and Sussman JM (1998). Routing and scheduling temporal and heterogeneous freightcar traffic on rail networks. Transp Res E Logist Transp Rev 34(2): 101–115.
Garey M and Johnson DS (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman: New York.
Lee YN (1995). Sequential and parallel solutions of the convoy movement problem using branch–and–bound and heuristic hybrid techniques. PhD thesis, School of Information Systems, University of East Anglia, Norwich, UK.
Harrison SA (1998). A greedy heuristic for the convoy movement problem with initial delays. Symposium on Combinatorial Optimization: Recent Advances in Theory and Practice, Universite Libres de Bruxelles, Belgium, April 1998.
Cohen PR (1995). Empirical Methods for Artificial Intelligence. MIT Press: Cambridge, MA.
Ahuja RK, Magnanti TL and Orlin JB (1993). Network Flows: Theory, Algorithms, and Applications. Prentice-Hall: Englewood Cliffs, NJ.
Acknowledgements
The UK MoD supported the work of both authors. This work was undertaken when Mr Harrison was an employee of the Defence Evaluation & Research Agency (DERA), an Agency of the UK MoD.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Tuson, A., Harrison, S. Problem difficulty of real instances of convoy planning. J Oper Res Soc 56, 763–775 (2005). https://doi.org/10.1057/palgrave.jors.2601863
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/palgrave.jors.2601863