[en] First-mile logistics tackles the movement of products from retailers to a warehouse or distribution centre. This first step towards the end customer has been pushed by large e-commerce platforms forming extensive networks of partners and is critical for fast deliveries. First-mile pickup requires efficient methods different from those developed for last-mile delivery, among other reasons due to the complexity of cargo features and volume — increasing the relevance of advanced packing methods. More importantly, the problem is essentially dynamic and the pickup process, in which the vehicle is initially empty, is much more flexible to react to disruptions arising when the vehicles are en route.
We model the static first-mile pickup problem as a vehicle routing problem for a heterogeneous fleet, with time windows and three-dimensional packing constraints. Moreover, we propose an approach to tackle the dynamic problem, in which the routes can be modified to accommodate disruptions — new customers’ demands and modified requests of known customers that are arriving while the initially established routes are being covered. We propose three reactive strategies for addressing the disruptions depending on the number of vehicles available, and study their results on a newly generated benchmark for dynamic problems.
The results allow quantifying the impact of disruptions depending on the strategy used and can help the logistics companies to define their own strategy, considering the characteristics of their customers and products and the available fleet.
Programa Operacional Temático Factores de Competitividade
Funders :
ERDF - European Regional Development Fund [BE] Junta de Comunidades de Castilla-La Mancha [ES] MICINN - Ministerio de Ciencia e Innovacion [ES] FCT - Fundação para a Ciência e a Tecnologia [PT]
Allahviranloo, M., Chow, J.Y., Recker, W.W., Selective vehicle routing problems under uncertainty without recourse. Transp. Res. E 62 (2014), 68–88.
Alvarez, D., Alvarez-Valdes, R., Parreño, F., A grasp algorithm for the container loading problem with multi-drop constraints. Pesqui. Oper. 35 (2015), 1–24.
Alvarez-Valdes, R., Parreño, F., Tamarit, J.M., A GRASP/Path Relinking algorithm for two- and three-dimensional multiple bin-size bin packing problems. Comput. Oper. Res. 40:12 (2013), 3081–3090.
Amaya, J., Delgado-Lindeman, M., Arellana, J., Allen, J., Urban freight logistics: What do citizens perceive?. Transp. Res. E, 152(May), 2021, 102390.
Andrade, C.E., Toso, R.F., Gonçalves, J.F., Resende, M.G., The multi-parent biased random-key genetic algorithm with implicit path-relinking and its real-world applications. European J. Oper. Res. 289:1 (2021), 17–30.
Bean, J.C., Genetic algorithms and random keys for sequencing and optimization. ORSA J. Comput. 6:2 (1994), 154–160.
Berbeglia, G., Cordeau, J.-F., Laporte, G., Dynamic pickup and delivery problems. European J. Oper. Res. 202:1 (2010), 8–15.
Bischoff, E., Ratcliff, M., Issues in the development of approaches to container loading. Omega 23:4 (1995), 377–390.
Bruni, M.E., Guerriero, F., Beraldi, P., Designing robust routes for demand-responsive transport systems. Transp. Res. E 70:1 (2014), 1–16.
Ceschia, S., Schaerf, A., Stützle, T., Local search techniques for a routing-packing problem. Comput. Ind. Eng. 66:4 (2013), 1138–1149.
Chen, H.-K., Hsueh, C.-F., Chang, M.-S., The real-time time-dependent vehicle routing problem. Transp. Res. E 42:5 (2006), 383–408.
Chen, S., Wang, H., Meng, Q., Solving the first-mile ridesharing problem using autonomous vehicles. Comput.-Aided Civ. Infrastruct. Eng. 35:1 (2020), 45–60.
Clausen, J., Larsen, J., Larsen, A., Hansen, J., Disruption management-operations research between planning and execution. OR/MS Today 28:5 (2001), 40–43.
Coffman, E.G. Jr., Garey, M.R., Johnson, D.S., Dynamic bin packing. SIAM J. Comput. 12:2 (1983), 227–258.
Cordeau, J.-F., Laporte, G., Ropke, S., Recent models and algorithms for one-to-one pickup and delivery problems. Golden, B., Raghavan, S., Wasil, E., (eds.) The Vehicle Routing Problem: Latest Advances and New Challenges, 2008, Springer US, Boston, MA, 327–357.
Correcher, J.F., Alvarez-Valdes, R., A biased random-key genetic algorithm for the time-invariant berth allocation and quay crane assignment problem. Expert Syst. Appl. 89 (2017), 112–128.
Cui, J., Zhao, M., Li, X., Parsafard, M., An, S., Reliable design of an integrated supply chain with expedited shipments under disruption risks. Transp. Res. E 95 (2016), 143–163.
Davies, A., Bischoff, E.E., Weight distribution considerations in container loading. European J. Oper. Res. 114:3 (1999), 509–527.
Eglese, R., Zambirinis, S., Disruption management in vehicle routing and scheduling for road freight transport: a review. TOP 26:1 (2018), 1–17.
Fan, T., Pan, Q., Pan, F., Zhou, W., Chen, J., Intelligent logistics integration of internal and external transportation with separation mode. Transp. Res. E, 133, 2020, 101806.
Fattahi, M., Govindan, K., Keyvanshokooh, E., Responsive and resilient supply chain network design under operational and disruption risks with delivery lead-time sensitive customers. Transp. Res. E 101 (2017), 176–200.
Giménez-Palacios, I., First mile. Mendeley Data, V1, 2021, 10.17632/fffg27yx9 m.1.
Ho, S., Szeto, W., Kuo, Y.-H., Leung, J., Petering, M., Tou, T., A survey of dial-a-ride problems: Literature review and recent developments. Transp. Res. B 111 (2018), 395–421.
Hu, X., Sun, L., Knowledge-based modeling for disruption management in urban distribution. Expert Syst. Appl. 39:1 (2012), 906–916.
Iori, M., Martello, S., Routing problems with loading constraints. TOP 18:1 (2010), 4–27.
Ivanov, D., Pavlov, A., Dolgui, A., Pavlov, D., Sokolov, B., Disruption-driven supply chain (re)-planning and performance impact assessment with consideration of pro-active and recovery policies. Transp. Res. E 90 (2016), 7–24.
Jäämaa, L., Kaipia, R., The first mile problem in the circular economy supply chains–Collecting recyclable textiles from consumers. Waste Manage. 141 (2022), 173–182.
Kåresdotter, E., Page, J., Mörtberg, U., Näsström, H., Kalantari, Z., First mile/last mile problems in smart and sustainable cities: A case study in stockholm county. J. Urban Technol., 2022, 1–23.
Karlaftis, M.G., Kepaptsoglou, K., Sambracos, E., Containership routing with time deadlines and simultaneous deliveries and pick-ups. Transp. Res. E 45:1 (2009), 210–221.
Koç, C., Laporte, G., Tükenmez, I., A review of vehicle routing with simultaneous pickup and delivery. Comput. Oper. Res., 122, 2020.
Kucukoglu, I., Dewil, R., Cattrysse, D., The electric vehicle routing problem and its variations: A literature review. Comput. Ind. Eng., 161, 2021, 107650.
Li, H., Chen, J., Wang, F., Bai, M., Ground-vehicle and unmanned-aerial-vehicle routing problems from two-echelon scheme perspective: A review. European J. Oper. Res. 294:3 (2021), 1078–1095.
Masmoudi, M.A., Hosny, M., Demir, E., Genikomsakis, K.N., Cheikhrouhou, N., The dial-a-ride problem with electric vehicles and battery swapping stations. Transp. Res. E 118 (2018), 392–420.
Moghdani, R., Salimifard, K., Demir, E., Benyettou, A., The green vehicle routing problem: A systematic literature review. J. Cleaner Prod., 279, 2021, 123691.
Moura, A., Oliveira, J.F., An integrated approach to the vehicle routing and container loading problems. OR Spectrum 31 (2009), 775–800.
Parajuli, A., Kuzgunkaya, O., Vidyarthi, N., The impact of congestion on protection decisions in supply networks under disruptions. Transp. Res. E, 145, 2021, 102166.
Parragh, S., Doerner, K., Hartl, R., A survey on pickup and delivery problems. J. Betriebswirtsch. 58:1 (2008), 21–51.
Parragh, S., Doerner, K., Hartl, R., A survey on pickup and delivery problems: Part II: Transportation between pickup and delivery locations. J. Betriebswirtsch. 58:2 (2008), 81–117.
Pillac, V., Gendreau, M., Guéret, C., Medaglia, A., A review of dynamic vehicle routing problems. European J. Oper. Res. 225:1 (2013), 1–11.
Pinto, B.Q., Ribeiro, C.C., Rosseti, I., Noronha, T.F., A biased random-key genetic algorithm for routing and wavelength assignment under a sliding scheduled traffic model. J. Global Optim. 77:4 (2020), 949–973.
Pollaris, H., Braekers, K., Caris, A., Janssens, G.K., Limbourg, S., Vehicle routing problems with loading constraints: state-of-the-art and future directions. OR Spectrum 37:2 (2015), 297–330.
Psaraftis, H.N., Wen, M., Kontovas, C.A., Dynamic vehicle routing problems: Three decades and counting. Networks 67:1 (2016), 3–31.
Ramos, A.G., Silva, E., Oliveira, J.F., A new load balance methodology for container loading problem in road transportation. European J. Oper. Res. 266:3 (2018), 1140–1152.
Ruiz, E., Soto-Mendoza, V., Ruiz Barbosa, A.E., Reyes, R., Solving the open vehicle routing problem with capacity and distance constraints with a biased random key genetic algorithm. Comput. Ind. Eng. 133 (2019), 207–219.
Seiden, S.S., On the online bin packing problem. Orejas, F., Spirakis, P.G., van Leeuwen, J., (eds.) Automata, Languages and Programming: 28th International Colloquium, ICALP 2001 Crete, Greece, July 8–12, 2001 Proceedings, 2001, Springer Berlin Heidelberg, Berlin, Heidelberg, 237–248.
Solomon, M.M., Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35:2 (1987), 254–265.
Spliet, R., Gabor, A.F., Dekker, R., The vehicle rescheduling problem. Comput. Oper. Res. 43 (2014), 129–136.
Toth, P., Vigo, D., Vehicle Routing: Problems, Methods, and Applications. 2014, SIAM.
Wang, X., Cao, H., A dynamic vehicle routing problem with backhaul and time window. 2008 IEEE International Conference on Service Operations and Logistics, and Informatics, Vol. 1, 2008, 1256–1261.
Wang, X., Huang, G.Q., When and how to share first-mile parcel collection service. European J. Oper. Res. 288:1 (2021), 153–169.
Wang, X., Ruan, J., Shi, Y., A recovery model for combinational disruptions in logistics delivery: Considering the real-world participators. Int. J. Prod. Econ. 140:1 (2012), 508–520.
Wang, X., Zhao, Z., Survey of the dynamic pickup and delivery problems. Xitong Gongcheng Lilun Yu Shijian/Syst. Eng. Theory Pract. 41:2 (2021), 319–331.
Xiao, Y., Konak, A., The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion. Transp. Res. E 88 (2016), 146–166.
Yu, G., Qi, X., Disruption Management: Framework, Models and Applications. 2004, World Scientific.
Zhang, J., Liu, F., Tang, J., Li, Y., The online integrated order picking and delivery considering Pickers’ learning effects for an O2O community supermarket. Transp. Res. E 123 (2019), 180–199, 10.1016/j.tre.2019.01.013.
Zhang, Z., Tafreshian, A., Masoud, N., Modular transit: Using autonomy and modularity to improve performance in public transportation. Transp. Res. E, 141, 2020, 102033.
Zhen, X., Li, Y., Cai, G.G., Shi, D., Transportation disruption risk management: Business interruption insurance and backup transportation. Transp. Res. E 90 (2016), 51–68.
