Solving a Time-Space Network Formulation for the Convoy Movement Problem
- 1 April 2005
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 53 (2), 219-230
- https://doi.org/10.1287/opre.1040.0183
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
This publication has 27 references indexed in Scilit:
- Solving the undirected multicommodity flow problem using a shortest path‐based pricing algorithmNetworks, 2001
- Balancing user preferences for aircraft schedule recovery during irregular operationsIIE Transactions, 2000
- Routing and scheduling temporal and heterogeneous freight car traffic on rail networksTransportation Research. Part E, Logistics and Transportation Review, 1998
- Testing and evaluation of a multi‐commodity multi‐modal network flow model for disaster relief managementJournal of Advanced Transportation, 1997
- An implementation of linear and nonlinear multicommodity network flowsEuropean Journal of Operational Research, 1996
- Efficiency considerations in the implementation of parallel branch-and-boundAnnals of Operations Research, 1993
- Branch-and-bound as a higher-order functionAnnals of Operations Research, 1991
- Formulation and solution of a combined train routing and makeup, and empty car distribution modelTransportation Research Part B: Methodological, 1989
- On the complexity of admissible search algorithmsArtificial Intelligence, 1977
- An application of heuristic search methods to edge and contour detectionCommunications of the ACM, 1976