A Two-Stage Hybrid Heuristic for Vehical Routing Problem with Pickups and Deliveries

This paper presents a two-stage hybrid heuristic for vehicle routing problem with pickups and deliveries. The first stage uses a simple simulated annealing algorithm to decrease the number of routes, while the second stage is to decrease total travel cost. The performance of the proposed algorithm was tested on benchmark instances involving from 100 to 600 customers. It produced high quality results, improving several best solutions previously reported. These results further confirm the benefits of two-stage approaches in vehicle routing.