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

Bouzid, Mouaouia Cherif and Ait Haddadene, Hacene and 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:https://doi.org/10.1016/j.cor.2016.02.009) (Access to this publication is currently restricted. You may be able to access a copy if URLs are provided)

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
[img]
Preview
PDF - Author's Accepted Manuscript
Restricted to Repository staff only
Contact us about this Publication Download (638kB)
[img]
Official URL
http://dx.doi.org/10.1016/j.cor.2016.02.009

Abstract

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
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: 25 Aug 2018 23:00 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/55070 (The current URI for this page, for reference purposes)
  • Depositors only (login required):

Downloads

Downloads per month over past year