A Mathematical Model and Novel Solution Approach Using Column Generation for Optimizing Automated Delivery Systems with Considering Wind Effect

Document Type : Research Paper

Authors

1 h.D. Candidate, Faculty of Industrial and Systems Engineering, Department of Industrial Engineering, Tarbiat Modares University, Tehran, Iran

2 . Professor, Faculty of Industrial and Systems Engineering, Department of Industrial Engineering, Tarbiat Modares University, Tehran, Iran

3 Associate Professor, Faculty of Industrial and Systems Engineering, Department of Socio-economic Systems, Tarbiat Modares University, Tehran, Iran

10.22084/ier.2025.30415.2194

Abstract

Efficient and rapid delivery of goods in last-mile logistics represents a key challenge for e-commerce companies. With advancements in automated delivery system technologies, these systems have emerged as a promising solution to address the challenges of traditional last-mile logistics. Given the environmental and social challenges in this domain, integrating sustainability into logistics planning has evolved from being a discretionary choice to an essential requirement. Automated delivery systems are identified as a potential means to reduce greenhouse gas emissions and improve the sustainability of last-mile logistics. In this study, we propose a mathematical model for a multi-depot, multi-period delivery problem involving automated delivery systems. The model considers the multi-period nature of operations, aiming to optimize the routing of automated delivery vehicles from multiple depots over a one-day or shift-based planning horizon, while accounting for the wind effect. To enhance computational efficiency, the problem is reformulated into a master problem and a pricing subproblem, enabling the use of the column generation algorithm. Subsequently, a dynamic programming algorithm is proposed to reduce the computational time of the pricing subproblem. To evaluate the performance of the proposed algorithm, 120 random instances were generated across 12 different problem sets. A comparison between the proposed method and the CPLEX solver was conducted to assess the efficiency of the proposed approach. The results indicate that the proposed algorithm achieves solutions with an optimality gap of less than 10%, whereas the CPLEX solver fails to deliver solutions with a gap smaller than 60%.

Keywords

Main Subjects

References

  • Coppola, D. J. S. R. F., (2022). Annual retail e-commerce sales growth worldwide from 2017 to 2025, 22, 2022.

https://www.statista.com/statistics/534123/e-commerce-share-of-retail-sales-worldwide/

  • حضرتی، ا.، مصلحی، ق.، رئیسی نافچی، م.، (2021). مسأله‌ یکپارچه‌ی دریافت، تحویل و بازگشت وسایل‌نقلیه با محدودیت‌های بارگذاری سه‌بعدی و پنجره‌ی زمانی نشریه پژوهش‌های مهندسی صنایع در سیستم‌های تولید، 8، 321-345.

 10.22084/ier.2021.3926

  • Boysen, N., Fedtke, S., Schwerdfeger, S. J. O. S., (2021). Last-mile delivery concepts: a survey from an operational research perspective, 43, 1-58.
  • نوروزی، ن.، صادق عمل نیک، م.، توکلی مقدم، ر.، (2017). کاهش انرژی مصرفی و زمان سفر در مساله مسیریابی وسائط نقلیه با در نظر گرفتن سرعت‌های سفر وابسته به زمان توسط الگوریتم رقابت استعماری %J نشریه پژوهش‌های مهندسی صنایع در سیستم‌های تولید، 4، 213-219.

10.22084/ier.2021.3926

  • Dablanc, L., Diziain, D., Levifve, H. J. E. t. r. r., (2011). Urban freight consultations in the Paris region, 3, 47-57.

https://doi.org/10.1007/s12544-011-0049-2

  • Jiang, L., Mahmassani, H. S. J. T. R. R., (2014). City logistics: Freight distribution management with time-dependent travel times and disruptive events, 2410, 85-95.

https://doi.org/10.3141/2410-10

  • Fan, W., Xu, H., Xu, X. J. C.-T. i. j. f. c., electrical, m. i., engineering, e., (2009). Simulation on vehicle routing problems in logistics distribution, 28, 1516-1531.

10.1016/j.trpro.2014.10.026

  • Murray, C. C., Chu, A. G., (2015). The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery, Transportation Research Part C: Emerging Technologies, 54, 86-109.

https://doi.org/10.1016/j.trc.2015.03.005

  • Macrina, G., Di Puglia Pugliese, L., Guerriero, F., Laporte, G., (2020). Drone-aided routing: A literature review, Transportation Research Part C: Emerging Technologies,

https://doi.org/10.1016/j.trc.2020.102762

  • Salama, M., Srinivas, S. J. T. R. P. C. E. T., (2020). Joint optimization of customer location clustering and drone-based routing for last-mile deliveries, Transportation Research Part C: Emerging Technologies, 114, 620-642.

https://doi.org/10.1016/j.trc.2020.01.019

  • Moshref-Javadi, M., Lee, S., Winkenbach, M. J. T. R. P. E. L., Review, T., (2020). Design and evaluation of a multi-trip delivery model with truck and drones, Transportation Research Part E: Logistics and Transportation Review, 136, 101887.

https://doi.org/10.1016/j.tre.2020.101887

  • Lei, D., Chen, X., (2022/09/01/ 2022). An improved variable neighborhood search for parallel drone scheduling traveling salesman problem, Applied Soft Computing, 127, 109416.

https://doi.org/10.1016/j.asoc.2022.109416

  • Chang, Y. S., Lee, H. J., (2018/08/15/ 2018). Optimal delivery routing with wider drone-delivery areas along a shorter truck-route, Expert Systems with Applications, 104, 307-317.

https://doi.org/10.1016/j.eswa.2018.03.032

  • Dorling, K., Heinrichs, J., Messier, G. G., Magierowski, S., (2017). Vehicle Routing Problems for Drone Delivery, IEEE Transactions on Systems, Man, and Cybernetics: Systems, 47, 70-85.

10.1109/TSMC.2016.2582745

  • Cheng, C., Adulyasak, Y., Rousseau, L.-M., (2020). Drone routing with energy function: Formulation and exact algorithm, Transportation Research Part B: Methodological, 139, 364-387.

https://doi.org/10.1016/j.trb.2020.06.011

  • Rabta, B., Wankmüller, C., Reiner, G., (2018). A drone fleet model for last-mile distribution in disaster relief operations, International Journal of Disaster Risk Reduction, 28, 107-112.

https://doi.org/10.1016/j.ijdrr.2018.02.020

  • Chowdhury, S., Shahvari, O., Marufuzzaman, M., Li, X., Bian, L., (2021). Drone routing and optimization for post-disaster inspection, Computers & Industrial Engineering,

https://doi.org/10.1016/j.cie.2021.107495

  • Liu, Y., (2019). An optimization-driven dynamic vehicle routing algorithm for on-demand meal delivery using drones, Computers & Operations Research, 111, 1-20.

https://doi.org/10.1016/j.cor.2019.05.024

  • Sajid, M., Mittal, H., Pare, S., Prasad, M., (2022/09/01/ 2022). Routing and scheduling optimization for UAV assisted delivery system: A hybrid approach, Applied Soft Computing, 126, 109225.

https://doi.org/10.1016/j.asoc.2022.109225

  • Liu, C., Chen, H., Li, X., Liu, Z., (2021/04/01/ 2021). A scheduling decision support model for minimizing the number of drones with dynamic package arrivals and personalized deadlines, Expert Systems with Applications, 167, 114157.

https://doi.org/10.1016/j.eswa.2020.114157

  • Boysen, N., Briskorn, D., Fedtke, S., Schwerdfeger, S. J. N., (2018). Drone delivery from trucks: Drone scheduling for given truck routes, Networks, 72, 506-527.

https://doi.org/10.1002/net.21847

  • Karak, A., Abdelghany, K., (2019). The hybrid vehicle-drone routing problem for pick-up and delivery services, Transportation Research Part C: Emerging Technologies, 102, 427-449.

https://doi.org/10.1016/j.trc.2019.03.021

  • Poikonen, S., Golden, B. J. I. J. o. C., (2020). The mothership and drone routing problem, INFORMS Journal on Computing, 32, 249-262.

https://doi.org/10.1287/ijoc.2018.0879

  • Poikonen, S., Golden, B. J. C., Research, O., (2020). Multi-visit drone routing problem, Computers & Operations Research, 113, 104802.

https://doi.org/10.1016/j.cor.2019.104802

  • Coelho, B. N. et al., (2017). A multi-objective green UAV routing problem, Computers & Operations Research, 88, 306-315.

https://doi.org/10.1016/j.cor.2017.04.011

  • Cokyasar, T. J. P. C. S., (2021). Delivery drone route planning over a battery swapping network, 184, 10-16.

https://doi.org/10.1016/j.procs.2021.03.013

  • Choi, Y., Schonfeld, P. M., "Optimization of multi-package drone deliveries considering battery capacity," in Proceedings of the 96th Annual Meeting of the Transportation Research Board, Washington, DC, USA, 2017, pp. 8-12.

https://trid.trb.org/View/1439294

  • Dhein, G., Zanetti, M. S., de Araújo, O. C. B., Cardoso Jr, G., (2019). Minimizing dispersion in multiple drone routing, Computers & Operations Research, 109, 28-42.

https://doi.org/10.1016/j.cor.2019.04.022

  • Shen, Y., Xu, X., Zou, B., Wang, H., (2020). Operating policies in multi-warehouse drone delivery systems, International Journal of Production Research, 59, 2140-2156.

https://doi.org/10.1080/00207543.2020.1756509

  • Nishira, M., Ito, S., Nishikawa, H., Kong, X., Tomiyama, H., (2023). An Integer Programming Based Approach to Delivery Drone Routing under Load-Dependent Flight Speed, Drones,

https://doi.org/10.3390/drones7050320

  • Radzki, G., Nielsen, I., Golińska-Dawson, P., Bocewicz, G., Banaszak, Z., (2021). Reactive UAV Fleet’s Mission Planning in Highly Dynamic and Unpredictable Environments, Sustainability, 13, 5228.

https://doi.org/10.3390/su13095228

  • Radzki, G., Bocewicz, G., Wikarek, J., Nielsen, P., Banaszak, Z., "Multi Depot UAVs Routing Subject to Changing Weather and Time Windows Variation," in Conference on Automation, 2022, pp. 64-74: Springer.

https://doi.org/10.1007/978-3-031-03502-9_7

Journal of Industrial Engineering Research in Production Systems
Volume 12, Issue 25
March 2025
Pages 121-135

Files

Share

How to cite

Statistics