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

Yuanyuan Feng (), Yi Cao (), Shuanghua Yang (), Lili Yang () and Tangjian Wei ()
Additional contact information
Yuanyuan Feng: Zhejiang University
Yi Cao: Zhejiang University
Shuanghua Yang: Zhejiang University
Lili Yang: Southern University of Science and Technology
Tangjian Wei: East China Jiao Tong University

Operational Research, 2023, vol. 23, issue 2, No 14, 35 pages

Abstract: Abstract 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.

Keywords: Bus evacuation problem; Network flow model; Pseudo-polynomial time; Large-scale disaster (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s12351-023-00781-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:operea:v:23:y:2023:i:2:d:10.1007_s12351-023-00781-x

Ordering information: This journal article can be ordered from
https://www.springer ... search/journal/12351

DOI: 10.1007/s12351-023-00781-x

Access Statistics for this article

Operational Research is currently edited by Nikolaos F. Matsatsinis, John Psarras and Constantin Zopounidis

More articles in Operational Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().