A Biased Randomised Large Neighbourhood Search for the two dimensional Vehicle Routing Problem with Backhauls
The two dimensional loading vehicle routing problem with clustered backhauls (2L VRPB) is a realistic extension of the classical vehicle routing problem where both delivery and pickup demands are composed of non stackable items. Despite the fact that the 2L VRPB can be frequently found in real life transportation activities, it has not been analysed so far in the literature. This paper presents a hybrid algorithm that integrates biased randomised versions of vehicle routing and packing heuristics within a Large Neighbourhood Search metaheuristic framework. The use of biased randomisation techniques allows to better guide the local search process. The proposed approach for solving the 2L VRPB is tested on an extensive set of instances, which have been adapted from existing benchmarks for the two dimensional loading vehicle routing problem (2L VRP) Additionally, when no backhauls are considered our algorithm is able to find new best solutions for several 2L VRP benchmark instances with sequential oriented loading, both with and without items rotation.
Eur. J. Oper. Res.