A two-step sub-optimal algorithm for bus evacuation planning

Feng，Yuanyuan1; Cao，Yi2,3; Yang，Shuanghua2,3,4; Yang，Lili5; Wei，Tangjian6,7

2023-06-01

10.1007/s12351-023-00781-x

Operational Research   Impact Factor & Quartile

1109-2858

1866-1505

In large-scale disasters, as an important part of the rescue management, buses are often used to evacuate carless people. Timing is always the main concern in any evacuation planning. Hence, not only is minimizing evacuation time the primary goal of bus evacuation problems (BEPs), but computation time to solve a BEP is also crucial. Nevertheless, BEP is NP-hard which makes optimization of the BEP for large-scale disasters within an acceptable time intractable. Practically, sub-optimal but efficient algorithms for bus evacuation planning are desired. In this work a two-step sub-optimal algorithm, called network flow planning (NFP) algorithm is proposed. In the NFP, firstly, an aggregated network flow model, which minimizes the total travel time of all the buses, is adopted. It is proven that the model can be solved as a linear programming problem. The minimum total travel time solution is then converted to approximate the minimum evacuation time solution by assigning evacuation tasks to all buses as equally as possible in the second step. To verify the effectiveness of the NFP algorithm, a greedy algorithm inspired by NFP is presented, and several numerical case studies are presented in this paper. In a Monte Carlo simulation study, randomized cases are used to demonstrate the superiority of the proposed algorithm over the presented greedy algorithm, a genetic algorithm, an approximation algorithm and CPLEX. Furthermore, a real-world large-scale flood disaster case in Xingguo, China is studied, which illustrates the efficiency and practical value of the proposed algorithm in large-scale evacuations.

Bus evacuation problem Large-scale disaster Network flow model Pseudo-polynomial time

SCI

English

Others

Shenzhen Science and Technology Innovation Program[JCYJ20200109141218676];

Operations Research & Management Science

Operations Research & Management Science

WOS:000999366900001

SPRINGER HEIDELBERG

2-s2.0-85160915721

Scopus

1.College of Computer Science and Technology,Zhejiang University,Hangzhou,Yuhangtang Rd, Zhejiang Province,310027,China
2.College of Chemical and Biological Engineering,Zhejiang University,Hangzhou,Yuhangtang Rd, Zhejiang Province,310027,China
3.Institute of Zhejiang University-Quzhou,Quzhou,Jiuhua North Rd, Zhejiang Province,324003,China
4.Department of Computer Science,University of Reading,Reading,Berkshire,RG6 6AH,United Kingdom
5.Department of Statistics and Data Science,Southern University of Science and Technology,Shenzhen,Guangdong Province,518055,China
6.School of Transportation Engineering,East China Jiao Tong University,Nanchang,Jiangxi Province,330013,China
7.Institute for Transport Studies,The University of Leeds,Leeds,LS2 9JT,United Kingdom

Feng，Yuanyuan,Cao，Yi,Yang，Shuanghua,et al. A two-step sub-optimal algorithm for bus evacuation planning[J]. Operational Research,2023,23(2).

Feng，Yuanyuan,Cao，Yi,Yang，Shuanghua,Yang，Lili,&Wei，Tangjian.(2023).A two-step sub-optimal algorithm for bus evacuation planning.Operational Research,23(2).

Feng，Yuanyuan,et al."A two-step sub-optimal algorithm for bus evacuation planning".Operational Research 23.2(2023).