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

Document Type : Research Article

Authors

1 Quality and Production Engineering, Instituto Tecnológico Metropolitano, Medellín, Colombia

2 Fundación Universitario CEIPA, School of Management, Sabaneta, Colombia

3 Department of Organization Engineering, Universidad Nacional de Colombia, Medellín, Colombia

Abstract

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 (UCC), and m customers). In addition, an algorithm based on a Greedy Randomized Adaptive Search Procedure (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 (VRP) in several instances. Thus, the proposed procedure achieved a 22% improvement over such algorithm.

Keywords


References:
1.Arango-Serna, M.D., Gómez-Marín, C.G., and Serna-Urán, C.A. “Modelos logísticos aplicados a ladistribución urbana de mercancías”, Revista EIA,14(28), pp. 57–76 (2017).https://doi.org/10.24050/reia.v14i28.1055.
2.Febbraro, A.Di., Sacco, N., and Saeednia, M. “An agent-based framework for cooperative planning of intermodal freight transport chains”, Transportation Research PartC, 64, pp. 72–85 (2016). http://dx.doi.org/10.1016/j.trc.2015.12.014.
3.Österle, I., Aditjandra, P.T., Vaghi, C., et al. “The role ofa structured stakeholder consultation process within theestablishment of a sustainable urban supply chain”,Supply Chain Management: An International Journal,20(3), pp. 284–299 (2015).https://doi.org/10.1108/SCM-05-2014-0149.
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).https://doi.org/10.1016/j.sbspro.2014.01.1451.
5.Arango-Serna, M.D., Zapata-Cortés, J.A., and Serna-Urán, C.A. “Collaborative multiobjective model forurban goods distribution optimization”, In NewPerspectives on Applied Industrial Tools andTechniques. 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). https://10.1007/978-3-319-56871-3_3.
6.Estrada, M.Á. “Análisis de estrategias eficientes en lalogística de distribución de paquetería”, (PhD Thesis),Universidad Politécnica de Cataluña (2007).http://www.tdx.cat/TDX-1211108-170550.
7.Ponce-Cueto, E., Carrasco-Gallego, R., and García-García, R. “Propuesta de una guía de selección delmodelo de distribución en el sistema logístico del canalHORECA”, Dirección y Organización, 37, pp. 67–75(2009). https://doi.org/10.37610/dyo.v0i37.40.
8.Nguyen, V.P., Prins, C., and Prodhon, C. “Solving thetwo-echelon location routing problem by a GRASPreinforced by a learning process and path relinking”,European Journal of Operational Research, 216(1), pp.113–126 (2012).http://dx.doi.org/10.1016/j.ejor.2011.07.030.
9.Hemmelmayr, V.C., Cordeau, J.-F., and Crainic, T.G.“An adaptive large neighborhood search heuristic fortwo-echelon vehicle routing problems arising in citylogistics”, Computers & Operations Research, 39(12),pp. 3215–3228 (2012).http://dx.doi.org/10.1016/j.cor.2012.04.007.
10.Faccio, M. and Gamberi, M. “New city logisticsparadigm: from the ‘last mile’ to the ‘last 50 miles’ sustainable distribution”, Sustainability, 7(11), pp.14873–14894 (2015). https://doi.org/10.3390/su71114873.
11.Amaral, R.R. and Aghezzaf, E.H. “City logistics andtraffic management: Modelling the inner and outerurban transport flows in a two-tiered system”,Transportation Research Procedia, 6, pp 297-312(2015). https://doi.org/10.1016/j.trpro.2015.03.023.
12.Serna-Urán, C.A., Arango-Serna, M.D., Zapata-Cortés,J.A., et al. “An agent-based memetic algorithm forsolving three-level freight distribution problems”, InExploring 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). https://doi.org/10.1007/978-3-319-74002-7_6.
13.Xu, D., Li, K., Zou, X., et al. “An unpaired pickup anddelivery vehicle routing problem with multi-visit”,Transportation Research Part E: Logistics andTransportation Review, 103, pp. 218–247 (2017).http://dx.doi.org/10.1016/j.tre.2017.04.011.
14.Lu, C.C., Ying, K.C., and Chen, H.J. “Real-time reliefdistribution in the aftermath of disasters - A rollinghorizon approach”, Transportation Research Part E:Logistics and Transportation Review, 93, pp. 1–20(2016). http://dx.doi.org/10.1016/j.tre.2016.05.002.
15.Crainic, T.G. and Montreuil, B. “Physical internetenabled interconnected city logistics”, Faculté dessciences de l’administration, Université Laval, 13(2015). http://doi.org/10.35090/gatech/7991.
16.Hasani-Goodarzi, A. and Tavakkoli-Moghaddam, R.“Capacitated vehicle routing problem for multi-productcross-docking with split deliveries and pickups”,Procedia - Social and Behavioral Sciences, 62(2010), pp. 1360–1365 (2012). https://doi.org/10.1016/j.sbspro.2012.09.232.
17.Shaabani, H. and Kamalabadi, I.N. “An efficientpopulation-based simulated annealing algorithm for themulti-product multi-retailer perishable inventoryrouting problem”, Computers and IndustrialEngineering, 99, pp. 189–201 (2016).http://dx.doi.org/10.1016/j.cie.2016.07.022.
18.Letchford, A.N. and Salazar-González, J.J. “Strongermulti-commodity flow formulations of the capacitatedvehicle routing problem”, European Journal ofOperational Research, 244(3), pp. 730–738 (2015).http://dx.doi.org/10.1016/j.ejor.2015.02.028.
19.Rieck, J., Ehren berg, C., and Zimmermann, J. “Many-to-many location-routing with inter-hub transport andmulti-commodity pickup-and-delivery”, EuropeanJournal of Operational Research, 236(3), pp. 863–878(2014). http://dx.doi.org/10.1016/j.ejor.2013.12.021.
20.Serna-Urán, C.A. “Modelo multi-agente para problemasde recogida y entrega de mercancías con ventanas detiempo usando un algoritmo memético con relajacionesdifusas”, (PhD Thesis), Universidad Nacional deColombia (2016).https://repositorio.unal.edu.co/handle/unal/57426.
21.Boccia, M., Crainic, T.G., Sforza, A., et al. “Multi-commodity location-routing: Flow interceptingformulation and branch-and-cut algorithm”, Computersand Operations Research, 89, pp. 94–112 (2018).http://dx.doi.org/10.1016/j.cor.2017.08.013.
22.Canales-Bustos, L., Santibañez-González, E., andCandia-Véjar, A. “A multi-objective optimization model for the design of an effective decarbonized supply chainin mining”, International Journal of ProductionEconomics,193, pp. 449–464 (2017). https://doi.org/10.1016/j.ijpe.2017.08.012.
23.Ahkamiraad, A. and Wang, Y. “Capacitated and multiplecross-docked vehicle routing problem with pickup,delivery, and time windows”, Computers and IndustrialEngineering, 119(November 2016), pp. 76–84 (2018).https://doi.org/10.1016/j.cie.2018.03.007.
24.Peres, I.T., Repolho, H.M., Martinelli, R., et al.“Optimization in inventory-routing problem withplanned transshipment: A case study in the retailindustry”, International Journal of ProductionEconomics, 193, pp. 748–756 (2017).https://doi.org/10.1016/j.ijpe.2017.09.002.
25.Pichka, K., Bajgiran, A.H., Petering, M.E.H., et al. “Thetwo echelon open location routing problem:Mathematical model and hybrid heuristic”, Computersand Industrial Engineering, 121, pp. 97–112 (2018).https://doi.org/10.1016/j.cie.2018.05.010.
26.Zhou, L., Baldacci, R., Vigo, D., et al. “A multi-depottwo-echelon vehicle routing problem with delivery Journal of Operational Research, 265, pp. 765–778 (2017). http://dx.doi.org/10.1016/j.ejor.2017.08.011.
27.Toth, P. and Vigo, D. The Vehicle Routing Problem.Philadelphia, PA, USA: SIAM, 2002., Philadelphia, PA, USA: SIAM (2002).https://doi.org/10.1137/1.9780898718515.
28.Cordeau, J.-F., Gendreau, M., Laporte, G., et al. “Newheuristics for the vehicle routing problem”, In LogisticsSystems: Design and Optimization, A. Langevin and D.Riopel, Eds., Sp, New York, NY, (iv) (2005).https://doi.org/10.1007/0-387-24977-X_9.
29.Gropp, W. and Moré, J.J. “Optimization Environmentsand the NEOS Server”, Argonne National Laboratory,Illinois, (1997).
30.Faure, L., Battaia, G., Marqués, G., et al. “How toanticipate the level of activity of a sustainablecollaborative network: The case of urban freightdelivery through logistics platforms”, IEEEInternational Conference on Digital Ecosystems andTechnologies, (August), pp. 126–131 (2013).https://doi.org/10.1109/DEST.2013.6611341.
31.Euchi, J., Yassine, A., and Chabchoub, H. “The dynamicvehicle routing problem: Solution with hybridmetaheuristic approach”, Swarm and EvolutionaryComputation, 21, pp. 41–53 (2015).http://dx.doi.org/10.1016/j.swevo.2014.12.003.
32.Drexl, M. and Schneider, M. “A survey of variants andextensions of the location-routing problem”, EuropeanJournal of Operational Research, 241(2), pp. 283–308(2015). http://dx.doi.org/10.1016/j.ejor.2014.08.030.
Volume 32, Issue 4
Transactions on Industrial Engineering
January and February 2025 Article ID:5191
  • Receive Date: 16 December 2020
  • Accept Date: 14 February 2022