Skip to main content
Kent Academic Repository

The multi-depot heterogeneous VRP with backhauls: formulation and a hybrid VNS with GRAMPS meta-heuristic approach

Kocatürk, Fatih, Tütüncü, G. Yazgı, Salhi, Said (2021) The multi-depot heterogeneous VRP with backhauls: formulation and a hybrid VNS with GRAMPS meta-heuristic approach. Annals of Operations Research, 307 . pp. 277-302. ISSN 0254-5330. E-ISSN 1572-9338. (doi:10.1007/s10479-021-04137-6) (KAR id:89063)

Abstract

In this paper, we investigate the Multi-Depot Heterogeneous VRP with Backhauls. Though the problem is a generalisation of three existing routing problems, this is the first time this combined routing problem is investigated. A mathematical formulation is first presented followed by some tightening. A powerful and novel hybridisation of Variable Neighbourhood Search (VNS) with the Greedy Randomized Adaptive Memory Programming Search is proposed. As there are no problem instances available for bench-marking and evaluation purposes, we generated data sets by combining those from existing vehicle routing problems. The proposed meta-heuristic obtains a number of optimal solutions for small instances

and yields about 13% gap from the lower bounds compared to nearly 40% and 20% average gap values for our CPLEX implementation and the VNS without

hybridisation, respectively.

Item Type: Article
DOI/Identification number: 10.1007/s10479-021-04137-6
Uncontrolled keywords: Routing, Heterogeneous vehicle fleet, Backhauling, Multiple depots, GRAMPS and VNS hybridisation
Subjects: H Social Sciences > H Social Sciences (General)
Divisions: Divisions > Kent Business School - Division > Department of Analytics, Operations and Systems
Depositing User: Said Salhi
Date Deposited: 07 Jul 2021 10:23 UTC
Last Modified: 19 Sep 2023 15:03 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/89063 (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.