ONLINE ROUTE REPLANNING UNDER CHANGING CONSTRAINTS AND PRIORITIES IN DYNAMIC TRANSPORT ENVIRONMENTS

Abstract

Real-time transport routing systems depend on constant changes such as link failures, demand spikes, vehicle failures, regulatory restrictions, and the activation of priority tasks that render prior plans invalid [1]. Complete re-optimization from scratch is inefficient computationally for large networks operating in very tight time windows, and simple local repair heuristics give us solutions far away from optimal because a knock-on effect works its way into interdependent routes.

References

1. Pillac, V., Gendreau, M., Guéret, C., & Medaglia, A. L. (2013). A Review of Dynamic Vehicle Routing Problems. European Journal of Operational Research, 225(1), 1–11. https://doi.org/10.1016/j.ejor.2012.08.015
2. Psaraftis, H. N., Wen, M., & Kontovas, C. A. (2016). Dynamic Vehicle Routing Problems: Three Decades and Counting. Networks, 67(1), 3–31. https://doi.org/10.1002/net.21628
3. Bent, R. W., & Van Hentenryck, P. (2004). Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic Customers. Operations Research, 52(6), 977–987. https://doi.org/10.1287/opre.1040.0124
4. Berbeglia, G., Cordeau, J. F., & Laporte, G. (2010). Dynamic Pickup and Delivery Problems. European Journal of Operational Research, 202(1), 8–15. https://doi.org/10.1016/j.ejor.2009.04.024
5. Ulmer, M. W., Mattfeld, D. C., & Köster, F. (2018). Budgeting Time for Dynamic Vehicle Routing with Stochastic Customer Requests. Transportation Science, 52(1), 20–37. https://doi.org/10.1287/trsc.2016.0719
6. Ichoua, S., Gendreau, M., & Potvin, J. Y. (2007). Planned Route Optimization for Real-Time Vehicle Routing. Springer Optimization and Its Applications, 2, 1–18. https://doi.org/10.1007/978-0-387-36699-9_1
7. Ferrucci, F., Bock, S., & Gendreau, M. (2013). A Pro-Active Real-Time Control Approach for Dynamic Vehicle Routing Problems. European Journal of Operational Research, 225(1), 130–141. https://doi.org/10.1016/j.ejor.2012.09.016
8. Azi, N., Gendreau, M., & Potvin, J. Y. (2012). A Dynamic Vehicle Routing Problem with Multiple Delivery Routes. Annals of Operations Research, 199(1), 103–112. https://doi.org/10.1007/s10479-011-0991-3
9. Ulmer, M. W., Goodson, J. C., Mattfeld, D. C., & Thomas, B. W. (2020). On Modeling Stochastic Dynamic Vehicle Routing Problems. EURO Journal on Transportation and Logistics, 9(2), 100008. https://doi.org/10.1016/j.ejtl.2020.100008
10. Gendreau, M., & Potvin, J. Y. (2019). Handbook of Metaheuristics (3rd ed.). Springer. https://doi.org/10.1007/978-3-319-91086-4