Offline-Online Reoptimization using a Hybrid Method

Offline-Online Reoptimization using a Hybrid Method

de Vringer, Stefan (TU Delft Electrical Engineering, Mathematics and Computer Science; TU Delft Algorithmics)

Yorke-Smith, N. (mentor)
Alonso Mora, J. (graduation committee)
Broz, F. (graduation committee)

Delft University of Technology

2022-01-28

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.

Vehicle Routing
Reinforcement Learning
Heuristics
Reoptmization

http://resolver.tudelft.nl/uuid:3aeb02ba-bc69-46ba-a3b2-84d9cbd54a81

Student theses

master thesis

© 2022 Stefan de Vringer