Skip to main content

An Integration of Lagrangian Split and VNS: The case of the Capacitated Vehicle Routing Problem

Bouzid, Mouaouia Cherif, Ait Haddadene, Hacene, Salhi, Said (2017) An Integration of Lagrangian Split and VNS: The case of the Capacitated Vehicle Routing Problem. Computers and Operations Research, 78 . pp. 513-525. ISSN 0305-0548. (doi:10.1016/j.cor.2016.02.009)

PDF - Author's Accepted Manuscript

Creative Commons Licence
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Download (484kB) Preview Download (484kB)
PDF - Author's Accepted Manuscript
Restricted to Repository staff only
Contact us about this Publication
Official URL


In this paper, we propose an efficient and novel Lagrangian relaxation method which incorporates a new integer linear programming (ILP) formulation to optimally partition a giant tour in the context of a capacitated vehicle routing problem (CVRP). This approach, which we call Lagrangian split (Ls), is more versatile than the ILP which, in most cases, can be intractable using a conventional solver. An effective repair mechanism followed by a local search are also embedded into the process. The mathematical validity of the repair mechanism and its time complexity are also provided. An integration of Ls into a powerful variable neighbourhood search (VNS) is also presented. Computational experiments are conducted to demonstrate that Ls provides encouraging results when applied on benchmark instances and that the integration of Ls into a metaheuristic scheme produces good results when compared to those found by state-of-the-art methods.

Item Type: Article
DOI/Identification number: 10.1016/j.cor.2016.02.009
Uncontrolled keywords: Routing problems, route-first cluster-second, Lagrangian relaxation, subgradient method, variable neighbourhood search, hybridisation
Subjects: Q Science > Operations Research - Theory
Divisions: Faculties > Social Sciences > Kent Business School > Management Science
Faculties > Social Sciences > Kent Business School > Centre for Logistics and Heuristic Organisation (CLHO)
Depositing User: Said Salhi
Date Deposited: 20 Apr 2016 10:06 UTC
Last Modified: 08 Feb 2020 04:08 UTC
Resource URI: (The current URI for this page, for reference purposes)
Salhi, Said:
  • Depositors only (login required):


Downloads per month over past year