A new insertion-based construction heuristic for solving the pickup and delivery problem with time windows

A new insertion-based construction heuristic for solving the pickup and delivery problem with time windows

0.00 Avg rating0 Votes
Article ID: iaor20083821
Country: Netherlands
Volume: 175
Issue: 2
Start Page Number: 672
End Page Number: 687
Publication Date: Dec 2006
Journal: European Journal of Operational Research
Authors: ,
Keywords: heuristics
Abstract:

In this paper we present a new insertion-based construction heuristic to solve the multi-vehicle pickup and delivery problem with time windows. The new heuristic does not only consider the classical incremental distance measure in the insertion evaluation criteria but also the cost of reducing the time window slack due to the insertion. We also present a non-standard measure, crossing length percentage, in the insertion evaluation criteria to quantify the visual attractiveness of the solution. We compared our heuristic with a sequential and a parallel insertion heuristic on different benchmarking problems, and the computational results show that the proposed heuristic performs better with respect to both the standard and nonstandard measures.

Reviews

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