[Zurück]

N. Frohner, G. Raidl:
"A Double-Horizon Approach to a Purely Dynamic and Stochastic Vehicle Routing Problem with Delivery Deadlines and Shift Flexibility";
Vortrag: International Conference of the Practice and Theory of Automated Timetabling (PATAT), Bruges, Belgium; 25.08.2020 - 29.08.2020; in: "Proceedings of the 13th International Conference on the Practice and Theory of Automated Timetabling", (2020), ISBN: 978-0-9929984-3-1; S. 58 - 76.

We are facing a purely dynamic and stochastic vehicle routing problem with delivery deadlines motivated by a real-world application where orders arrive at an online store dynamically over a day to be delivered within short time. Pure dynamism is given since we do not know any orders in advance, whereas the stochastic aspect comes into play by having estimates for the hourly numbers of orders. The goal is to satisfy the daily demand by constructing closed routes from a single depot to the customers given a set of drivers with a predefined shift plan and the hourly demand estimates as input while first minimizing due time violations and then labor and travel costs. Labor costs are subject to optimization since the end times of shifts have a certain amount of flexibility and a decision has to made whether to send home a driver earlier than planned or to extend the shift.
In this work, we present a novel double-horizon approach based on the shifts and the hourly demand estimation. Within the shorter horizon we optimize the routes for the orders currently available whereas within the longer horizon we extrapolate until the end of the day to determine target shift end times for the drivers. Furthermore, we devise a route departure time strategy that balances between route quality and risking due time violations. The routing is performed by a classical adaptive large neighborhood search. We consider artificial instances and compare the results for the online problem with those for the offline scenario where all orders are known from the beginning. We observe superior performance of our approach as compared to fixed route departure time and driver send home strategies.

https://publik.tuwien.ac.at/files/publik_293661.pdf