A multi-product multi-layer urban freight distribution problem solved using a hybrid metaheuristic procedure

Document Type : Article


1 Instituto Tecnologico Metropolitano, Medellin, Colombia

2 Instituto Tecnologico Metropolitano, Medellin, Colombia.

3 Institucion Universitaria CEIPA, Sabaneta, Colombia

4 Universidad Nacional de Colombia, Medellin Colombia



The pick-up and delivery routing problem has received special attention thanks to its application to urban freight distribution processes. However, due to the multiple levels involved in those processes, modeling and analyzing urban distribution networks in urban contexts are complex tasks. As a result, efficient and robust solution methods should be proposed according to the dynamic and uncertain conditions that characterize this type of problems. This article presents a new formulation for the pick-up and delivery problem in a logistics distribution network composed of 3 levels: n: 1: m (n suppliers, 1 urban consolidation center, and m customers). In addition, an algorithm based on GRASP heuristic and 2-opt algorithm was implemented here to find solutions to problem, which were compared with the results of the same algorithm for a two-layer vehicle routing problem in several instances. Thus, the proposed procedure achieved a 22% improvement over such algorithm.


  1. References


    1. Arango-Serna, M. D., Gómez-Marín, C. G., and Serna-Urán, C. A. “Modelos logísticos aplicados a la distribución urbana de mercancías”, Revista EIA, 14(28), pp. 57–76 (2017).
    2. Febbraro, A. Di, Sacco, N., and Saeednia, M. “An agent-based framework for cooperative planning of intermodal freight transport chains”, Transportation Research Part C, 64, pp. 72–85 (2016).
    3. Österle, I., Aditjandra, P. T., Vaghi, C., et al. “The role of a structured stakeholder consultation process within the establishment of a sustainable urban supply chain”, Supply Chain Management: An International Journal, 20(3), pp. 284–299 (2015).
    4. Taniguchi, E., Thompson, R. G., and Yamada, T. “Recent Trends and Innovations in Modelling City Logistics”, Procedia - Social and Behavioral Sciences, 125, pp. 4–14 (2014).
    5. Arango-Serna, M. D., Zapata-Cortés, J. A., and Serna-Urán, C. A. “Collaborative multiobjective model for urban goods distribution optimization”, In New Perspectives on Applied Industrial Tools and Techniques. Management and Industrial Engineering, García-Alcaraz J., G. Alor-Hernández, A. Maldonado-Macías, and C. Sánchez-Ramírez, Eds., Springer, Cham, pp. 47–70 (2018).
    6. Estrada, M. Á. “Análisis de Estrategias Eficientes en la Logística de Distribución de Paquetería (Tesis de Doctorado)”, Universidad Politécnica de Cataluña (2007).
    7. Ponce-Cueto, E., Carrasco-Gallego, R., and García-García, R. “Propuesta de una guía de selección del modelo de distribución en el sistema logístico del canal HORECA”, Dirección y Organización, 37, pp. 67–75 (2009).
    8. Nguyen, V. P., Prins, C., and Prodhon, C. “Solving the two-echelon location routing problem by a GRASP reinforced by a learning process and path relinking”, European Journal of Operational Research, 216(1), pp. 113–126 (2012).
    9. Hemmelmayr, V. C., Cordeau, J.-F., and Crainic, T. G. “An adaptive large neighborhood search heuristic for Two-Echelon Vehicle Routing Problems arising in city logistics”, Computers & Operations Research, 39(12), pp. 3215–3228 (2012).
    10. Faccio, M. and Gamberi, M. “New City Logistics Paradigm: From the ‘Last Mile’ to the ‘Last 50 Miles’ Sustainable Distribution”, Sustainability, 7(11), pp. 14873–14894 (2015).
    11. Amaral, R. R. and Aghezzaf, E. H. “City Logistics and Traffic Management: Modelling the Inner and Outer Urban Transport Flows in a Two-tiered System”, Transportation Research Procedia (2015).
    12. Serna-Urán, C. A., Arango-Serna, M. D., Zapata-Cortés, J. A., et al. “An agent-based memetic algorithm for solving three-level freight distribution problems”, In Exploring Intelligent Decision Support Systems, J. L. Sánchez-Cervantes, G. Alor-Hernández, M. del P. Salas-Zárate, J. L. García-Alcaraz, and L. Rodríguez-Mazahua, Eds., Springer International Publishing, pp. 111–131 (2018).
    13. Xu, D., Li, K., Zou, X., et al. “An unpaired pickup and delivery vehicle routing problem with multi-visit”, Transportation Research Part E: Logistics and Transportation Review, 103, pp. 218–247 (2017).
    14. Lu, C. C., Ying, K. C., and Chen, H. J. “Real-time relief distribution in the aftermath of disasters - A rolling horizon approach”, Transportation Research Part E: Logistics and Transportation Review, 93, pp. 1–20 (2016).
    15. Crainic, T. G. and Montreuil, B. “Physical Internet Enabled Interconnected City Logistics”, Faculté des sciences de l’administration, Université Laval., 13 (2015).
    16. Hasani-Goodarzi, A. and Tavakkoli-Moghaddam, R. “Capacitated Vehicle Routing Problem for Multi-Product Cross- Docking with Split Deliveries and Pickups”, Procedia - Social and Behavioral Sciences, 62(2010), pp. 1360–1365 (2012).
    17. Shaabani, H. and Kamalabadi, I. N. “An efficient population-based simulated annealing algorithm for the multi-product multi-retailer perishable inventory routing problem”, Computers and Industrial Engineering, 99, pp. 189–201 (2016).
    18. Letchford, A. N. and Salazar-González, J. J. “Stronger multi-commodity flow formulations of the Capacitated Vehicle Routing Problem”, European Journal of Operational Research, 244(3), pp. 730–738 (2015).
    19. Rieck, J., Ehrenberg, C., and Zimmermann, J. “Many-to-many location-routing with inter-hub transport and multi-commodity pickup-and-delivery”, European Journal of Operational Research, 236(3), pp. 863–878 (2014).
    20. Serna-Urán, C. A. “Modelo multi-agente para problemas de recogida y entrega de mercancías con ventanas de tiempo usando un algoritmo memético con relajaciones difusas (Tesis de doctorado)”, Universidad Nacional de Colombia (2016).
    21. Boccia, M., Crainic, T. G., Sforza, A., et al. “Multi-commodity location-routing: Flow intercepting formulation and branch-and-cut algorithm”, Computers and Operations Research, 89, pp. 94–112 (2018).
    22. Canales-Bustos, L., Santibañez-González, E., and Candia-Véjar, A. “A multi-objective optimization model for the design of an effective decarbonized supply chain in mining”, International Journal of Production Economics, 193, pp. 449–464 (2017).
    23. Ahkamiraad, A. and Wang, Y. “Capacitated and multiple cross-docked vehicle routing problem with pickup, delivery, and time windows”, Computers and Industrial Engineering, 119(November 2016), pp. 76–84 (2018).
    24. Peres, I. T., Repolho, H. M., Martinelli, R., et al. “Optimization in inventory-routing problem with planned transshipment: A case study in the retail industry”, International Journal of Production Economics, 193, pp. 748–756 (2017).
    25. Pichka, K., Bajgiran, A. H., Petering, M. E. H., et al. “The two echelon open location routing problem: Mathematical model and hybrid heuristic”, Computers & Industrial Engineering, 121, pp. 97–112 (2018).
    26. Zhou, L., Baldacci, R., Vigo, D., et al. “A Multi-Depot Two-Echelon Vehicle Routing Problem with Delivery Options Arising in the Last Mile Distribution”, European Journal of Operational Research, 265, pp. 765–778 (2017).
    27. Toth, P. and Vigo, D. The Vehicle Routing Problem. Philadelphia, PA, USA: SIAM, 2002., Philadelphia, PA, USA: SIAM (2002).
    28. Cordeau, J.-F., Gendreau, M., Laporte, G., et al. “New Heuristics for the vehicle routing problem”, In Logistics Systems: Design and Optimization, A. Langevin and D. Riopel, Eds., Sp, New York, NY, (iv) (2005).
    29. Gropp, W. and Moré, J. J. “Optimization Environments and the NEOS Server”, In Approximation Theory and Optimization, Buhmann M. D. and A. Iserles, Eds., Cambridge University Press, pp. 167–182 (1997).
    30. Faure, L., Battaia, G., Marqués, G., et al. “How to anticipate the level of activity of a sustainable collaborative network: The case of urban freight delivery through logistics platforms”, IEEE International Conference on Digital Ecosystems and Technologies, (August), pp. 126–131 (2013).
    31. Euchi, J., Yassine, A., and Chabchoub, H. “The dynamic vehicle routing problem: Solution with hybrid metaheuristic approach”, Swarm and Evolutionary Computation, 21, pp. 41–53 (2015).
    32. Drexl, M. and Schneider, M. “A survey of variants and extensions of the location-routing problem”, European Journal of Operational Research, 241(2), pp. 283–308 (2015).