×

Learning surrogate functions for the short-horizon planning in same-day delivery problems. (English) Zbl 07493635

Stuckey, Peter J. (ed.), Integration of constraint programming, artificial intelligence, and operations research. 18th international conference, CPAIOR 2021, Vienna, Austria, July 5–8, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12735, 283-298 (2021).
Summary: Same-day delivery problems are challenging stochastic vehicle routing problems, where dynamically arriving orders have to be delivered to customers within a short time while minimizing costs. In this work, we consider the short-horizon planning of a problem variant where every order has to be delivered with the goal to minimize delivery tardiness, travel times, and labor costs of the drivers involved. Stochastic information as spatial and temporal order distributions is available upfront. Since timely routing decisions have to be made over the planning horizon of a day, the well-known sampling approach from the literature for considering expected future orders is not suitable due to its high runtimes. To mitigate this, we suggest to use a surrogate function for route durations that predicts the future delivery duration of the orders belonging to a route at its planned starting time. This surrogate function is directly used in the online optimization replacing the myopic current route duration. The function is trained offline by data obtained from running full day-simulations, sampling and solving a number of scenarios for each route at each decision point in time. We consider three different models for the surrogate function and compare with a sampling approach on challenging real-world inspired artificial instances. Results indicate that the new approach can outperform the sampling approach by orders of magnitude regarding runtime while significantly reducing travel costs in most cases.
For the entire collection see [Zbl 1482.68041].

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C27 Combinatorial optimization

Software:

Adam
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Azi, N.; Gendreau, M.; Potvin, JY, An adaptive large neighborhood search for a vehicle routing problem with multiple routes, Comput. Oper. Res., 41, 1, 167-173 (2014) · Zbl 1348.90065 · doi:10.1016/j.cor.2013.08.016
[2] Bent, RW; Van Hentenryck, P., Scenario-based planning for partially dynamic vehicle routing with stochastic customers, Oper. Res., 52, 6, 977-987 (2004) · Zbl 1165.90600 · doi:10.1287/opre.1040.0124
[3] Frohner, N., Raidl, G.R.: A double-horizon approach to a purely dynamic and stochastic vehicle routing problem with delivery deadlines and shift flexibility. In: Causmaecker, P.D., et al. (eds.) Proceedings of the 13th International Conference on the Practice and Theory of Automated Timetabling - PATAT 2021, Vol. I. Bruges, Belgium (2020)
[4] Joe, W., Lau, H.C.: Deep reinforcement learning approach to solve dynamicvehicle routing problem with stochastic customers. In: Proceedings of theInternational Conference on Automated Planning and Scheduling, vol. 30, pp. 394-402 (2020)
[5] Kingma, D.P., Ba, J.: Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014)
[6] Mitrović-Minić, S.; Krishnamurti, R.; Laporte, G., Double-horizon based heuristics for the dynamic pickup and delivery problem with time windows, Trans. Res. Part B: Methodol., 38, 8, 669-685 (2004) · doi:10.1016/j.trb.2003.09.001
[7] Pisinger, D.; Ropke, S., A general heuristic for node routing problems, Comput. Oper. Res., 34, 2403-2435 (2007) · Zbl 1144.90318 · doi:10.1007/978-3-642-46629-8_9
[8] Powell, WB, Approximate Dynamic Programming: Solving the Curses of Dimensionality (2007), Hoboken: Wiley, Hoboken · Zbl 1156.90021 · doi:10.1002/9780470182963
[9] Ritzinger, U.; Puchinger, J.; Hartl, RF, A survey on dynamic and stochastic vehicle routing problems, Int. J. Prod. Res., 54, 1, 215-231 (2016) · doi:10.1080/00207543.2015.1043403
[10] Ropke, S.; Pisinger, D., An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Trans. Sci., 40, 4, 455-472 (2006) · doi:10.1287/trsc.1050.0135
[11] Ulmer, Marlin W.; Thomas, Barrett W.; Mattfeld, Dirk C., Preemptive depot returns for dynamic same-day delivery, EURO J. Trans. Logist., 8, 4, 327-361 (2018) · doi:10.1007/s13676-018-0124-0
[12] Voccia, SA; Campbell, AM; Thomas, BW, The same-day delivery problem for online purchases, Trans. Sci., 53, 1, 167-184 (2019) · doi:10.1287/trsc.2016.0732
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.