Offline-Online Reoptimization using a Hybrid Method

Master thesis (2022)

Authors

S.O. de Vringer Electrical Engineering, Mathematics and Computer Science

Contributors

N. Yorke-Smith Algorithmics - EEMCS (mentor)
J. Alonso-Mora Learning & Autonomous Control - Mechanical, Maritime and Materials Engineering (graduation committee member)
F. Broz Interactive Intelligence - EEMCS (graduation committee member)
Faculty
Electrical Engineering, Mathematics and Computer Science, Electrical Engineering, Mathematics and Computer Science
Copyright: © 2022 Stefan de Vringer
More Info
expand_more

Published Date

28-01-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

Realistic vehicle routing problems have been highly relevant for years in a wide variety of domains. One such domain is food delivery, where well-crafted routes can reduce costs and contribute to customer satisfaction. This thesis formulates a problem variant for the restaurant meal delivery problem in order to examine the reoptimization of meal delivery routes. A novel solution algorithm that combines rule-based reinforcement learning and adaptive large neighbourhood search is used to tackle the problem. This hybrid algorithm manages to incorporate both learning and handcrafted search heuristics, as well as both offline and online computation. Analysis of the algorithmic components shows that the proposed algorithmic approach is computationally feasible for small scale reoptimization problems. Analysis also demonstrates that the reinforcement learning component currently does not improve performance with respect to the established objective function.