A hybrid metaheuristic algorithm for the multi-objective location-routing problem in the early post-disaster stage

Tongren Yan; Fuqiang Lu; Suxin Wang; Leizhen Wang; Hualing Bi

doi:10.3934/jimo.2022145

Article Contents

2023, Volume 19, Issue 6: 4663-4691. Doi: 10.3934/jimo.2022145

This issue Previous Article A linesearch projection algorithm for solving equilibrium problems without monotonicity in Hilbert spaces Next Article Platform contract selection and coordination contract design in reward-based crowdfunding

A hybrid metaheuristic algorithm for the multi-objective location-routing problem in the early post-disaster stage

1.
College of Information Science and Engineering, Northeastern University, Shenyang, Liaoning 110819, China
2.
School of Economics and Management, Yanshan University, Qinhuangdao, Hebei 066004, China

^*Corresponding author: Fuqiang Lu
^*Corresponding author: Fuqiang Lu

Received: December 2021

Revised: June 2022

Early access: August 2022

Published: June 2023

Abstract / Introduction Full Text(HTML) Figure(11) / Table(13) Related Papers Cited by

Abstract

Disasters such as earthquakes, typhoons, floods and COVID-19 continue to threaten the lives of people in all countries. In order to cover the basic needs of the victims, emergency logistics should be implemented in time. Location-routing problem (LRP) tackles facility location problem and vehicle routing problem simultaneously to obtain the overall optimization. In response to the shortage of relief materials in the early post-disaster stage, a multi-objective model for the LRP considering fairness is constructed by evaluating the urgency coefficients of all demand points. The objectives are the lowest cost, delivery time and degree of dissatisfaction. Since LRP is a NP-hard problem, a hybrid metaheuristic algorithm of Discrete Particle Swarm Optimization (DPSO) and Harris Hawks Optimization (HHO) is designed to solve the model. In addition, three improvement strategies, namely elite-opposition learning, nonlinear escaping energy, multi-probability random walk, are introduced to enhance its execution efficiency. Finally, the effectiveness and performance of the LRP model and the hybrid metaheuristic algorithm are verified by a case study of COVID-19 in Wuhan. It demonstrates that the hybrid metaheuristic algorithm is more competitive with higher accuracy and the ability to jump out of the local optimum than other metaheuristic algorithms.

Keywords:

Mathematics Subject Classification: Primary: 90B06.

Citation:

Full Text(HTML)

Figure 1. A simplified diagram of location-routing problem

Download: Full-size image PowerPoint slide

Figure 2. Encoding scheme

Download: Full-size image PowerPoint slide

Figure 3. An example of the encoding scheme

Download: Full-size image PowerPoint slide

Figure 4. The change curve of sigmoid function

Download: Full-size image PowerPoint slide

Figure 5. The change curve of unimproved $ E $

Download: Full-size image PowerPoint slide

Figure 6. The change curve of improved $ E $

Download: Full-size image PowerPoint slide

Figure 7. The flow chart of IHDH

Download: Full-size image PowerPoint slide

Figure 8. The geographical location information of the 7 candidate delivery centers and the 13 demand points

Download: Full-size image PowerPoint slide

Figure 9. The iterative convergence curve of IHDH

Download: Full-size image PowerPoint slide

Figure 10. The convergence curves of the average of 30 running results

Download: Full-size image PowerPoint slide

Figure 11. The box-plot for the seven metaheuristic algorithms

Download: Full-size image PowerPoint slide

Table 1. Explanations of corresponding notations

Notation	Explanation
Sets
$ I $	Set of candidate distribution centers.
$ J $	Set of demand points.
$ K $	Set of vehicles.
Parameters
$ Q $	Maximum supply of relief materials.
$ Q_{1i} $	Maximum capacity of distribution center $ i $.
$ Q_{2k} $	Maximum capacity of vehicle $ k $.
$ C_{1i} $	Construction and operation costs of distribution center $ i $.
$ C_{2k} $	Unit transportation cost of vehicle $ k $.
$ q_j $	Demand of demand point $ j $.
$ \lambda_j $	Urgency coefficient of demand point $ j $.
$ d_{ij} $	Distance between node $ i $ and node $ j $.
$ t_{ijk} $	Time for vehicle $ k $ to transport from node $ i $ to node $ j $.
$ u_j $	Quantity of relief materials received at demand point $ j $.
Decisions variables
$ z_i $	Whether candidate distribution center $ i $ is employed.
$ y_{ijk} $	Whether vehicle $ k $ delivers relief materials from node $ i $ to $ j $.
$ x_{ij} $	Whether demand point $ j $ is served by distribution center $ i $.
$ X_{ij} $	Quantity of relief materials provided by distribution center
	$ i $ to demand point $ j $.

| Show Table

DownLoad: CSV

Table 2. The overall vehicle delivery routes of the example

Vehicle number	Delivery route of the vehicle
1	$ 3 \longrightarrow 6 \longrightarrow 8 \longrightarrow 3 $
2	$ 1 \longrightarrow 4 \longrightarrow 1 $
3	$ 3 \longrightarrow 3 $
4	$ 1 \longrightarrow 5 \longrightarrow 7 \longrightarrow 1 $

| Show Table

DownLoad: CSV

Table 3. The comparison results between the precise algorithm and the hybrid metaheuristic algorithm in the small scale experiment

Solving algorithm	Fitness	CPU time (s)
Precise algorithm	1.2763	224.169
Metaheuristic algorithm	1.2814	3.465

| Show Table

DownLoad: CSV

Table 4. The parameters of candidate delivery centers

Candidate delivery center	Number	Cost (CNY)	Capacity (kg)
Wuhan Railway Station	1	40000	20000
Wuchang Railway Station	2	36000	18000
Hankou Railway Station	3	34000	17000
Huashannan Railway Station	4	32000	16000
Tangxunhu Railway Station	5	30000	15000
Tianhe International Airport	6	40000	20000
Hannan General Airport	7	34000	17000

| Show Table

DownLoad: CSV

Table 5. The parameters of demand vehicles

Number of vehicles	Cost (CNY)	Velocity (km/h)	Capacity (kg)
1–3	8000	45	320
4–6	9000	45	360
7–10	10000	45	400

| Show Table

DownLoad: CSV

Table 6. The parameters of demand points

Demand point	Number	Demand (kg)
Jiangan District	8	5100
Jianghan District	9	9400
Qiaokou District	10	9700
Hanyang District	11	4600
Wuchang District	12	8900
Qingshan District	13	4200
Hongshan District	14	4500
Hannan District	15	3900
Caidian District	16	2400
Jiangxia District	17	1700
Huangpi District	18	1400
Xinzhou District	19	1200
Dongxihu District	20	1900

| Show Table

DownLoad: CSV

Table 7. The relevant information of the 13 districts in Wuhan on February 29

Number	Cumulative cases	Additional cases	Percentage	Density (/km$ ^{2} $)	GDP (CNY)
8	4300	183	0.4466%	11993	$ 1335.9 \times 10^8 $
9	7290	191	0.9989%	25797	$ 1428.5 \times 10^8 $
10	7239	739	0.8331%	21689	$ 874.18 \times 10^8 $
11	3579	407	0.5342%	6007	$ 761.39 \times 10^8 $
12	8224	351	0.6398%	19904	$ 1522.04 \times 10^8 $
13	2958	143	0.5592%	9261	$ 863.14 \times 10^8 $
14	4999	351	0.2918%	2988	$ 1058.58 \times 10^8 $
15	1517	47	1.1154%	474	$ 1643.53 \times 10^8 $
16	1974	120	0.2515%	718	$ 400.53 \times 10^8 $
17	1661	196	0.1683%	489	$ 948.8 \times 10^8 $
18	1775	106	0.1727%	456	$ 1071.1 \times 10^8 $
19	1018	22	0.1111%	626	$ 951.61 \times 10^8 $
20	2588	65	0.4304%	1214	$ 1351.63 \times 10^8 $

| Show Table

DownLoad: CSV

Table 8. The weights of these evaluation indicators

Evaluation indicator	Indicator weight
Cumulative cases	0.181597
Additional cases	0.191141
Percentage	0.161722
Density	0.35917
GDP	0.10637

| Show Table

DownLoad: CSV

Table 9. The urgent coefficients of the 13 districts in Wuhan

Number of demand points	Urgent coefficient
8	0.0879481
9	0.155844
10	0.18134
11	0.0765009
12	0.145336
13	0.0749613
14	0.0624538
15	0.0583092
16	0.0450429
17	0.0323935
18	0.0247054
19	0.0244273
20	0.0307375

| Show Table

DownLoad: CSV

Table 10. The specific information of the selected distribution centers in the optimal LRP scheme

Number of selected delivery centers	Capacity (kg)	Actual supply (kg)
1	20000	17000
2	18000	8400
3	17000	17000
5	30000	12600

| Show Table

DownLoad: CSV

Table 11. The vehicle delivery routes in the optimal LRP scheme

Number of vehicles	Delivery route of the vehicle
1	$ 1 \longrightarrow 20 \longrightarrow 19 \longrightarrow 18 \longrightarrow 13 \longrightarrow 1 $
2	$ 5 \longrightarrow 16 \longrightarrow 11 \longrightarrow 5 $
3	$ 5 \longrightarrow 17 \longrightarrow 15 \longrightarrow 5 $
4	$ 2 \longrightarrow 12 \longrightarrow 2 $
5	$ 1 \longrightarrow 8 \longrightarrow 14 \longrightarrow 1 $
6	$ 1 \longrightarrow 1 $
7	$ 3 \longrightarrow 10 \longrightarrow 3 $
8	$ 3 \longrightarrow 3 $
9	$ 5 \longrightarrow 5 $
10	$ 3 \longrightarrow 9 \longrightarrow 3 $

| Show Table

DownLoad: CSV

Table 12. The specific information of the demand points in the optimal LRP scheme

Number of demand points	Urgency coefficient	Demand (kg) (kg)	Quantities received (kg)
8	0.0879481	5100	5100
9	0.155844	9400	7300
10	0.18134	9700	9700
11	0.0765009	4600	4600
12	0.145336	8900	8400
13	0.0749613	4200	4200
14	0.0624538	4500	3900
15	0.0583092	3900	3900
16	0.0450429	3400	2400
17	0.0323935	1700	1700
18	0.0247054	1400	1400
19	0.0244273	1200	500
20	0.0307375	1900	1900

| Show Table

DownLoad: CSV

Table 13. The experiment results of these metaheuristic algorithms

Algorithm	Best fitness	Worst fitness	Average fitness	Standard deviation	Average iterations to its optimum	Time (s)
SA	1.5038	1.6284	1.5557	0.0342	599	3.762
DPSO	1.5821	1.6807	1.6201	0.0337	503	4.753
WOA	1.5515	1.6512	1.5952	0.0328	459	5.668
SOA	1.5065	1.6351	1.5859	0.0373	481	5.343
BWO	1.5006	1.6649	1.6005	0.0472	514	2.805
HDH	1.5131	1.6058	1.5701	0.0274	372	6.164
IHDH	1.4029	1.5056	1.4595	0.0365	251	13.567

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	K. Alamatsaz, A. Ahmadi and S. M. J. M. Al-e-hashem, A multiobjective model for the green capacitated location-routing problem considering drivers' satisfaction and time window with uncertain demand, Environmental Science and Pollution Research, 29 (2022), 5052-5071. doi: 10.1007/s11356-021-15907-x.
[2]	R. Bandyopadhyay, R. Kundu and D. Oliva, Segmentation of brain MRI using an altruistic Harris Hawks' Optimization algorithm, Knowledge-Based Systems, 232 (2021), 107468.
[3]	K. L. Chang, H. Zhou, G. J. Chen and H. Q. Chen, Multiobjective location routing problem considering uncertain data after disasters, Discrete Dyn. Nat. Soc., (2017), Art. ID 1703608, 7 pp. doi: 10.1155/2017/1703608.
[4]	L. Cooper, The transportation-location problem, Operations Research, 20 (1972), 94-108. doi: 10.1287/opre.20.1.94.
[5]	G. Dhiman and V. Kumar, Seagull optimization algorithm: Theory and its applications for large-scale industrial engineering problems, Knowledge-Based Systems, 165 (2019), 169-196. doi: 10.1016/j.knosys.2018.11.024.
[6]	R. Eberhart and J. Kennedy, A new optimizer using particle swarm theory, MHS'95. Proceedings of the Sixth International Symposium on Micro Machine and Human Science, (1995), 39–43. doi: 10.1109/MHS.1995.494215.
[7]	A. M. Fathollahi-Fard, M. Hajiaghaei-Keshteli, R. Tavakkoli-Moghaddam and N. R. Smith, Bi-level programming for home health care supply chain considering outsourcing, Journal of Industrial Information Integration, 25 (2021), 100246. doi: 10.1016/j.jii.2021.100246.
[8]	X. H. Gao, A bi-level stochastic optimization model for multi-commodity rebalancing under uncertainty in disaster response, Annals of Operations Research, (2019), 1–34. doi: 10.1007/s10479-019-03506-6.
[9]	A. Gogna and A. Tayal, Metaheuristics: Review and application, Journal of Experimental & Theoretical Artificial Intelligence, 25 (2013), 503-526. doi: 10.1080/0952813X.2013.782347.
[10]	A. A. Heidari, S. Mirjalili, H. Faris, I. Aljarah, M. Mafarja and H. L. Chen, Harris hawks optimization: Algorithm and applications, Future Generation Computer Systems, 97 (2019), 849-872. doi: 10.1016/j.future.2019.02.028.
[11]	J. H. Holland, Genetic algorithms, Scientific American, 267 (1992), 66-73.
[12]	M. Irfan, A. Wadood, T. Khurshaid, B. M. Khan, K.-C. Kim, S.-R. Oh and S.-B. Rhee, An optimized adaptive protection scheme for numerical and directional overcurrent relay coordination using Harris Hawk Optimization, Energies, 14 (2021), 5603. doi: 10.3390/en14185603.
[13]	M. Issa and A. Samn, Passive vehicle suspension system optimization using Harris Hawk Optimization algorithm, Math. Comput. Simulation, 191 (2022), 328-345. doi: 10.1016/j.matcom.2021.08.016.
[14]	Y. P. Jiang and Y. F. Yuan, Emergency logistics in a large-scale disaster context: Achievements and challenges, International Journal of Environmental Research and Public Health, 16 (2019), 779. doi: 10.3390/ijerph16050779.
[15]	J. Kennedy and R. Eberhart, A discrete binary version of the particle swarm algorithm, International Conference on Systems, Man, and Cybernetics, 5 (1997), 4104-4108. doi: 10.1109/ICSMC.1997.637339.
[16]	S. Khanchehzarrin, M. P. Panah, N. Mahdavi-Amiri and S. Shiripour, A bi-level multi-objective location-routing optimization model for disaster relief operations considering public donations, Socio-Economic Planning Sciences, 80 (2021), 101165. doi: 10.1016/j.seps.2021.101165.
[17]	G. Kou, H. Xiao, M. H. Cao and L. H. Lee, Optimal computing budget allocation for the vector evaluated genetic algorithm in multi-objective simulation optimization, Automatica, 129 (2021), 109599, 14 pp. doi: 10.1016/j.automatica.2021.109599.
[18]	Y. H. Li and W. D. Chen, Entropy method of constructing a combined model for improving loan default prediction: A case study in China, Journal of the Operational Research Society, 72 (2021), 1099-1109. doi: 10.1080/01605682.2019.1702905.
[19]	B. Liang, D. P. Yang, X. H. Qin and T. Tinta, A risk-averse shelter location and evacuation routing assignment problem in an uncertain environment, International Journal of Environmental Research and Public Health, 16 (2019), 4007. doi: 10.3390/ijerph16204007.
[20]	C. S. Liu, G. Kou, Y. Peng and F. E. Alsaadi, Location-routing problem for relief distribution in the early post-earthquake stage from the perspective of fairness, Sustainability, 11 (2019), 3420. doi: 10.3390/su11123420.
[21]	R. B. Lopes, C. Ferreira and B. S. Santos, A simple and effective evolutionary algorithm for the capacitated location-routing problem, Comput. Oper. Res., 70 (2016), 155-162. doi: 10.1016/j.cor.2016.01.006.
[22]	Z. Mahtab, A. Azeem, S. M. Ali, S. K. Paul and A. M. Fathollahi-Fard, Multi-objective robust-stochastic optimisation of relief goods distribution under uncertainty: A real-life case study, International Journal of Systems Science: Operations & Logistics, (2021), 241–262. doi: 10.1080/23302674.2021.1879305.
[23]	Y. Marinakis, An improved particle swarm optimization algorithm for the capacitated location routing problem and for the location routing problem with stochastic demands, Applied Soft Computing, 37 (2015), 680-701. doi: 10.1016/j.asoc.2015.09.005.
[24]	S. Mirjalili and A. Lewis, The whale optimization algorithm, Advances in Engineering Software, 95 (2016), 51-67. doi: 10.1016/j.advengsoft.2016.01.008.
[25]	M. Mojtahedi, R. Y. Sunindijo, F. Lestari, Su parni and O. Wijaya, Developing hospital emergency and disaster management index using TOPSIS method, Sustainability, 13 (2021), 5213. doi: 10.3390/su13095213.
[26]	A. M. Nezhadroshan, A. M. Fathollahi-Fard and M. Hajiaghaei-Keshteli, A scenario-based possibilistic-stochastic programming approach to address resilient humanitarian logistics considering travel time and resilience levels of facilities, International Journal of Systems Science: Operations & Logistics, 8 (2021), 321-347. doi: 10.1080/23302674.2020.1769766.
[27]	A. F. Pena-Delgado, H. Peraza-Vazquez and J. H. Almazan-Covarrubias, A novel bio-inspired algorithm applied to selective harmonic elimination in a three-phase eleven-level inverter, Mathematical Problems in Engineering, (2020).
[28]	J. Piri and P. Mohapatra, An analytical study of modified multi-objective Harris Hawk Optimizer towards medical data feature selection, Computers in Biology and Medicine, 135 (2021), 104558. doi: 10.1016/j.compbiomed.2021.104558.
[29]	B. Rabta, C. Wankmuller and G. Reiner, A drone fleet model for last-mile distribution in disaster relief operations, International Journal of Disaster Risk Reduction, 28 (2018), 107-112. doi: 10.1016/j.ijdrr.2018.02.020.
[30]	B. Saeidian, M. S. Mesgari and M. Ghodousi, Evaluation and comparison of Genetic Algorithm and Bees Algorithm for location-allocation of earthquake relief centers, International Journal of Disaster Risk Reduction, 15 (2016), 94-107. doi: 10.1016/j.ijdrr.2016.01.002.
[31]	S. M. Shavarani, Multi-level facility location-allocation problem for post-disaster humanitarian relief distribution: A case study, Journal of Humanitarian Logistics and Supply Chain Management, 9 (2019), 70-81. doi: 10.1108/JHLSCM-05-2018-0036.
[32]	L. Shen, F. M. Tao, Y. H. Shi and R. R. Qin, Optimization of location-routing problem in emergency logistics considering carbon emissions, International Journal of Environmental Research and Public Health, 16 (2019), 2982. doi: 10.3390/ijerph16162982.
[33]	H. R. Tizhoosh, Opposition-based learning: A new scheme for machine intelligence, International Conference on Computational Intelligence for Modelling, Control and Automation and International Conference on Intelligent Agents, Web Technologies and Internet Commerce, 1 (2015), 695-701. doi: 10.1109/CIMCA.2005.1631345.
[34]	B. Vahdani, D. Veysmoradi, N. Shekari and S. M. Mousavi, Multi-objective, multi-period location-routing model to distribute relief after earthquake by considering emergency roadway repair, Neural Computing and Applications, 30 (2018), 835-854. doi: 10.1007/s00521-016-2696-7.
[35]	D. Veysmoradi, B. Vahdani, M. F. Sartangi and S. M. Mousavi, Multi-objective open location-routing model for relief distribution networks with split delivery and multi-mode transportation under uncertainty, Scientia Iranica, 25 (2018), 3635-3653. doi: 10.24200/sci.2017.4572.
[36]	S. X. Wang, H. Wen and F. Q. Lu, Modeling of 3D cargo loading problem and optimization of crow search algorithm, Journal of Hunan University Natural Sciences, 47 (2020), 21-30.
[37]	X. W. Xiong, F. Zhao, Y. D. Wang and Y. P. Wang, Research on the model and algorithm for multimodal distribution of emergency supplies after earthquake in the perspective of fairness, Mathematical Problems in Engineering, (2019), 1629321. doi: 10.1155/2019/1629321.
[38]	R. Y. Yin and P. X. Lu, A cluster-first route-second constructive heuristic method for emergency logistics scheduling in urban transport networks, Sustainability, 14 (2022), 2301. doi: 10.3390/su14042301.
[39]	S. Y. Yin, L. J. Du, Y. F. Xia and Z. Ye, Review on model and algorithms of the post-disaster relief distribution problem, Journal of Physics: Conference Series, 1302 (2019), 022003. doi: 10.1088/1742-6596/1302/2/022003.
[40]	S. Zhang, Q. F. Luo and Y. Q. Zhou, Hybrid grey wolf optimizer using elite opposition-based learning strategy and simplex method, International Journal of Computational Intelligence and Applications, 16 (2017), 1750012. doi: 10.1142/S1469026817500122.