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

Authors: S.A. Ezhil; Chandrasekharan Rajendran

Addresses: Department of Management Studies, IIT Madras, Chennai, 600036, India ' Department of Management Studies, IIT Madras, Chennai, 600036, India

Abstract: 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.

Keywords: military logistics; convoy movement problem; lower bound; Lagrangian relaxation.

DOI: 10.1504/IJSOM.2020.109031

International Journal of Services and Operations Management, 2020 Vol.36 No.4, pp.480 - 504

Received: 13 Feb 2018
Accepted: 24 May 2018
Published online: 17 Aug 2020 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article