Limits...
K-Shortest-Path-Based Evacuation Routing with Police Resource Allocation in City Transportation Networks.

He Y, Liu Z, Shi J, Wang Y, Zhang J, Liu J - PLoS ONE (2015)

Bottom Line: The proposed algorithms are tested with a number of examples based on real data from cities of different sizes.The computational results show that the police resource utilization efficiency index is very helpful in finding near-optimal solutions.Additionally, comparing the performance of the heuristic algorithm and the linearization method by using randomly generated examples indicates that the efficiency of the heuristic algorithm is superior.

View Article: PubMed Central - PubMed

Affiliation: Science and Technology on Information Systems Engineering Laboratory, National University of Defense Technology, Changsha, Hunan, China.

ABSTRACT
Emergency evacuation aims to transport people from dangerous places to safe shelters as quickly as possible. Police play an important role in the evacuation process, as they can handle traffic accidents immediately and help people move smoothly on roads. This paper investigates an evacuation routing problem that involves police resource allocation. We propose a novel k-th-shortest-path-based technique that uses explicit congestion control to optimize evacuation routing and police resource allocation. A nonlinear mixed-integer programming model is presented to formulate the problem. The model's objective is to minimize the overall evacuation clearance time. Two algorithms are given to solve the problem. The first one linearizes the original model and solves the linearized problem with CPLEX. The second one is a heuristic algorithm that uses a police resource utilization efficiency index to directly solve the original model. This police resource utilization efficiency index significantly aids in the evaluation of road links from an evacuation throughput perspective. The proposed algorithms are tested with a number of examples based on real data from cities of different sizes. The computational results show that the police resource utilization efficiency index is very helpful in finding near-optimal solutions. Additionally, comparing the performance of the heuristic algorithm and the linearization method by using randomly generated examples indicates that the efficiency of the heuristic algorithm is superior.

No MeSH data available.


Related in: MedlinePlus

The computing time of heuristic algorithm and the linearization method.
© Copyright Policy
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC4520475&req=5

pone.0131962.g004: The computing time of heuristic algorithm and the linearization method.

Mentions: Random experiments provide more insights into the effect of network size on the two methods over a large number of experiments. We generated random transportation networks and randomly set up the parameters (see S2 Dataset). Then, two methods were tested based on the random data. Results of the random experiments are shown in Figs 4 and 5.


K-Shortest-Path-Based Evacuation Routing with Police Resource Allocation in City Transportation Networks.

He Y, Liu Z, Shi J, Wang Y, Zhang J, Liu J - PLoS ONE (2015)

The computing time of heuristic algorithm and the linearization method.
© Copyright Policy
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC4520475&req=5

pone.0131962.g004: The computing time of heuristic algorithm and the linearization method.
Mentions: Random experiments provide more insights into the effect of network size on the two methods over a large number of experiments. We generated random transportation networks and randomly set up the parameters (see S2 Dataset). Then, two methods were tested based on the random data. Results of the random experiments are shown in Figs 4 and 5.

Bottom Line: The proposed algorithms are tested with a number of examples based on real data from cities of different sizes.The computational results show that the police resource utilization efficiency index is very helpful in finding near-optimal solutions.Additionally, comparing the performance of the heuristic algorithm and the linearization method by using randomly generated examples indicates that the efficiency of the heuristic algorithm is superior.

View Article: PubMed Central - PubMed

Affiliation: Science and Technology on Information Systems Engineering Laboratory, National University of Defense Technology, Changsha, Hunan, China.

ABSTRACT
Emergency evacuation aims to transport people from dangerous places to safe shelters as quickly as possible. Police play an important role in the evacuation process, as they can handle traffic accidents immediately and help people move smoothly on roads. This paper investigates an evacuation routing problem that involves police resource allocation. We propose a novel k-th-shortest-path-based technique that uses explicit congestion control to optimize evacuation routing and police resource allocation. A nonlinear mixed-integer programming model is presented to formulate the problem. The model's objective is to minimize the overall evacuation clearance time. Two algorithms are given to solve the problem. The first one linearizes the original model and solves the linearized problem with CPLEX. The second one is a heuristic algorithm that uses a police resource utilization efficiency index to directly solve the original model. This police resource utilization efficiency index significantly aids in the evaluation of road links from an evacuation throughput perspective. The proposed algorithms are tested with a number of examples based on real data from cities of different sizes. The computational results show that the police resource utilization efficiency index is very helpful in finding near-optimal solutions. Additionally, comparing the performance of the heuristic algorithm and the linearization method by using randomly generated examples indicates that the efficiency of the heuristic algorithm is superior.

No MeSH data available.


Related in: MedlinePlus