The vehicle routing problem (VRP) is a highly significant and extensively studied issue in post-disaster rescue. In recent years, there has been widespread utilization of helicopters for post-disaster rescue. However, efficiently dispatching helicopters to reach rescue sites in post-disaster rescue is a challenge. To address this issue, this study models the issue of dispatching helicopters as a specific variant of the VRP with time window (VRPTW). Considering that the VRPTW is an NP-hard problem, the genetic algorithm (GA) as one of the prominent evolutionary algorithms with robust optimization capabilities, is a good candidate to deal with this issue. In this study, an improved GA with a local search strategy and global search strategy is proposed. To begin, a cooperative initialization strategy is proposed to generate an initial population with high quality and diversity. Subsequently, a local search strategy is presented to improve the exploitation ability. Additionally, a global search strategy is embedded to enhance the global search performance. Finally, 56 instances extended from Solomon instances are utilized for conducting simulation tests. The simulation results indicate that the average relative percentage increase (RPI) of the distance travelled by helicopters as obtained by the proposed algorithm is 0.178, 0.027, 0.075 and 0.041 times smaller than the average RPIs obtained by the tabu search algorithm, ant colony optimization algorithm, hybrid GA and simulated annealing algorithm, respectively. Simulation results reveal that the proposed algorithm is more efficient and effective for solving the VRPTW to reduce the driving distance of the helicopters in post-disaster rescue.
Citation: Kaidong Yang, Peng Duan, Huishan Yu. An improved genetic algorithm for solving the helicopter routing problem with time window in post-disaster rescue[J]. Mathematical Biosciences and Engineering, 2023, 20(9): 15672-15707. doi: 10.3934/mbe.2023699
The vehicle routing problem (VRP) is a highly significant and extensively studied issue in post-disaster rescue. In recent years, there has been widespread utilization of helicopters for post-disaster rescue. However, efficiently dispatching helicopters to reach rescue sites in post-disaster rescue is a challenge. To address this issue, this study models the issue of dispatching helicopters as a specific variant of the VRP with time window (VRPTW). Considering that the VRPTW is an NP-hard problem, the genetic algorithm (GA) as one of the prominent evolutionary algorithms with robust optimization capabilities, is a good candidate to deal with this issue. In this study, an improved GA with a local search strategy and global search strategy is proposed. To begin, a cooperative initialization strategy is proposed to generate an initial population with high quality and diversity. Subsequently, a local search strategy is presented to improve the exploitation ability. Additionally, a global search strategy is embedded to enhance the global search performance. Finally, 56 instances extended from Solomon instances are utilized for conducting simulation tests. The simulation results indicate that the average relative percentage increase (RPI) of the distance travelled by helicopters as obtained by the proposed algorithm is 0.178, 0.027, 0.075 and 0.041 times smaller than the average RPIs obtained by the tabu search algorithm, ant colony optimization algorithm, hybrid GA and simulated annealing algorithm, respectively. Simulation results reveal that the proposed algorithm is more efficient and effective for solving the VRPTW to reduce the driving distance of the helicopters in post-disaster rescue.
| [1] |
F. Wex, G. Schryen, S. Feuerriegel, D. Neumann, Emergency response in natural disaster management: allocation and scheduling of rescue units, Eur. J. Oper. Res., 235 (2014), 697–708. https://doi.org/10.1016/j.ejor.2013.10.029 doi: 10.1016/j.ejor.2013.10.029
|
| [2] |
G. Tian, A. M. Fathollahi-Fard, Y. Ren, Z. Li, X. Jiang, Multi-objective scheduling of priority-based rescue vehicles to extinguish forest fires using a multi-objective discrete gravitational search algorithm, Inf. Sci., 608 (2022), 578–596. https://doi.org/10.1016/j.ins.2022.06.052 doi: 10.1016/j.ins.2022.06.052
|
| [3] |
Z. Mahtab, A. Azeem, S. M. Ali, S. K. Paul, A. M. Fathollahi-Fard, Multi-objective robust-stochastic optimisation of relief goods distribution under uncertainty: a real-life case study, Int. J. Syst. Sci. Oper. Logist., 9 (2022), 241–262. https://doi.org/10.1080/23302674.2021.1879305 doi: 10.1080/23302674.2021.1879305
|
| [4] |
Y. Okuno, K. Kobayashi, H. Ishii, Development of a helicopter operations management system for disaster relief missions, J. Am. Helicopter Soc., 61 (2016), 1–9. https://doi.org/10.4050/JAHS.61.012006 doi: 10.4050/JAHS.61.012006
|
| [5] |
A. Andreeva-Mori, K. Kobayashi, M. Shindo, Particle swarm optimization/greedy-search algorithm for helicopter mission assignment in disaster relief, J. Aerosp. Inf. Syst., 12 (2015), 646–660. https://doi.org/10.2514/1.I010362 doi: 10.2514/1.I010362
|
| [6] |
Q. Shao, C. Xu, Y. Zhu, Multi-helicopter search and rescue route planning based on strategy optimization algorithm, Int. J. Pattern Recognit Artif Intell., 33 (2019), 1950002. https://doi.org/10.1142/S0218001419500022 doi: 10.1142/S0218001419500022
|
| [7] |
J. Zhang, Y. Zhu, X. Li, M. Ming, W. Wang, T. Wang, Multi-trip time-dependent vehicle routing problem with split delivery, Mathematics, 10 (2022), 3527. https://doi.org/10.3390/math10193527 doi: 10.3390/math10193527
|
| [8] |
W. VanDeventer, E. Jamei, G. S. Thirunavukkarasu, M. Seyedmahmoudian, T. K. Soon, B. Horan, et al., Short-term PV power forecasting using hybrid GASVM technique, Renewable Energy, 140 (2019), 367–379. https://doi.org/10.1016/j.renene.2019.02.087 doi: 10.1016/j.renene.2019.02.087
|
| [9] |
S. B. Jouida, S. Krichen, A genetic algorithm for supplier selection problem under collaboration opportunities, J. Exp. Theor. Artif. Intell., 34 (2022), 53–79. https://doi.org/10.1080/0952813X.2020.1836031 doi: 10.1080/0952813X.2020.1836031
|
| [10] |
L. Meng, W. Cheng, B. Zhang, W. Zou, W. Feng, P. Duan, An improved genetic algorithm for solving the multi-AGV flexible job shop scheduling problem, Sensors, 23 (2023), 3815. https://doi.org/10.3390/s23083815 doi: 10.3390/s23083815
|
| [11] |
J. Ochelska-Mierzejewska, A. Poniszewska-Marańda, W. Marańda, Selected genetic algorithms for vehicle routing problem solving, Electronics, 10 (2021), 3147. https://doi.org/10.3390/electronics10243147 doi: 10.3390/electronics10243147
|
| [12] |
H. Park, D. Son, B. Koo, B. Jeong, Waiting strategy for the vehicle routing problem with simultaneous pickup and delivery using genetic algorithm, Expert Syst. Appl., 165 (2021), 113959. https://doi.org/10.1016/j.eswa.2020.113959 doi: 10.1016/j.eswa.2020.113959
|
| [13] |
M. A. Mohammed, M. K. A. Ghani, R. I. Hamed, S. Mostafa, M. S. Ahmad, D. A. Ibrahim, Solving vehicle routing problem by using improved genetic algorithm for optimal solution, J. Comput. Sci., 21 (2017), 255–262. https://doi.org/10.1016/j.jocs.2017.04.003 doi: 10.1016/j.jocs.2017.04.003
|
| [14] |
G. B. Dantzig, J. H. Ramser, The truck dispatching problem, Manage. Sci., 6 (1959), 80–91. https://doi.org/10.1287/mnsc.6.1.80 doi: 10.1287/mnsc.6.1.80
|
| [15] |
A. M. Fathollahi-Fard, A. Ahmadi, B. Karimi, Sustainable and robust home healthcare logistics: a response to the COVID-19 pandemic, Symmetry, 14 (2022), 193. https://doi.org/10.3390/sym14020193 doi: 10.3390/sym14020193
|
| [16] |
A. M. Fathollahi-Fard, M. Hajiaghaei-Keshteli, R. Tavakkoli-Moghaddam, N. R. Smith, Bi-level programming for home health care supply chain considering outsourcing, J. Ind. Inf. Integr., 25 (2022), 100246. https://doi.org/10.1016/j.jii.2021.100246 doi: 10.1016/j.jii.2021.100246
|
| [17] |
M. Mojtahedi, A. M. Fathollahi-Fard, R. Tavakkoli-Moghaddam, S. Newton, Sustainable vehicle routing problem for coordinated solid waste management, J. Ind. Inf. Integr., 23 (2021), 100220. https://doi.org/10.1016/j.jii.2021.100220 doi: 10.1016/j.jii.2021.100220
|
| [18] |
F. E. Zulvia, R. J. Kuo, D. Y. Nugroho, A many-objective gradient evolution algorithm for solving a green vehicle routing problem with time windows and time dependency for perishable products, J. Cleaner Prod., 242 (2020), 118428. https://doi.org/10.1016/j.jclepro.2019.118428 doi: 10.1016/j.jclepro.2019.118428
|
| [19] |
A. Expósito, J. Brito, J. A. Moreno, C. Exposito-Izquierdo, Quality of service objectives for vehicle routing problem with time windows, Appl. Soft Comput., 84 (2019), 105707. https://doi.org/10.1016/j.asoc.2019.105707 doi: 10.1016/j.asoc.2019.105707
|
| [20] |
C. Liu, G. Kou, X. Zhou, Y. Peng, H. Sheng, P. E. Alsaadi, Time-dependent vehicle routing problem with time windows of city logistics with a congestion avoidance approach, Knowledge-Based Syst., 188 (2020), 104813. https://doi.org/10.1016/j.knosys.2019.06.021 doi: 10.1016/j.knosys.2019.06.021
|
| [21] |
N. Bianchessi, S. Irnich, Branch-and-cut for the split delivery vehicle routing problem with time windows, Transp. Sci., 53 (2019), 442–462. https://doi.org/10.1287/trsc.2018.0825 doi: 10.1287/trsc.2018.0825
|
| [22] |
A. Agga, A. Abbou, M. Labbadi, Y. E. Houm, I. H. Ou Ali, CNN-LSTM: An efficient hybrid deep learning architecture for predicting short-term photovoltaic power production, Electr. Power Syst. Res., 208 (2022), 107908. https://doi.org/10.1016/j.epsr.2022.107908 doi: 10.1016/j.epsr.2022.107908
|
| [23] |
S. Han, Y. Qiao, J. Yan, Y. Liu, L. Li, Z. Wang, Mid-to-long term wind and photovoltaic power generation prediction based on copula function and long short term memory network, Appl. Energy, 239 (2019), 181–191. https://doi.org/10.1016/j.apenergy.2019.01.193 doi: 10.1016/j.apenergy.2019.01.193
|
| [24] |
Z. Yu, P. Duan, L. Meng, Y. Han, F. Ye, Multi-objective path planning for mobile robot with an improved artificial bee colony algorithm, Math. Biosci. Eng., 20 (2023), 2501–2529. https://doi.org/10.3934/mbe.2023117 doi: 10.3934/mbe.2023117
|
| [25] |
L. Li, Z. Liu, M. Tseng, S. Zheng, M. K. Lim, Improved tunicate swarm algorithm: Solving the dynamic economic emission dispatch problems, Appl. Soft Comput., 108 (2021), 107504. https://doi.org/10.1016/j.asoc.2021.107504 doi: 10.1016/j.asoc.2021.107504
|
| [26] |
Z. Liu, L. Li, Y. Liu, J. Liu, H. Li, Q. Shen, Dynamic economic emission dispatch considering renewable energy generation: a novel multi-objective optimization approach, Energy, 235 (2021), 121407. https://doi.org/10.1016/j.energy.2021.121407 doi: 10.1016/j.energy.2021.121407
|
| [27] |
A. T. Eseye, J. Zhang, D. Zheng, Short-term photovoltaic solar power forecasting using a hybrid wavelet-PSO-SVM model based on SCADA and meteorological information optimization approach, Renewable Energy, 118 (2018), 357–367. https://doi.org/10.1016/j.renene.2017.11.011 doi: 10.1016/j.renene.2017.11.011
|
| [28] |
L. Meng, K. Gao, Y. Ren, B. Zhang, H. Sang, C. Zhang, Novel MILP and CP models for distributed hybrid flowshop scheduling problem with sequence-dependent setup times, Swarm Evol. Comput., 71 (2022), 101058. https://doi.org/10.1016/j.swevo.2022.101058 doi: 10.1016/j.swevo.2022.101058
|
| [29] |
L. Meng, C. Zhang, Y. Ren, B. Zhang, C. Lv, Mixed-integer linear programming and constraint programming formulations for solving distributed flexible job shop scheduling problem, IEEE Trans. Cybern., 142 (2020), 106347. https://doi.org/10.1016/j.cie.2020.106347 doi: 10.1016/j.cie.2020.106347
|
| [30] |
H. Guo, H. Sang, B. Zhang, L. Meng, L. Liu, An effective metaheuristic with a differential flight strategy for the distributed permutation flowshop scheduling problem with sequence-dependent setup times, Knowledge-Based Syst., 242 (2022), 108328. https://doi.org/10.1016/j.knosys.2022.108328 doi: 10.1016/j.knosys.2022.108328
|
| [31] |
Z. Li, H. Sang, J. Li, Y. Han, K. Gao, Z. Zheng, et al., Invasive weed optimization for multi-AGVs dispatching problem in a matrix manufacturing workshop, Swarm Evol. Comput., 77 (2023), 101227. https://doi.org/10.1016/j.swevo.2023.101227 doi: 10.1016/j.swevo.2023.101227
|
| [32] |
H. Guo, H. Sang, X. Zhang, P. Duan, J. Li, Y. Han, An effective fruit fly optimization algorithm for the distributed permutation flowshop scheduling problem with total flowtime, Eng. Appl. Artif. Intell., 123 (2023), 106347. https://doi.org/10.1016/j.engappai.2023.106347 doi: 10.1016/j.engappai.2023.106347
|
| [33] |
J. Duan, Z. He, G. G. Yen, Robust multiobjective optimization for vehicle routing problem with time windows, IEEE Trans. Cybern., 52 (2022), 8300–8314. https://doi.org/10.1109/TCYB.2021.3049635 doi: 10.1109/TCYB.2021.3049635
|
| [34] |
Y. Shen, M. Liu, J. Yang, Y. Shi, M. Middendorf, A hybrid swarm intelligence algorithm for vehicle routing problem with time windows, IEEE Access, 8 (2020), 93882–3893. https://doi.org/10.1109/ACCESS.2020.2984660 doi: 10.1109/ACCESS.2020.2984660
|
| [35] |
J. Brito, A. Expósito, J. A. Moreno, Variable neighbourhood search for close–open vehicle routing problem with time windows, IMA J. Manage. Math., 27 (2016), 25–38. https://doi.org/10.1093/imaman/dpt024 doi: 10.1093/imaman/dpt024
|
| [36] |
M. Keskin, B. Catay, Partial recharge strategies for the electric vehicle routing problem with time windows, Transp. Res. Part C Emerging Technol., 65 (2016), 111–127. https://doi.org/10.1016/j.trc.2016.01.013 doi: 10.1016/j.trc.2016.01.013
|
| [37] |
Z. H. Ahmed, M. Yousefikhoshbakht, An improved tabu search algorithm for solving heterogeneous fixed fleet open vehicle routing problem with time windows, Alexandria Eng. J., 64 (2023), 349–363. https://doi.org/10.1016/j.aej.2022.09.008 doi: 10.1016/j.aej.2022.09.008
|
| [38] |
N. L. Giedelmann, W. J. Guerrero, E. L. Solano-Charris, On the emergency water distribution problem: optimizing vehicle routing decisions with deprivation costs considerations, IFAC-PapersOnLine, 55 (2022), 3166–3171. https://doi.org/10.1016/j.ifacol.2022.10.216 doi: 10.1016/j.ifacol.2022.10.216
|
| [39] |
Y. E. M. Vieira, R. A. de Mello Bandeira, O. S. da Silva Júnior, Multi-depot vehicle routing problem for large scale disaster relief in drought scenarios: the case of the Brazilian northeast region, Int. J. Disaster Risk Reduct., 58 (2021), 102193. https://doi.org/10.1016/j.ijdrr.2021.102193 doi: 10.1016/j.ijdrr.2021.102193
|
| [40] |
J. Yi, J. Wang, G. Wang, Using monarch butterfly optimization to solve the emergency vehicle routing problem with relief materials in sudden disasters, Open Geosci., 11 (2019), 391–413. https://doi.org/10.1515/geo-2019-0031 doi: 10.1515/geo-2019-0031
|
| [41] |
M. F. N. Maghfiroh, S. Hanaoka, Dynamic truck and trailer routing problem for last mile distribution in disaster response, J. Humanitarian Logist. Supply Chain Manage., 8 (2018), 252–278. https://doi.org/10.1108/JHLSCM-10-2017-0050 doi: 10.1108/JHLSCM-10-2017-0050
|
| [42] |
M. M. Solomon, Algorithms for the vehicle routing and scheduling problems with time window constraints, Oper. Res., 35 (1987), 254–265. https://doi.org/doi:10.1287/opre.35.2.254 doi: 10.1287/opre.35.2.254
|
| [43] |
C. Lu, Q. Liu, B. Zhang, L. Yin, A pareto-based hybrid iterated greedy algorithm for energy-efficient scheduling of distributed hybrid flowshop, Expert Syst. Appl., 204 (2022), 117555. https://doi.org/10.1016/j.eswa.2022.117555 doi: 10.1016/j.eswa.2022.117555
|
| [44] |
X. Ren, S. Chen, L. Ren, Optimization of regional emergency supplies distribution vehicle route with dynamic real-time demand, Math. Biosci. Eng., 20 (2023), 7487–7518. https://doi.org/10.3934/mbe.2023324 doi: 10.3934/mbe.2023324
|
| [45] |
Y. Xia, Z. Fu, Improved tabu search algorithm for the open vehicle routing problem with soft time windows and satisfaction rate, Cluster Comput., 22 (2019), 8725–8733. https://doi.org/10.1007/s10586-018-1957-x doi: 10.1007/s10586-018-1957-x
|
| [46] |
W. Ran, L. Liu, G. Yang, A hybrid ant colony algorithm for vehicle routing problem with time windows, Inf. Technol. J., 12 (2013), 5701–5706. https://doi.org/10.3923/itj.2013.5701.5706 doi: 10.3923/itj.2013.5701.5706
|
| [47] |
Q. Liu, P. Xu, Y. Wu, T. Shen, A hybrid genetic algorithm for the electric vehicle routing problem with time windows, Control Theory Technol., 20 (2022), 279–286. https://doi.org/10.1007/s11768-022-00091-1 doi: 10.1007/s11768-022-00091-1
|
| [48] |
A. Redi, P. Jewpanya, A. C. Kurniawan, S. F. Persada, R. Nadlifatin, O. Dewi, A simulated annealing algorithm for solving two-echelon vehicle routing problem with locker facilities, Algorithms, 13 (2020), 218. https://doi.org/10.3390/a13090218 doi: 10.3390/a13090218
|
Figures(13) / Tables(8)
Kaidong Yang, Peng Duan, Huishan Yu. An improved genetic algorithm for solving the helicopter routing problem with time window in post-disaster rescue[J]. Mathematical Biosciences and Engineering, 2023, 20(9): 15672-15707. doi: 10.3934/mbe.2023699
DownLoad: