An effective local search approach for the Vehicle Routing Problem with Backhauls

This paper deals with a practical transportation model known as the Vehicle Routing Problem with Backhauls (VRPB), which aims at designing the minimum cost route set for satisfying both delivery and pick-up demands. In methodological terms, we propose a local search metaheuristic which explores rich solution neighborhoods composed of exchanges of variable-length customer sequences. To efficiently investigate these rich solution neighborhoods, tentative local search move are statically encoded by data structures stored in Fibonacci Heaps which are special priority queue structures offering fast minimum retrieval, insertion and deletion capabilities. To avoid cycling phenomena and induce diversification, we introduce the concept of promises, which is a parameter-free mechanism based on the regional aspiration criterion used in Tabu Search implementations. The proposed metaheuristic development was tested on well-known VRPB benchmark instances. It exhibited fine performance, as it consistently generated the best-known solutions for all the examined benchmark problems.