Solving the Multi-vehicle Pick-up and Delivery Problem with Time Widows by New Construction Heuristic

A new insertion-based construction heuristic is presented to solve the multi-vehicle pickup and delivery problem with time windows. A non-standard measure, crossing length percentage, is presented in the insertion evaluation criteria to quantify the visual attractiveness of the solution. The heuristic is compared 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 non-standard measures