A Biased-Randomised Large Neighbourhood Search for the two-dimensional Vehicle Routing Problem with Backhauls

• We define and solve the two-dimensional Vehicle Routing Problem with Backhauls.
• We combine Large Neighbourhood Search with biased-randomised heuristics.
• Our approach found new best solutions for some benchmark instances without backhauls.
• We also permit items rotation in the packing process, a rarely considered assumption.

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.