A stochastic-fuzzy multi-objective model for the last-mile delivery problem using drones and ground vehicles, a case study

Document Type : Article

Authors

1 School of Industrial and Systems Engineering, College of Engineering, University of Tehran, Tehran, Iran

2 - School of Industrial and Systems Engineering, College of Engineering, University of Tehran, Tehran, Iran - School of Industrial Engineering, K. N. Toosi University of Technology (KNTU), Tehran, Iran

Abstract

Drone delivery as a novel approach for parcel delivery has been under the focus of many scholars and practitioners. In this regard, this paper introduces a stochastic-fuzzy multi-objective optimization model for designing a last-mile delivery system with drones and ground vehicles. The first two objective functions aim to minimize the detrimental effects of the delivery system on the environment and the total costs. The last objective function maximized the system's reliability by considering the breakdown probability of both drones and ground vehicles. Then, AUGMECON2 is utilized as an exact method to solve the proposed model. besides determining the number of required drones and ground vehicles, the model indicates locations and capacities of facilities where vehicles start their one-to-one trips to meet the customer demands. The proposed model is then validated by applying it to a real case study of an e-commerce company in Karaj, Iran. The findings suggest that the system's total cost rises when the reliability increases and the environmental impacts decrease. Furthermore, when both drones and ground vehicles are considered for meeting the customer demands, the delivery system functions better in terms of costs, environmental impacts, and reliability than when only one mode of delivery is considered.

Keywords

References

References:

[1] Boysen, N., Fedtke, S. and Schwerdfeger, S. “Last-mile delivery concepts: a survey from an operational research perspective,” OR Spectrum, Sep. 2020, doi: 10.1007/s00291-020-00607-8.
[2] Karaca, Y., Cicek, M., Tatli, O., et al. “The potential use of unmanned aircraft systems (drones) in mountain search and rescue operations,” The American Journal of Emergency Medicine, vol. 36, no. 4, pp. 583–588, Apr. 2018, doi: 10.1016/j.ajem.2017.09.025.
[3] Pulver, A. and Wei, R. “Optimizing the spatial location of medical drones,” Applied Geography, vol. 90, pp. 9–16, Jan. 2018, doi: 10.1016/j.apgeog.2017.11.009.
[4] Rabta, B., Wankmüller, C. and Reiner, G. “A drone fleet model for last-mile distribution in disaster relief operations,” International Journal of Disaster Risk Reduction, vol. 28, pp. 107–112, Jun. 2018, doi: 10.1016/j.ijdrr.2018.02.020.
[5] Thiels, C.A., Aho, J.M., Zietlow, S.P., et al. “Use of Unmanned Aerial Vehicles for Medical Product Transport,” Air Medical Journal, vol. 34, no. 2, pp. 104–108, Mar. 2015, doi: 10.1016/j.amj.2014.10.011.
[6] Dorling, K., Heinrichs, J., Messier, G.G., et al. “Vehicle Routing Problems for Drone Delivery,” IEEE Trans. Syst. Man Cybern, Syst., vol. 47, no. 1, pp. 70–85, Jan. 2017, doi: 10.1109/TSMC.2016.2582745.
[7] Gong, D.-C., Chen, P.-S. and Lu, T.-Y. “Multi-Objective Optimization of Green Supply Chain Network Designs for Transportation Mode Selection,” Scientia Iranica, vol. 0, no. 0, pp. 0–0, Sep. 2017, doi: 10.24200/sci.2017.4403.
[8] Mohtashami, Z., Aghsami, A. and Jolai, F. “A green closed loop supply chain design using queuing system for reducing environmental impact and energy consumption,” Journal of Cleaner Production, vol. 242, Jan 2020, doi: https://doi.org/10.1016/j.jclepro.2019.118452.
[9] Figliozzi, M.A. “Lifecycle modeling and assessment of unmanned aerial vehicles (Drones) CO 2 e emissions,” Transportation Research Part D: Transport and Environment, vol. 57, pp. 251–261, Dec. 2017, doi: 10.1016/j.trd.2017.09.011.
[10] Park, J., Kim, S. and Suh, K. “A Comparative Analysis of the Environmental Benefits of Drone-Based Delivery Services in Urban and Rural Areas,” Sustainability, vol. 10, no. 3, p. 888, Mar. 2018, doi: 10.3390/su10030888.
[11] Chiang, W.-C., Li, Y., Shang, J., et al. “Impact of drone delivery on sustainability and cost: Realizing the UAV potential through vehicle routing optimization,” Applied Energy, vol. 242, pp. 1164–1175, May 2019, doi: 10.1016/j.apenergy.2019.03.117.
[12] Chung, S.H., Sah, B. and Lee, J. “Optimization for drone and drone-truck combined operations: A review of the state of the art and future directions,” Computers & Operations Research, vol. 123, p. 105004, Nov. 2020, doi: 10.1016/j.cor.2020.105004.
[13] Iranian tech minister posts video-tweet of Iran Post drone delivery trial, bne IntelliNews, December 15, 2019, accessed January 28, 2021, https://www.intellinews.com.
[12] Delivery of goods by UAV; Efforts made and challenges ahead, DigikalaMAG, December 12, 2019, accessed January 28, 2021, https://www.digikala.com/mag.
[15] Otto, A., Agatz, N., Campbell, J., et al. “Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey,” NETWORKS, vol. 72, no. 4, pp. 411–458, Dec. 2018, doi: 10.1002/net.21818.
[16] Rojas Viloria, D., Solano‐Charris, E.L., Muñoz‐Villamizar, A., et al. “Unmanned aerial vehicles/drones in vehicle routing problems: a literature review,” Intl. Trans. in Op. Res., p. itor.12783, Mar. 2020, doi: 10.1111/itor.12783.
[17] Macrina, G., Di Puglia Pugliese, L., Guerriero, F., et al. “Drone-aided routing: A literature review,” Transportation Research Part C: Emerging Technologies, vol. 120, p. 102762, Nov. 2020, doi: 10.1016/j.trc.2020.102762.
[18] Sundar, K. and Rathinam, S. “Algorithms for Routing an Unmanned Aerial Vehicle in the Presence of Refueling Depots,” IEEE Trans. Automat. Sci. Eng., vol. 11, no. 1, pp. 287–294, Jan. 2014, doi: 10.1109/TASE.2013.2279544.
[19] Kim, S.J., Lim, G.J. and Cho, J. “Drone flight scheduling under uncertainty on battery duration and air temperature,” Computers & Industrial Engineering, vol. 117, pp. 291–302, Mar. 2018, doi: 10.1016/j.cie.2018.02.005.
[20] Murray, C.C. and Chu, A.G. “The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery,” Transportation Research Part C: Emerging Technologies, vol. 54, pp. 86–109, May 2015, doi: 10.1016/j.trc.2015.03.005.
[21] Ha, Q.M., Deville, Y., Pham, Q.D., et al. “On the min-cost Traveling Salesman Problem with Drone,” Transportation Research Part C: Emerging Technologies, vol. 86, pp. 597–621, Jan. 2018, doi: 10.1016/j.trc.2017.11.015.
[22] Agatz, N., Bouman, P. and Schmidt, M. “Optimization Approaches for the Traveling Salesman Problem with Drone,” Transportation Science, p. 18, 2018.
[23] Schermer, D., Moeini, M. and Wendt, O. “The Traveling Salesman Drone Station Location Problem,” in Optimization of Complex Systems: Theory, Models, Algorithms and Applications, vol. 991, H. A. Le Thi, H. M. Le, and T. Pham Dinh, Eds. Cham: Springer International Publishing, 2020, pp. 1129–1138.
[24] Murray, C.C. and Raj, R. “The multiple flying sidekicks traveling salesman problem: Parcel delivery with multiple drones,” Transportation Research Part C: Emerging Technologies, vol. 110, pp. 368–398, Jan. 2020, doi: 10.1016/j.trc.2019.11.003.
[25] Carlsson, J.G. and Song, S. “Coordinated Logistics with a Truck and a Drone,” Management Science, vol. 64, no. 9, pp. 4052–4069, Sep. 2018, doi: 10.1287/mnsc.2017.2824.
[26] Moshref-Javadi, M., Hemmati, A. and Winkenbach, M. “A truck and drones model for last-mile delivery: A mathematical model and heuristic approach,” Applied Mathematical Modelling, vol. 80, pp. 290–318, Apr. 2020, doi: 10.1016/j.apm.2019.11.020.
[27] Moshref-Javadi, M., Lee, S. and Winkenbach, M. “Design and evaluation of a multi-trip delivery model with truck and drones,” Transportation Research Part E: Logistics and Transportation Review, vol. 136, p. 101887, Apr. 2020, doi: 10.1016/j.tre.2020.101887.
[28] Salama, M. and Srinivas, S. “Joint optimization of customer location clustering and drone-based routing for last-mile deliveries,” Transportation Research Part C: Emerging Technologies, vol. 114, pp. 620–642, May 2020, doi: 10.1016/j.trc.2020.01.019.
[29] Kitjacharoenchai, P., Min, B.-C. and Lee, S. “Two echelon vehicle routing problem with drones in last mile delivery,” International Journal of Production Economics, vol. 225, p. 107598, Jul. 2020, doi: 10.1016/j.ijpe.2019.107598.
[30] Shavarani, S.M., Golabi, M. and Izbirak, G. “A capacitated biobjective location problem with uniformly distributed demands in the UAV‐supported delivery operation,” Intl. Trans. in Op. Res., p. itor.12735, Oct. 2019, doi: 10.1111/itor.12735.
[31] Golabi, M., Shavarani, S.M. and Izbirak, G. “An edge-based stochastic facility location problem in UAV-supported humanitarian relief logistics: a case study of Tehran earthquake,” Nat Hazards, p. 21, 2017.
[32] Shavarani, S.M., Mosallaeipour, S., Golabi, M., et al. “A congested capacitated multi-level fuzzy facility location problem: An efficient drone delivery system,” Computers & Operations Research, vol. 108, pp. 57–68, Aug. 2019, doi: 10.1016/j.cor.2019.04.001.
[33] Hong, I., Kuby, M. and Murray, A.T. “A range-restricted recharging station coverage model for drone delivery service planning,” Transportation Research Part C: Emerging Technologies, vol. 90, pp. 198–212, May 2018, doi: 10.1016/j.trc.2018.02.017.
[34] Kim, S.J., Lim, G.J., Cho, J., et al. “Drone-Aided Healthcare Services for Patients with Chronic Diseases in Rural Areas,” J Intell Robot Syst, p. 18, 2017.
[35] Dukkanci, O., Kara, B.Y. and Bektaş, T. “Minimizing energy and cost in range-limited drone deliveries with speed optimization”, Transportation Research Part C: Emerging Technologies, vol. 125, Apr. 2021, doi: 10.1016/j.trc.2021.102985.
[36] Chauhan, D., Unnikrishnan, A. and Figliozzi, M. “Maximum coverage capacitated facility location problem with range constrained drones,” Transportation Research Part C: Emerging Technologies, vol. 99, pp. 1–18, Feb. 2019, doi: 10.1016/j.trc.2018.12.001.
[37] Chauhan, D.R., Unnikrishnan, A., Figliozzi, M., et al. “Robust Maximum Coverage Facility Location Problem with Drones Considering Uncertainties in Battery Availability and Consumption,” Transportation Research Record, Dec. 2020, doi: 10.1177/0361198120968094.
[38] Kim, D., Lee, K. and Moon, I. “Stochastic facility location model for drones considering uncertain flight distance,” Annals of Operations Research, p. 20, 2019.
[39] Chen, H., Hu, Z. and Solak, S. “Improved delivery policies for future drone-based delivery systems,” European Journal of Operational Research, vol. 294, no. 3, pp.1181-1201, Nov. 2021, doi: 10.1016/j.ejor.2021.02.039
[40] Rohaninejad, M., Sahraeian, R. and Tavakkoli-Moghaddam, R. “An accelerated Benders decomposition algorithm for reliable facility location problems in multi-echelon networks,” Computers & Industrial Engineering, vol. 124, pp. 523–534, Oct. 2018, doi: 10.1016/j.cie.2018.07.047.
[41] Korani, E., Eydi, A. and Nakhai Kamalabadi, I. “Reliable Hierarchical Multimodal Hub Location Problem: Models and Lagrangian Relaxation Algorithm,” Scientia Iranica, vol. 27, no. 3, pp. 1525–1543, May. 2020, doi: 10.24200/sci.2018.50797.1870.
[42] Afify, B., Ray, S., Soeanu, A., et al. “Evolutionary learning algorithm for reliable facility location under disruption,” Expert Systems with Applications, vol. 115, pp. 223–244, Jan. 2019, doi: 10.1016/j.eswa.2018.07.045.
[43] Rabbani, M., Aghamohammadi Bosjin, S., Yazdanparast, R., et al. “A stochastic time-dependent green capacitated vehicle routing and scheduling problem with time window, resiliency and reliability: a case study,” 10.5267/j.dsl, pp. 381–394, 2018, doi: 10.5267/j.dsl.2018.2.002.
[44] Amini, A. and Tavakkoli-Moghaddam, R. “A bi-objective truck scheduling problem in a cross-docking center with probability of breakdown for trucks,” Computers & Industrial Engineering, vol. 96, pp. 180–191, Jun. 2016, doi: 10.1016/j.cie.2016.03.023.
[45] Mousazadeh, M., Torabi, S.A. and Zahiri, B. “A robust possibilistic programming approach for pharmaceutical supply chain network design,” Computers & Chemical Engineering, vol. 82, pp. 115–128, Nov. 2015, doi: 10.1016/j.compchemeng.2015.06.008.
[46] Gitinavard, H., Ghodsypour, S.H. and Akbarpour Shirazi, M. “A bi-objective multi-echelon supply chain model with Pareto optimal points evaluation for perishable products under uncertainty,” Scientia Iranica, vol. 0, no. 0, pp. 0–0, Jul. 2018, doi: 10.24200/sci.2018.5047.1060.
[47] Pourmohammadi, F., Teimoury, E. and Gholamian, M.R. “A fuzzy chance-constrained programming model for integrated planning of the wheat supply chain considering wheat quality and sleep period: a case study,” Scientia Iranica, vol. 0, no. 0, pp. 0–0, Oct. 2020, doi: 0.24200/sci.2020.53772.3404.
[48] Pishvaee, M.S., Razmi, J. and Torabi, S.A. “Robust possibilistic programming for socially responsible supply chain network design: A new approach,” Fuzzy Sets and Systems, vol. 206, pp. 1–20, Nov. 2012, doi: 10.1016/j.fss.2012.04.010.
[49] Charnes, A. and Cooper, W.W. “Chance-Constrained Programming,” Management Science, vol. 6, no. 1, pp. 73–79, Oct. 1959, doi: 10.1287/mnsc.6.1.73.
[50] Nourzadeh, F., Ebrahimnejad, S., Khalili-Damghani, K., et al. “Chance constrained programming and robust optimization approaches for uncertain hub location problem in a cooperative competitive environment,” Scientia Iranica, vol. 0, no. 0, pp. 0–0, Sep. 2020, doi: 10.24200/sci.2020.54072.3573.
[51] Shen, J. “An e-commerce facility location problem under uncertainty,” Scientia Iranica, vol. 0, no. 0, pp. 0–0, May 2019, doi: 10.24200/sci.2019.50437.1692.
[52] Shaw, K., Irfan, M., Shankar, R., et al. “Low carbon chance constrained supply chain network design problem: a Benders decomposition based approach,” Computers & Industrial Engineering, vol. 98, pp. 483–497, Aug. 2016, doi: 10.1016/j.cie.2016.06.011.
[53] Mavrotas, G. “Effective implementation of the ε-constraint method in Multi-Objective Mathematical Programming problems,” Applied Mathematics and Computation, vol. 213, no. 2, pp. 455–465, Jul. 2009, doi: 10.1016/j.amc.2009.03.037.
[54] Mavrotas, G. and Florios, K. “An improved version of the augmented ε-constraint method (AUGMECON2) for finding the exact pareto set in multi-objective integer programming problems,” Applied Mathematics and Computation, vol. 219, no. 18, pp. 9652–9669, May 2013, doi: 10.1016/j.amc.2013.03.002.
[55] Asefi, H., Shahparvari, S., Chhetri, P., et al. “Variable fleet size and mix VRP with fleet heterogeneity in Integrated Solid Waste Management,” Journal of Cleaner Production, vol. 230, pp. 1376–1395, Sep. 2019, doi: 10.1016/j.jclepro.2019.04.250.
[56] Digikala Indices, 2020, available: discopp.com/Digikala_statistics98.
[57] Shafiee Moghadam, S., Aghsami, A. and Rabbani, M. “A hybrid NSGA-II algorithm for the closed-loop supply chain network design in e-commerce,” RAIRO-Operations Research, vol. 55, no. 3, pp. 1643-1674, June 2021, doi: 10.1051/ro/2021068.
[58] Digikala open data mining program, available: https://www.digikala.com/opendata/
[59] Ochieng, W.O. “Uncrewed aircraft systems versus motorcycles to deliver laboratory samples in west Africa: a comparative economic study,” vol. 8, p. 9, 2020.
[60] Aghsami, A. and Jolai, F. “Equilibrium threshold strategies and social benefits in the fully observable Markovian queues with partial breakdowns and interruptible setup/closedown policy,” Quality Technology & Quantitative Management, vol 17, no. 6, pp. 685-722, Mar 2020, doi: 10.1080/16843703.2020.1736365.
Scientia Iranica

Articles in Press, Accepted Manuscript
Available Online from 11 May 2022

Files

Share

How to cite

Statistics