Truck Routing for an Online Grocer

Solving a Pickup and Delivery Problem with Resource Constraint

Master thesis (2022)

Authors

T.J.N. Barendse Electrical Engineering, Mathematics and Computer Science

Contributors

N. Yorke-Smith Algorithmics - EEMCS (mentor)
G. Konijnendijk (mentor)
J.T. van Essen Discrete Mathematics and Optimization - EEMCS (graduation committee member)
J. Alonso-Mora Learning & Autonomous Control - Mechanical, Maritime and Materials Engineering (graduation committee member)
Faculty
Electrical Engineering, Mathematics and Computer Science, Electrical Engineering, Mathematics and Computer Science
Copyright: © 2022 Thomas Barendse
More Info
expand_more

Published Date

21-04-2022

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

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.