A Lagrangian-relaxation-based bounding approach for the convoy movement problem in military logistics

Convoy movement problem (CMP) is an important optimisation problem, especially occurring in military logistics, which focuses on routing convoys concurrently in a network. The CMP is subject to constraints for preventing certain interactions between convoys such that the objectives related to travel times of them are minimised. We propose a Lagrangian relaxation (LR) approach to efficiently obtain a lower bound on the optimal solution. Our LR approach does not have integrality property, and hence the lower bound obtained is always tigher than the lower bound obtained using the LP relaxation. As CMP is an NP-complete problem, lower bounds are useful to evaluate the solutions obtained by a heuristic. From our computational experimentation, it is found that the proposed LR approach is superior to the existing LR approach.