The Role of Optimization and Machine Learning in e-Commerce Logistics in 2030

Authors: Vincenzo Capalbo, Gianpaolo Ghiani, Emanuele Manni

Abstract:

Global e-commerce sales have reached unprecedented levels in the past few years. As this trend is only predicted to go up as we continue into the ’20s, new challenges will be faced by companies when planning and controlling e-commerce logistics. In this paper, we survey the related literature on Optimization and Machine Learning as well as on combined methodologies. We also identify the distinctive features of next-generation planning algorithms - namely scalability, model-and-run features and learning capabilities - that will be fundamental to cope with the scale and complexity of logistics in the next decade.

Keywords: e-Commerce, Logistics, Machine Learning, Optimization.

References:

[1] Allied Market Research (2017), E-Commerce Logistics Market Report.
[2] Ashton, K. That ‘internet of things’ thing, RFID journal 22(7), 97–114, 2009.
[3] Attanasio, A., Cordeau, J.-F., Ghiani, G. and Laporte, G. Parallel tabu search heuristics for the dynamic multi-vehicle dial-a-ride problem. Parallel Computing, 30(3), 377–387, 2004.
[4] Baker, B.M. and Sheasby, J. Extensions to the generalised assignment heuristic for vehicle routing. European Journal of Operational Research, 119(1), 147–157, 1999.
[5] Bektas¸, T., Erdo˘gan, G. and Røpke, S. Formulations and branch-and-cut algorithms for the generalized vehicle routing problem. Transportation Science, 45(3), 299–316, 2011.
[6] Bondi, A.B. Characteristics of scalability and their impact on performance. In: Proceedings of the 2nd international workshop on Software and performance, pp. 195–203, 2000.
[7] Baldacci, R., Hadjiconstantinou, E. and Mingozzi, A. An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation. Operations research, 52(5), 723–738, 2004.
[8] Baldacci, R., Christofides, N. and Mingozzi, A. An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Mathematical Programming, 115(2), 351–385, 2008.
[9] Braekers, K., Ramaekers, K. and Van Nieuwenhuyse, I. The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering, 99, 300–313, 2016.
[10] Brand˜ao, J. A tabu search algorithm for the heterogeneous fixed fleet vehicle routing problem. Computers & Operations Research, 38(1), 140–151, 2011.
[11] Christofides, N., Mingozzi, A. and Toth, P. State-space relaxation procedures for the computation of bounds to routing problems. Networks, 11(2), 145–164, 1981.
[12] Clarke, G. and Wright, J.W. Scheduling of vehicles from a central depot to a number of delivery points. Operations research, 12(4), 568–581, 1964.
[13] Cooray, P.L.N.U. and Rupasinghe, T.D. Machine learning-based parameter tuned genetic algorithm for energy minimizing vehicle routing problem. Journal of Industrial Engineering, 2017.
[14] Dantzig, G.B. and Ramser, J.H. The truck dispatching problem. Management science, 6(1):80–91, 1959.
[15] Ferrucci, F. and Bock, S. Real-time control of express pickup and delivery processes in a dynamic environment. Transportation Research Part B: Methodological, 63, 1–14, 2014.
[16] Gendreau, M. and Potvin, J.Y. (Eds.). Handbook of metaheuristics (Vol. 2). New York: Springer, 2010.
[17] Ghiani, G., Manni, A. and Manni, E. A scalable anticipatory policy for the dynamic pickup and delivery problem. Submitted for publication, 2019.
[18] Ghiani, G., Manni, E., Quaranta, A. and Triki, C. Anticipatory algorithms for same-day courier dispatching. Transportation Research Part E: Logistics and Transportation Review, 45(1), 96–106, 2009.
[19] Godfrey, G.A. and Powell, W.B. An adaptive dynamic programming algorithm for dynamic fleet management, I: Single period travel times. Transportation Science, 36(1), 21–39, 2002.
[20] Golden, B.L., Raghavan, S. and Wasil, E.A. (Eds.). The vehicle routing problem: latest advances and new challenges (Vol. 43). Springer Science & Business Media, 2008.
[21] Gutierrez-Rodr´ıguez, A.E., Conant-Pablos, S.E., Ortiz-Bayliss, J.C. and Terashima-Mar´ın, H. Selecting meta-heuristics for solving vehicle routing problems with time windows via meta-learning. Expert Systems with Applications, 118, 470–481, 2019.
[22] Hadjiconstantinou, E., Christofides, N. and Mingozzi, A. A new exact algorithm for the vehicle routing problem based on q-paths and k-shortest paths relaxations. Annals of Operations Research, 61(1), 21–43, 1995.
[23] He, Q., Irnich, S. and Song, Y. Branch-and-Cut-and-Price for the Vehicle Routing Problem with Time Windows and Convex Node Costs. Transportation Science, 53(5), 1409–1426, 2019.
[24] Holler, J., Vuorio, R., Qin, Z., Tang, X., Jiao, Y., Jin, T., Singh., S., Wang, C. and Ye, J. Deep Reinforcement Learning for Multi-Driver Vehicle Dispatching and Repositioning Problem. In: 2019 IEEE International Conference on Data Mining (ICDM), pp. 1090–1095, 2019.
[25] Koza, J.R. Human-competitive results produced by genetic programming. Genetic programming and evolvable machines, 11(3-4), 251–284, 2010.
[26] Kunze, O. Replicators, ground drones and crowd logistics a vision of urban logistics in the year 2030. Transportation Research Procedia, 19:286–299, 2016.
[27] Laporte, G. Fifty years of vehicle routing. Transportation science, 43(4), 408–416, 2009.
[28] Laporte, G., Nobert, Y. and Desrochers, M. Optimal routing under capacity and distance restrictions. Operations research, 33(5), 1050–1073, 1985.
[29] Lu, H., Zhang, X. and Yang, S. A Learning-based Iterative Method for Solving Vehicle Routing Problems. In: International Conference on Learning Representations, 2019.
[30] Magrassi, P., Panarella, A., Deighton, N. and Johnson, G. (2001), Computers to acquire control of the physical world, Gartner research report T-14-0301.
[31] Mao, C. and Shen, Z. A reinforcement learning framework for the adaptive routing problem in stochastic time-dependent network. Transportation Research Part C: Emerging Technologies, 93, 179–197, 2018.
[32] Nazari, M., Oroojlooy, A., Snyder, L. and Tak´ac, M. Reinforcement learning for solving the vehicle routing problem. In: Advances in Neural Information Processing Systems, pp. 9839–9849, 2018.
[33] Potvin, J.Y., Lapalme, G. and Rousseau, J.M. Integration of AI and OR techniques for computer-aided algorithmic design in the vehicle routing domain. Journal of the Operational Research Society, 41(6), 517–525, 1990.
[34] Reischel, G. Die Post macht den Kofferraum zum Briefkasten. Future zone Technology News, 2015.
[35] Renaud, J., Boctor, F.F. and Laporte, G. An improved petal heuristic for the vehicle routeing problem. Journal of the operational Research Society, 47(2), 329–336, 1996.
[36] Schilde, M., Doerner, K.F. and Hartl, R.F. Integrating stochastic time-dependent travel speed in solution methods for the dynamic dial-a-ride problem. European journal of operational research, 238(1), 18–30, 2014.
[37] Secomandi, N. Comparing neuro-dynamic programming algorithms for the vehicle routing problem with stochastic demands. Computers & Operations Research, 27(11-12), 1201–1225, 2000.
[38] T-systems. Big Data in Logistics, 2020.
[39] Teng, S.H. Scalable algorithms for data and network analysis. Foundations and Trends in Theoretical Computer Science, 12(1-2), 1–274, 2016.
[40] Thomas, B.W. Waiting strategies for anticipating service requests from known customer locations. Transportation Science, 41(3), 319–331, 2007.
[41] Thompson, P.M. and Psaraftis, H.N. Cyclic transfer algorithm for multivehicle routing and scheduling problems. Operations Research, 41(5), 935–946, 1993.
[42] Toth, P. and Vigo, D. (Eds.). Vehicle routing: problems, methods, and applications. Society for Industrial and Applied Mathematics, 2014.
[43] Ulmer, M.W., Mattfeld, D.C. and K¨oster, F. Budgeting time for dynamic vehicle routing with stochastic customer requests. Transportation Science, 52(1), 20–37, 2018.
[44] Voccia, S.A., Campbell, A.M. and Thomas, B.W. The same-day delivery problem for online purchases. Transportation Science, 53(1), 167–184, 2019.
[45] Wei, L., Zhang, Z., Zhang, D. and Leung, S.C. A simulated annealing algorithm for the capacitated vehicle routing problem with two-dimensional loading constraints. European Journal of Operational Research, 265(3), 843.-859, 2018.
[46] Wei, L., Zhang, Z., Zhang, D. and Lim, A. A variable neighborhood search for the capacitated vehicle routing problem with two-dimensional loading constraints. European Journal of Operational Research, 243(3), 798–814, 2015.
[47] Yu, J.J.Q., Yu, W. and Gu, J. Online vehicle routing with neural combinatorial optimization and deep reinforcement learning. IEEE Transactions on Intelligent Transportation Systems, 20(10), 3806–3817, 2019.