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 *