Optimizing the transport scheduling of an online grocer

Abstract

In this thesis, we consider the Multi Depot Vehicle Scheduling Problem with Time Windows with driver day duration restrictions that addresses the task of assigning a given set of time window shipments to trucks with consideration of practical requirements. The goal of this thesis is to design an algorithm that finds a good solution for the problem within 15 minutes. In the literature, the problem is usually applied to public transport cases. We consider the freight transport application of an online grocer. We introduce a Multi-Commodity Minimum Network Flow ILP implementation for MDVSPTW with short computation time. Also, based on the Concurrent Scheduler algorithm for MDVSP from the literature, we introduce the Greedy Scheduler algorithm that is able to find a feasible solution within short computation time for our problem. These two implementations form building blocks for the three main algorithms we introduce, that find good feasible solutions for our problem within 15 minutes: the ILP + Greedy algorithm, the Random Search algorithm and the Random Search and Fix algorithm. We incorporate the driver day duration restriction in the three algorithms by either allowing a driver change, that is two drivers executing one truck day, or not, and compare the results. We show that the ILP + Greedy algorithm performs the best. In the case an algorithm that does not involve an ILP is preferred, e.g., for robustness reasons, the Random Search and Fix algorithm performs better than the Random Search algorithm.