Exact and heuristic static routing algorithms for improving online grocery shoppingblogistics

  • Francesco Cepolina 
  • Elvezia Maria Cepolina, 
  • c Guido Ferla  
  • Department of Mechanical Engineering, DIME, University of Genoa, Genoa, 16145, Italy
  • b Italian Center of Excellence on Logistics, Transport and Infrastructure, CIELI, University of Genoa, Genoa, 16135, Italy
  • c School of Sciences and Technology, University of Camerino, Italy
Cite as
Cepolina F., Cepolina E.M., Ferla G. (2021). Exact and heuristic static routing algorithms for improving online grocery shopping logistics. Proceedings of the 23rd International Conference on Harbor, Maritime and Multimodal Logistic Modeling & Simulation(HMS 2021), pp. 17-26 . DOI: https://doi.org/10.46354/i3m.2021.hms.003

Abstract

The context is online grocery shopping and the paper focuses on the optimization of the related transport logistics that can lead to important economic and environmental advantages. At the beginning of the day, each customer provides: a shopping list, defining the product typologies and the related quantities to be collected from the different shops, the delivery address and the related delivery time window. One vehicle is in charge of serving all the customers by collecting the products from the shops and by delivering them to the provided delivery addresses. The target is to find the shortest path that satisfies the customer’s needs.
The proposed routing algorithms could support also logistic processes in supermarket supply. Each supermarket defines the daily freight demand, in terms of product typologies and related quantities, to be collected from the different manufactures/distributors, the delivery address and the related delivery time window. One vehicle is in charge of collecting the products from manufactures/distributors and of delivering them to the provided delivery addresses.
The faced problem is therefore a complex multi commodity pick-up and delivery traveling salesman problem. Many constraints could be taken into account, related, for instance, to ecology and customer satisfaction. One local and four global optimization algorithms are proposed; their advantages and limits are discussed.  The algorithms are tested on a basic logistic example, the numerical results are reported. The proposed algorithms use effective and efficient optimization algorithms able to minimize the overall miles necessary to deliver the goods in order to increase business efficiency.

References

  1. Ascheuer, N., Jünger, M., Reinelt, G. (2000). A branch & cut algorithm for the asymmetric traveling salesman problem with precedence constraints. Comput. Optim. Appl. 17:61–84.
  2. Bruzzone, A.G., Longo, F. (2010). An advanced system for supporting the decision process within large scale retail stores. Simulation, 86(12),742-762
  3. Cepolina E.M., Farina A., Holloway C., Tyler N. (2015). Innovative strategies for urban car-sharing systems and a simulator to assess their performance. Transportation Planning and
    Technology. 38:375-391.
  4. Cepolina, E.M. (2016). The packages clustering optimisation in the logistics of the last mile freight distribution. International Journal of Simulation and Process Modelling, 11:468-478
  5. Cepolina, E.M., Cepolina, F., Ferla, G. (2021). On line grocery shopping: a fast dynamic vehicle routing algorithm for dealing with information evolution. In E. Bottani, A. G. Bruzzone, F. Longo, Y. Merkuryev, M. A. Piera (Eds.). Proceedings of the International Conference on Harbor, Maritime and Multimodal Logistic Modeling & Simulation (HMS 2021). DIME Università di Genova, DIMEG Università della Calabria: Publisher.
  6. De Giovanni, L., Gastaldon, N., Losego, M., Sottovia, F. (2018). Algorithms for a Vehicle Routing Tool Supporting Express Freight Delivery in Small Trucking Companies. Transportation research procedia. 30:197-206.
  7. Hernández-Pérez, H., Salazar-González, J.-J. (2004). A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery. Discrete Appl. Math. 145:126–139.
  8. Lu, Q., Dessouky, M. (2004). An exact algorithm for the multiple vehicle pickup and delivery problem. Transportation Sci. 38:503–514.
  9. Molfino, R., Zoppi, M., Muscolo, G.G., Cepolina, E.M., Farina, A., Nashashibi, F., Pollard and E., Dominguez, J.A. (2015). An electro-mobility system for freight service in urban areas. International Journal of Electric and Hybrid Vehicles, 7:1-21.
  10. Psaraftis, H. (1983). An exact algorithm for the single vehicle many-to-many dial-a-ride problem with time windows. Transportation Science. 17:351–357.
  11. Renaud, J., Boctor, F.F., Laporte, G. (2002). Pertubation heuristics for the pickup and delivery traveling salesman problem. Comp. Oper. Res. 29:1129–1141.
  12. Renaud, J., Boctor, F.F., Ouenniche, J. (2000). A heuristic for the pickup and delivery traveling salesman problem. Comp. Oper. Res. 27:905–916.
  13. Rodriguez-Martin, I. and Salazar González, J. J. (2011). The Multi-Commodity One-to-One Pickup-and-Delivery Traveling Salesman Problem: A Matheuristic. In Pahl J., Reiners T., Voß S. (Eds.). Networ Optimization. INOC 2011. Lecture Notes in Computer Science. 49:258–272.
    Springer, Berlin, Heidelberg.
  14. Ropke, S., Cordeau, J.-F., Laporte, G. (2007). Models and branch-and-cut algorithms for pickup and delivery problems with time windows. Networks.