Solving a time-space network formulation for the convoy movement problem

Chardaire, P., McKeown, G. P., Verity-Harrison, S. A. and Richardson, S. B. (2005) Solving a time-space network formulation for the convoy movement problem. Operations Research, 53 (2). pp. 219-230. ISSN 0030-364X

Full text not available from this repository. (Request a copy)

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.

Item Type:	Article
Faculty \ School:	Faculty of Science > School of Computing Sciences
Depositing User:	Vishal Gautam
Date Deposited:	09 Jun 2011 15:19
Last Modified:	24 Sep 2024 09:56
URI:	https://ueaeprints.uea.ac.uk/id/eprint/23582
DOI:	10.1287/opre.1040.0183

Actions (login required)

View Item