# American Institute of Mathematical Sciences

doi: 10.3934/jimo.2022145
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

## 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

Received  December 2021 Revised  June 2022 Early access August 2022

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.

Citation: Tongren Yan, Fuqiang Lu, Suxin Wang, Leizhen Wang, Hualing Bi. A hybrid metaheuristic algorithm for the multi-objective location-routing problem in the early post-disaster stage. Journal of Industrial and Management Optimization, doi: 10.3934/jimo.2022145
##### References:

show all references

##### References:
A simplified diagram of location-routing problem
Encoding scheme
An example of the encoding scheme
The change curve of sigmoid function
The change curve of unimproved $E$
The change curve of improved $E$
The flow chart of IHDH
The geographical location information of the 7 candidate delivery centers and the 13 demand points
The iterative convergence curve of IHDH
The convergence curves of the average of 30 running results
The box-plot for the seven metaheuristic algorithms
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$.
 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$.
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$
 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$
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
 Solving algorithm Fitness CPU time (s) Precise algorithm 1.2763 224.169 Metaheuristic algorithm 1.2814 3.465
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
 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
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
 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
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
 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
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$
 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$
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
 Evaluation indicator Indicator weight Cumulative cases 0.181597 Additional cases 0.191141 Percentage 0.161722 Density 0.35917 GDP 0.10637
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
 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
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
 Number of selected delivery centers Capacity (kg) Actual supply (kg) 1 20000 17000 2 18000 8400 3 17000 17000 5 30000 12600
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$
 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$
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
 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
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
 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
 [1] Shoufeng Ji, Jinhuan Tang, Minghe Sun, Rongjuan Luo. Multi-objective optimization for a combined location-routing-inventory system considering carbon-capped differences. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1949-1977. doi: 10.3934/jimo.2021051 [2] Lixin Wei, Bin Feng, Qingsong Liu. Picker routing optimization of storage stacker based on improved multi-objective iterative local search algorithm. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022187 [3] Anh Son Ta, Le Thi Hoai An, Djamel Khadraoui, Pham Dinh Tao. Solving Partitioning-Hub Location-Routing Problem using DCA. Journal of Industrial and Management Optimization, 2012, 8 (1) : 87-102. doi: 10.3934/jimo.2012.8.87 [4] Xiliang Sun, Wanjie Hu, Xiaolong Xue, Jianjun Dong. Multi-objective optimization model for planning metro-based underground logistics system network: Nanjing case study. Journal of Industrial and Management Optimization, 2023, 19 (1) : 170-196. doi: 10.3934/jimo.2021179 [5] Namsu Ahn, Soochan Kim. Optimal and heuristic algorithms for the multi-objective vehicle routing problem with drones for military surveillance operations. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1651-1663. doi: 10.3934/jimo.2021037 [6] Min Zhang, Gang Li. Multi-objective optimization algorithm based on improved particle swarm in cloud computing environment. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1413-1426. doi: 10.3934/dcdss.2019097 [7] Tone-Yau Huang, Tamaki Tanaka. Optimality and duality for complex multi-objective programming. Numerical Algebra, Control and Optimization, 2022, 12 (1) : 121-134. doi: 10.3934/naco.2021055 [8] Lin Jiang, Song Wang. Robust multi-period and multi-objective portfolio selection. Journal of Industrial and Management Optimization, 2021, 17 (2) : 695-709. doi: 10.3934/jimo.2019130 [9] Zhongqiang Wu, Zongkui Xie. A multi-objective lion swarm optimization based on multi-agent. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022001 [10] Jian Xiong, Zhongbao Zhou, Ke Tian, Tianjun Liao, Jianmai Shi. A multi-objective approach for weapon selection and planning problems in dynamic environments. Journal of Industrial and Management Optimization, 2017, 13 (3) : 1189-1211. doi: 10.3934/jimo.2016068 [11] Dušan M. Stipanović, Claire J. Tomlin, George Leitmann. A note on monotone approximations of minimum and maximum functions and multi-objective problems. Numerical Algebra, Control and Optimization, 2011, 1 (3) : 487-493. doi: 10.3934/naco.2011.1.487 [12] Hamed Fazlollahtabar, Mohammad Saidi-Mehrabad. Optimizing multi-objective decision making having qualitative evaluation. Journal of Industrial and Management Optimization, 2015, 11 (3) : 747-762. doi: 10.3934/jimo.2015.11.747 [13] Yuan-mei Xia, Xin-min Yang, Ke-quan Zhao. A combined scalarization method for multi-objective optimization problems. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2669-2683. doi: 10.3934/jimo.2020088 [14] Xia Zhao, Jianping Dou. Bi-objective integrated supply chain design with transportation choices: A multi-objective particle swarm optimization. Journal of Industrial and Management Optimization, 2019, 15 (3) : 1263-1288. doi: 10.3934/jimo.2018095 [15] Fan Zhang, Guifa Teng, Mengmeng Gao, Shuai Zhang, Jingjing Zhang. Multi-machine and multi-task emergency allocation algorithm based on precedence rules. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1501-1513. doi: 10.3934/dcdss.2019103 [16] Shungen Luo, Xiuping Guo. Multi-objective optimization of multi-microgrid power dispatch under uncertainties using interval optimization. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021208 [17] Ömer Arslan, Selçuk Kürşat İşleyen. A model and two heuristic methods for The Multi-Product Inventory-Location-Routing Problem with heterogeneous fleet. Journal of Industrial and Management Optimization, 2022, 18 (2) : 897-932. doi: 10.3934/jimo.2021002 [18] Jiao-Yan Li, Xiao Hu, Zhong Wan. An integrated bi-objective optimization model and improved genetic algorithm for vehicle routing problems with temporal and spatial constraints. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1203-1220. doi: 10.3934/jimo.2018200 [19] Giuseppe Buttazzo, Serena Guarino Lo Bianco, Fabrizio Oliviero. Optimal location problems with routing cost. Discrete and Continuous Dynamical Systems, 2014, 34 (4) : 1301-1317. doi: 10.3934/dcds.2014.34.1301 [20] Adriel Cheng, Cheng-Chew Lim. Optimizing system-on-chip verifications with multi-objective genetic evolutionary algorithms. Journal of Industrial and Management Optimization, 2014, 10 (2) : 383-396. doi: 10.3934/jimo.2014.10.383

2021 Impact Factor: 1.411