Mathematical model and hybrid meta-heuristic solution approaches for hub location problem with hybrid drone-airplane delivery mode

Document Type : Research Article

Authors

1 Shiraz University of Technology

2 Faculty of Mathematics, Shiraz University of Technology, Shiraz, Iran

Abstract

This study addresses the integrated hub location and drone delivery problem, an area with few5
prior investigations. We propose a bi-objective integer linear programming model to minimize total cost and total drone route time. A novel three-zone structure allows drone transfers between zones via cargo planes, enhancing realism and complexity. Drone capacities are categorized as light and heavy, improving allocation flexibility. Due to the model’s complexity, several metaheuristic algorithms including Genetic Algorithm, Differential Evolution, Simulated Annealing, and their hybrid versions (SA-GA and SA-DE) are developed and compared. Parameter tuning is performed using the Taguchi method. Computational experiments on various instances show that hybrid algorithms outperform classical methods and scale effectively for larger problems, providing a practical and integrated framework for hub location and drone delivery planning.

Keywords

Main Subjects


[1] M. Abdolhosseinzadeh, M.M. Alipour, A simulated annealing algorithm for the restricted stochas
tic traveling salesman problem with exponentially distributed arc lengths, J. Math. Model. 8(3)
(2020) 279–290.
[2] S. Alumur, B.Y. Kara, Network hub location problems: The state of the art, Eur. J. Oper. Res.
190(1) (2008) 1–21
[3] S.A. Alumur, J.F. Campbell, I. Contreras, B.Y. Kara, V. Marianov, M.E. O’Kelly, Perspectives on
modeling hub location problems, Eur. J. Oper. Res. 291(1) (2021) 1–17.
[4] J.P. Aurambout, K. Gkoumas, B. Ciuffo, Last mile delivery by drones: An estimation of viable
market potential and access to citizens across European cities, Eur. Transp. Res. Rev. 11(1) (2019)
1–21.
[5] G. Baloch, F. Gzara, Strategic network design for parcel delivery with drones under competition,
Transp. Sci. 54(1) (2020) 204–228.
[6] O. Bozorg-Haddad, M. Solgi, H.A. Lo´aiciga, Meta-Heuristic and Evolutionary Algorithms for En
gineering Optimization, John Wiley & Sons, 2017.
[7] L. Budd, S. Ison, Air Transport Management, Routledge, 2017.
[8] J.F. Campbell, Integer programming formulations of discrete hub location problems, Eur. J. Oper.
Res. 72(2) (1994) 387–405.
[9] D. Chauhan, A. Unnikrishnan, M. Figliozzi, Maximum coverage capacitated facility location prob
lem with range constrained drones, Transp. Res. Part C Emerg. Technol. 99 (2019) 1–18.
[10] A.P. Chobar, H. Bigdeli, N. Shamami, M. Abolghasemian, Optimizing hub location for military
equipment: A robust mathematical model for uncertainty and meta-heuristic approaches, Fuzzy
Optim. Model. J. 5(4) (2024) 44–59.
[11] S. Chowdhury, A. Emelogu, M. Marufuzzaman, S.G. Nurre, L. Bian, Drones for disaster response
and relief operations: A continuous approximation model, Int. J. Prod. Econ. 188 (2017) 167–184.
[12] B.N. Coelho, V.N. Coelho, I.M. Coelho, L.S. Ochi, R. Haghnazar, D. Zuidema, M.S.F. Lima, A.R.
da Costa, A multi-objective green UAV routing problem, Comput. Oper. Res. 88 (2017) 306–315.
[13] I. Contreras, M. O’Kelly, Hub location problems, Loc. Sci. (2019) 327–363.
[14] K. Dorling, J. Heinrichs, G.G. Messier, S. Magierowski, Vehicle routing problems for drone deliv
ery, IEEE Trans. Syst. Man Cybern. Syst. 47(1) (2016) 70–85.
[15] A.T. Ernst, M. Krishnamoorthy, Efficient algorithms for the uncapacitated single allocation p-hub
median problem, Loc. Sci. 4(3) (1996) 139–154.
[16] A.T. Ernst, M. Krishnamoorthy, Exact and heuristic algorithms for the uncapacitated multiple
allocation p-hub median problem, Eur. J. Oper. Res. 104(1) (1998) 100–112.
[17] F. Farajzadeh, A. Moadab, O.F. Valilai, M. Houshmand, A novel mathematical model for a
cloud-based drone enabled vehicle routing problem considering multi-echelon supply chain, IFAC
PapersOnLine 53(2) (2020) 15035–15040.
[18] H. Garg, A hybrid GSA-GA algorithm for constrained optimization problems, Inf. Sci. 478 (2019)
499–523
[19] S. Gelareh, S. Nickel, Hub location problems in transportation networks, Transp. Res. Part E Lo
gist. Transp. Rev. 47(6) (2011) 1092–1111.
[20] M. Golabi, S.M. Shavarani, G. Izbirak, An edge-based stochastic facility location problem in UAV
supported humanitarian relief logistics: a case study of Tehran earthquake, Nat. Hazards 87 (2017)
1545–1565.
[21] Q.M.Ha, Y.Deville, Q.D. Pham, M.H.H`a, Onthe min-cost traveling salesman problem with drone,
Transp. Res. Part C Emerg. Technol. 86 (2018) 597–621.
[22] M.Hajiaghaei-Keshteli, G. Rahmanifar, M. Mohammadi, F. Gholian-Jouybari, J.J. Klemeˇs, S. Zah
matkesh, A. Bokhari, G. Fusco, C. Colombaroni, Designing a multi-period dynamic electric vehicle
production-routing problem in a supply chain considering energy consumption, J. Clean. Prod. 421
(2023) 138471.
[23] J.H. Holland, Adaptation in Natural and Artificial Systems: An Introductory Analysis with Appli
cations to Biology, Control, and Artificial Intelligence, Michigan Press, 1975.
[24] H. Huang, A.V. Savkin, C. Huang, A new parcel delivery system with drones and a public train, J.
Intell. Robot. Syst. 100 (2020a) 1341–1354.
[25] H. Huang, A.V. Savkin, C. Huang, Round trip routing for energy-efficient drone delivery based on
a public transportation network, IEEE Trans. Transp. Electrific. 6(3) (2020b) 1368–1376.
[26] M. Imanparast, V. Kiani, A practical heuristic for maximum coverage in large-scale continuous
location problem, J. Math. Model. 9(4) (2021) 555–572.
[27] B.Y. Kara, Modeling and analysis of issues in hub location problem, Ph.D. Thesis, Bilkent Univer
sity, Turkey, 1999.
[28] A. Khaleghi, A. Eydi, Hybrid solution methods for a continuous-time multi-period hub location
problem with time-dependent demand and sustainability considerations, J. Ambient Intell. Hu
maniz. Comput. 15(1) (2024) 115–155.
[29] M. Khalilzadeh, M. Ahmadi, O. Kebriyaii, A bi-objective mathematical programming model
for a maximal covering hub location problem under uncertainty, SAGE Open 15(1) (2025)
21582440251324335.
[30] S. Kirkpatrick, C.D. Gelatt Jr., M.P. Vecchi, Optimization by simulated annealing, Sci. 220(4598)
(1983) 671–680.
[31] G. Laporte, S. Nickel, F. Saldanha-da-Gama, Introduction to Location Science, Springer, 2019.
[32] Y. Liu, An optimization-driven dynamic vehicle routing algorithm for on-demand meal delivery
using drones, Comput. Oper. Res. 111 (2019) 1–20.
[33] J.E. Macias, P. Angeloudis, W. Ochieng, Optimal hub selection for rapid medical deliveries using
unmanned aerial vehicles, Transp. Res. Part C Emerg. Technol. 110 (2020) 56–80
[34] G. Macrina, L.D.P. Pugliese, F. Guerriero, G. Laporte, Drone-aided routing: A literature review,
Transp. Res. Part C Emerg. Technol. 120 (2020) 102762.
[35] A.I. Mahmutogullari, B.Y. Kara, Hub location under competition, Eur. J. Oper. Res. 250(1) (2016)
214–225.
[36] T. Meyer, A.T. Ernst, M. Krishnamoorthy, A 2-phase algorithm for solving the single allocation
p-hub center problem, Comput. Oper. Res. 36(12) (2009) 3143–3151.
[37] J. Minas, L. Mitten, The hub operation scheduling problem, Oper. Res. 6(3) (1958) 329–345.
[38] C.C. Murray, A.G. Chu, The flying sidekick traveling salesman problem: Optimization of drone
assisted parcel delivery, Transp. Res. Part C Emerg. Technol. 54 (2015) 86–109.
[39] M.E. O’Kelly, A quadratic integer program for the location of interacting hub facilities, Eur. J.
Oper. Res. 32(3) (1987) 393–404.
[40] H. Omagari, S.I. Higashino, Provisional-ideal-point-based multi-objective optimization method for
drone delivery problem, Int. J. Aeronaut. Space Sci. 19 (2018) 262–277.
[41] C. Ortiz-Astorquiza, I. Contreras, G. Laporte, Multi-level facility location as the maximization of a
submodular set function, Eur. J. Oper. Res. 247(3) (2015) 1013–1016.
[42] D. Pamucar, D. Lazarevi´c, M. Dobrodolac, V. Simic, ¨ O.F. G¨ orc¸¨ un, Prioritization of crowdsourcing
models for last-mile delivery using fuzzy Sugeno–Weber framework, Eng. Appl. Artif. Intell. 128
(2024) 107414.
[43] S. Poikonen, X. Wang, B. Golden, The vehicle routing problem with drones: Extended models and
connections, Netw. 70(1) (2017) 34–43.
[44] I. Rodr´ ıguez-Mart´ ın, J.J. Salazar-Gonz´alez, H. Yaman, A branch-and-cut algorithm for the hub
location and routing problem, Comput. Oper. Res. 50 (2014) 161–174.
[45] B. Rostami, N. K¨ammerling, J. Naoum-Sawaya, C. Buchheim, U. Clausen, Stochastic single
allocation hub location, Eur. J. Oper. Res. 289(3) (2021) 1087–1106.
[46] M.R. Salama, S. Srinivas, Collaborative truck multi-drone routing and scheduling problem: Pack
age delivery with flexible launch and recovery sites, Transp. Res. Part E Logist. Transp. Rev. 164
(2022) 102788.
[47] E. Shadkam, Parameter setting of meta-heuristic algorithms: a new hybrid method based on DEA
and RSM, Environ. Sci. Pollut. Res. 29(15) (2022) 22404–22426.
[48] E. Shadkam, S. Safari, S.S. Abdollahzadeh, Finally, which meta-heuristic algorithm is the best
one?, Int. J. Decis. Sci. Risk Manag. 10(1-2) (2021) 32–50.
[49] D. Skorin-Kapov, J. Skorin-Kapov, M. O’Kelly, Tight linear programming relaxations of uncapac
itated p-hub median problems, Eur. J. Oper. Res. 94(3) (1996) 582–593
[50] B. Soylu, H. Katip, A multiobjective hub-airport location problem for an airline network design,
Eur. J. Oper. Res. 277(2) (2019) 412–425.
[51] R. Storn, K. Price, Differential evolution—a simple and efficient heuristic for global optimization
over continuous spaces, J. Glob. Optim. 11(4) (1997) 341–359.
[52] G. Taguchi, Introduction to Quality Engineering: Designing Quality into Products and Processes,
Asian Productivity Organization, Tokyo, 1986.
[53] Y. Tanabe, Y. Kitagawa, An adaptive selection system of base-isolation devices evaluated by using
a soft computing method that considers seismic performance, 13th World Conf. Earthquake Eng.,
Vancouver, B.C., Canada, 2004.
[54] M. Tavana, K. Khalili-Damghani, F.J. Santos-Arteaga, M.H. Zandi, Drone shipping versus truck
delivery in a cross-docking system with multiple fleets and products, Expert Syst. Appl. 72 (2017)
93–107.
[55] A.Troudi, S.A. Addouche, S. Dellagi, A. E. Mhamedi, Sizing of the drone delivery fleet considering
energy autonomy, Sustainability 10(9) (2018) 3344.
[56] B. Urazel, Y. B. Sahin, Solving a cubic cell formation problem with quality index using a hybrid
meta-heuristic approach, Gazi Univ. J. Sci. 36(2) (2023) 752–771.
[57] X. Wang, S. Poikonen, B. Golden, The vehicle routing problem with drones: several worst-case
results, Optim. Lett. 11 (2017) 679–697.
[58] Z. Wang, J. B. Sheu, Vehicle routing problem with drones, Transp. Res. Part B Methodol. 122
(2019) 350–364.
[59] G. Wu, N. Mao, Q. Luo, B. Xu, J. Shi, P N. Suganthan, Collaborative truck-drone routing for
contactless parcel delivery during the epidemic, IEEE Trans. Intell. Transp. Syst. 23(12) (2022)
25077–25091.
[60] Y. Yadav, A. Narasimhamurthy, Algorithms for solving the vehicle routing problem with drones,
Proc. 2017 Ninth Int. Conf. Adv. Pattern Recognit. (ICAPR), 2017.
[61] M. Ziaee, M. Imanparast, V. Khodabakhshi, Multi-agent single machine scheduling problem with
transportation constraints, J. Math. Model. 10(3) (2022) 367–385