Skip to main content
Kent Academic Repository

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) (KAR id:55070)

PDF Author's Accepted Manuscript
Language: English

Download this file
[thumbnail of Bouzid%28Revision-final sent-dec2015%29.pdf]
Request a format suitable for use with assistive technology e.g. a screenreader
PDF Author's Accepted Manuscript
Language: English

Restricted to Repository staff only
Contact us about this Publication
[thumbnail of Bouzid(Revision-final sent-dec2015).pdf]
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: Divisions > Kent Business School - Division > Department of Analytics, Operations and Systems
Depositing User: Said Salhi
Date Deposited: 20 Apr 2016 10:06 UTC
Last Modified: 19 Sep 2023 15:03 UTC
Resource URI: (The current URI for this page, for reference purposes)

University of Kent Author Information

  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.