A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows

A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows

0.00 Avg rating0 Votes
Article ID: iaor20071803
Country: United Kingdom
Volume: 33
Issue: 4
Start Page Number: 875
End Page Number: 893
Publication Date: Apr 2006
Journal: Computers and Operations Research
Authors: ,
Keywords: optimization: simulated annealing, heuristics
Abstract:

This paper presents a two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows and multiple vehicles (PDPTW). The first stage uses a simple simulated annealing algorithm to decrease the number of routes, while the second stage uses Large neighborhood search (LNS) to decrease total travel cost. Experimental results show the effectiveness of the algorithm which has produced many new best solutions on problems with 100, 200, and 600 customers. In particular, it has improved 47% and 76% of the best solutions on the 200 and 600-customer benchmarks, sometimes by as much as 3 vehicles. These results further confirm the benefits of two-stage approaches in vehicle routing. They also answer positively the open issue in the original LNS paper, which advocated the use of LNS for the PDPTW and argue for the robustness of LNS with respect to side-constraints.

Reviews

Required fields are marked *. Your email address will not be published.