On the usage of Lagrangean Relaxation for the convoy movement problem

Abstract

The problem of routing military convoys between specific origin and destination pairs is known as convoy movement problem (CMP). In this study, we consider an existing mathematical model of CMP and propose a lower bounding procedure based on Lagrangean Relaxation. The robustness of the proposed procedure is evaluated on a variety of test problem instances. Encouraging results are obtained.

Keywords:

• military convoys
• conflicts
• scheduling
• Lagrangean Relaxation
• heuristics

Acknowledgements

The authors acknowledge two anonymous referees and the editor for their valuable suggestions to improve the earlier version of this paper.