This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Chardaire, P. Articles by Richardson, S. B. Search for Related Content

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

School of Computing Sciences, University of East Anglia, Norwich NR4 7TJ, United Kingdom
School of Computing Sciences, University of East Anglia, Norwich NR4 7TJ, United Kingdom
Defence Science and Technology Laboratory, Malvern Technology Centre, St. Andrews Road, Malvern WR14 3PS, United Kingdom
QinetiQ, Malvern Technology Centre, St. Andrews Road, Malvern WR14 3PS, United Kingdom
pc{at}cmp.uea.ac.uk
gpm{at}cmp.uea.ac.uk
avharrison{at}dstl.gov.uk
sbrichardson{at}btinternet.com

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.

Subject classifications: military: logistics; transportation: vehicle routing; programming: integer; relaxation/subgradient.
History: Received November 1999; revision received July 2003; accepted October 2003.

This article has been cited by other articles:

				A. Cohn, S. Root, A. Wang, and D. Mohr Integration of the Load-Matching and Routing Problem with Equipment Balancing for Small Package Carriers Transportation Science, May 1, 2007; 41(2): 238 - 252. [Abstract] [PDF]