An approximation algorithm for bus evacuation problem

doi:10.1016/j.neucom.2024.127252

An approximation algorithm for bus evacuation problem

2024-03-01

0

PRE

AI

DOI：10.1016/j.neucom.2024.127252

Original

Original request for help

Save

Abstract

En 中文

In large-scale disasters, evacuation using public transport, such as buses, is always essential, especially with limitations on the time window and resources available. Unfortunately, a Bus Evacuation Problem (BEP) is NP -hard in nature. This means it is impossible to find an optimal evacuation plan within a reasonable time window. Therefore, it is efficacious and requisite to use an approximation algorithm such that a sub -optimal plan can be derived quickly in large-scale disasters. In the literature, an approximation algorithm for BEP has been presented. However, there is not only a lack of rigorous proof of the approximation ratio, but also the computation time of the approximation algorithm is influenced by the number of evacuees. In this work, firstly the approximation ratio is derived as 2nb +7, where nb is the number of buses, which is fundamentally more precise than the existing work. Further, the approximation ratio can be reduced to nb+ 6 through a new proof provided in this work. More importantly, a new approximation algorithm is proposed in this work, with an aggregated network flow model that can be quickly solved as a linear programming problem in polynomial time. The approximation ratio of the new algorithm is proven to be nb + 1 when there is a pile of buses, and the computation time is insensitive to the number of evacuees. Finally, 10 sets of random cases and a real -life disaster, the flooding in Xingguo, China in 2019 are studied to illustrate the efficiency and practical applicability of the proposed approximation algorithm.

Keywords:

Disaster relief

Bus evacuation problem

Network flow model

Approximation algorithm

Approximation ratio

An approximation algorithm for bus evacuation problem

Abstract

Journal

Organization