Offline-Online Reoptimization using a Hybrid Method

More Info


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.