A reactive tabu search meta-heuristic for the vehicle routing problem with back-hauls

The vehicle routing problem with back-hauls involves the design of a set of minimum cost routes, originating and terminating at a central depot, for a set of vehicles to service a set of customers with known quantities to be either delivered or collected. This paper describes two route-construction heuristics that generate initial solutions quickly. These heuristics are based on the saving-insertion and saving-assignment procedures, respectively. The initial solutions are then improved by a reactive tabu search meta-heuristic. The reactive concept is used in a new way to trigger the switch between different neighbourhood structures for the intensification and diversification phases of the search. Special data structures are also used to manage efficiently the search of the neighbourhood space. Computational results are reported for a number of benchmarks. The results show that the proposed meta-heuristic is robust and competitive to the best approaches in the literature.