Kocaturk, FatihTütüncü, Gözde YazgıSalhi, Said2023-06-162023-06-1620210254-53301572-9338https://doi.org/10.1007/s10479-021-04137-6https://hdl.handle.net/20.500.14365/887In 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.eninfo:eu-repo/semantics/openAccessRoutingHeterogeneous vehicle fleetBackhaulingMultiple depotsGRAMPS and VNS hybridisationVehicle-Routing ProblemFleet SizeSearchPickupSingleAlgorithmArticle10.1007/s10479-021-04137-62-s2.0-85107609502