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

✍ Scribed by Ibrahim H. Osman; Niaz A. Wassan

• Publisher: Springer US
• Year: 2002
• Tongue: English
• Weight: 195 KB
• Volume: 5
• Category: Article
• ISSN: 1094-6136
• DOI: 10.1002/jos.122

✦ Synopsis

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 di erent neighbourhood structures for the intensiÿcation and diversiÿcation phases of the search. Special data structures are also used to manage e ciently 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.