The pickup and delivery problem with time-dependent travel times

Abstract

In this thesis we consider the multi-depot vehicle routing problem with pickup and delivery requests with time windows, based on a real world case of a precision transport company. To be able to generate more realistic schedules we include time dependent travel times in our model. The algorithm can handle alternative pickup and delivery locations and times, and gives the possibility to generate solutions with a maximum shift time to make sure driver regulations are respected. This problem is solved using a simulated annealing approach combined with large neighborhood operators. The algorithm is guided towards better solutions by using a selection probability that prefers better changes, and a similarity value to select orders that are similar to each other. A comparison using a benchmark by Li & Lim shows that our algorithm is competitive on basic Pickup and Delivery instances with time windows. To allow for comparison of algorithms in further research we have created a benchmark for the problem with time dependency and alternative pickup and delivery options.