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 line graph of accidents probabilities coefficients and gap.
© Copyright Policy
Related In: Results  -  Collection

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

pone.0131962.g006: The line graph of accidents probabilities coefficients and gap.

Mentions: Fig 6 presents the trends in gap between the two methods while traffic accident probabilities increase. When the coefficient is less than 1, the gaps are all below 0.3%. After peaking at 1.1 (where the gap is 1.7%), the gap tapers off to approximately 1%. Eventually, the gap falls back to approximately 0.25%. Although that gap is still acceptable, the fluctuation is relatively large. An increasing coefficient indicates that the capacity of the roads is decreasing and that the number of bottlenecks might soar. Considering the sequential nature of the police allocation used by the heuristic method, a bad choice of deployment in an iteration might lead to a slip into a local optimum solution. The heuristic method might be not useful for solving a problem with numerous bottlenecks.


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 line graph of accidents probabilities coefficients and gap.
© Copyright Policy
Related In: Results  -  Collection

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

pone.0131962.g006: The line graph of accidents probabilities coefficients and gap.
Mentions: Fig 6 presents the trends in gap between the two methods while traffic accident probabilities increase. When the coefficient is less than 1, the gaps are all below 0.3%. After peaking at 1.1 (where the gap is 1.7%), the gap tapers off to approximately 1%. Eventually, the gap falls back to approximately 0.25%. Although that gap is still acceptable, the fluctuation is relatively large. An increasing coefficient indicates that the capacity of the roads is decreasing and that the number of bottlenecks might soar. Considering the sequential nature of the police allocation used by the heuristic method, a bad choice of deployment in an iteration might lead to a slip into a local optimum solution. The heuristic method might be not useful for solving a problem with numerous bottlenecks.

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