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

Fatih Kocatürk (), G. Yazgı Tütüncü and Said Salhi
Additional contact information
Fatih Kocatürk: İzmir University of Economics
G. Yazgı Tütüncü: İzmir University of Economics
Said Salhi: University of Kent

Annals of Operations Research, 2021, vol. 307, issue 1, No 14, 277-302

Abstract: 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\%$$ 13 % gap from the lower bounds compared to nearly $$40\%$$ 40 % and $$20\%$$ 20 % average gap values for our CPLEX implementation and the VNS without hybridisation, respectively.

Keywords: Routing; Heterogeneous vehicle fleet; Backhauling; Multiple depots; GRAMPS and VNS hybridisation (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-021-04137-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:307:y:2021:i:1:d:10.1007_s10479-021-04137-6

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-021-04137-6

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().