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

Transportation road network of Oldenburg, Germany.
© Copyright Policy
Related In: Results  -  Collection

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

pone.0131962.g003: Transportation road network of Oldenburg, Germany.

Mentions: In this section, we tested the performance of the two ERPRA solution algorithms on different datasets. Some of the datasets are based on the real transportation network of Changsha, China, as shown in Fig 2 (the original GIS data is from openstreetmap.org [43]). Other datasets are based on the subnet of the road network of Oldenburg, Germany, as shown in Fig 3 [44]. Specifically, (1) geographical information, such as the number (N) and length of the roads, is calculated by a commercial GIS software, ArcGIS, based on the data of the two cities; (2) k-th shortest paths parameters, such as tijk and αlijk, are derived during preprocess using mature methods [9–11] based on geographical information; (3) other related parameters, including ei, vj, λi, , ul, wl, pl, rl, cl, and B, are randomly generated (See S1 Dataset). Randomly generated transportation networks (See S2 Dataset) were also used to test the performance of the two algorithms. The unit of objective value is a unit time, but comparing the objective value across network scales is meaningless due to random parameters of different networks. The algorithms were coded in MATLAB by invoking CPLEX Optimizer v12.6. We executed the programs on a 32-bit Windows 7 computer with a 2.1GHz Duo core CPU and 1.0 GB of physical RAM.


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)

Transportation road network of Oldenburg, Germany.
© Copyright Policy
Related In: Results  -  Collection

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

pone.0131962.g003: Transportation road network of Oldenburg, Germany.
Mentions: In this section, we tested the performance of the two ERPRA solution algorithms on different datasets. Some of the datasets are based on the real transportation network of Changsha, China, as shown in Fig 2 (the original GIS data is from openstreetmap.org [43]). Other datasets are based on the subnet of the road network of Oldenburg, Germany, as shown in Fig 3 [44]. Specifically, (1) geographical information, such as the number (N) and length of the roads, is calculated by a commercial GIS software, ArcGIS, based on the data of the two cities; (2) k-th shortest paths parameters, such as tijk and αlijk, are derived during preprocess using mature methods [9–11] based on geographical information; (3) other related parameters, including ei, vj, λi, , ul, wl, pl, rl, cl, and B, are randomly generated (See S1 Dataset). Randomly generated transportation networks (See S2 Dataset) were also used to test the performance of the two algorithms. The unit of objective value is a unit time, but comparing the objective value across network scales is meaningless due to random parameters of different networks. The algorithms were coded in MATLAB by invoking CPLEX Optimizer v12.6. We executed the programs on a 32-bit Windows 7 computer with a 2.1GHz Duo core CPU and 1.0 GB of physical RAM.

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