Truck Routing for an Online Grocer: Solving a Pickup and Delivery Problem with Resource Constraint

Demand for online grocer Picnic has increased exponentially over the past years, and their truck transport operation must scale with it. Given the resource constraints at all warehouses, as well as other specific restrictions, this poses a Multi Depot Pickup and Delivery Problem with Resource Constraints, for which no good solutions are found to date. The goal of this thesis is to develop an algorithm that provides good solutions to this problem within 30 minutes.This thesis presents three solution methods to solve this problem. The first is an Adaptive Large Neighbourhood Search (ALNS) algorithm closely related to earlier research. We propose a mechanism with only linear time additional complexity to impose the resource constraint. We also demonstrate ways to take additional constraints into account, such as minimum route duration and driver switches. For the second method, dubbed ALNS+LS, we extend the ALNS with local search heuristics to enhance its performance. As a third method, we propose a matheuristic novel to this specific problem class. This consists of the ALNS+LS algorithm applied to the problem without resource constraints in the first phase, and imposing the constraints using a Constraint Programming model in the second phase. We show that the ALNS+LS outperforms the other two algorithms on a real-life-inspired benchmark set, and that the matheuristic comes close to the ALNS+LS for small instances. We finally show that the full problem is best solved by decomposing it into four parts and solving these separately.Computer Scienc