Solving a Time-Space Network Formulation for the Convoy Movement Problem

P. Chardaire (), G. P. McKeown (), S. A. Verity-Harrison () and S. B. Richardson ()
Additional contact information
P. Chardaire: School of Computing Sciences, University of East Anglia, Norwich NR4 7TJ, United Kingdom
G. P. McKeown: School of Computing Sciences, University of East Anglia, Norwich NR4 7TJ, United Kingdom
S. A. Verity-Harrison: Defence Science and Technology Laboratory, Malvern Technology Centre, St. Andrews Road, Malvern WR14 3PS, United Kingdom
S. B. Richardson: QinetiQ, Malvern Technology Centre, St. Andrews Road, Malvern WR14 3PS, United Kingdom

Operations Research, 2005, vol. 53, issue 2, 219-230

Abstract: We give a formal specification for a strategic network routing problem known as the convoy movement problem (CMP) and establish that the corresponding feasibility problem is NP-complete. We then introduce an integer programming (IP) model based on the concept of a time-space network and apply a Lagrangian relaxation to this model. We discuss how the dual function may be evaluated using a modified version of Dijkstra’s algorithm suitable to very large, implicitly defined graphs and show how heuristic solutions to the primal problem may be obtained. We present results for a number of instances of the CMP, most of which are based on real-world problems. The number of convoys in these instances varies between 15–25, and their movement time requires up to several thousand time units in networks ranging in size from a few dozen to several thousand vertices and edges. The most difficult instance tested involves 17 long convoys each taking four times the average link travel time to pass through a point in the network. This instance is solved within 3.3% of optimality in less than 3.5 hours of computing time on a Dell Precision 420 dual processor computer. Every other test instance is solved within 2% of the optimal value in less than 20 minutes of computing time.

Keywords: military: logistics; transportation: vehicle routing; programming: integer; relaxation/subgradient (search for similar items in EconPapers)
Date: 2005
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1040.0183 (application/pdf)

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:inm:oropre:v:53:y:2005:i:2:p:219-230

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().