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

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.