Rescue vehicle allocation problem based on optimal reliable path under uncertainty

Abstract

Consideration of the travel time variation for rescue vehicles is significant in the field of emergency management research. Because of uncertain factors, such as the weather or OD (origin-destination) variations caused by traffic accidents, travel time is a random variable. In emergency situations, it is particularly necessary to determine the optimal reliable route of rescue vehicles from the perspective of uncertainty. This paper first proposes an optimal reliable path finding (ORPF) model for rescue vehicles, which considers the uncertainties of travel time, and link correlations. On this basis, it investigates how to optimize rescue vehicle allocation to minimize rescue time, taking into account travel time reliability under uncertain conditions. Because of the non-additive property of the objective function, this paper adopts a heuristic algorithm based on the K-shortest path algorithm, and inequality techniques to tackle the proposed modified integer programming model. Finally, the numerical experiments are presented to verify the accuracy and effectiveness of the proposed model and algorithm. The results show that ignoring travel time reliability may lead to an over- or under-estimation of the effective travel time of rescue vehicles on a particular path, and thereby an incorrect allocation scheme.

Keywords

heuristic algorithm / travel time correlation / optimal reliable path / rescue vehicle allocation / traffic network

References

[1] HuangH-J, LamW H K. Modeling and solving the dynamic user equilibrium route and departure time choice problem in network with queues [J]. Transportation Research Part B, 2002, 36(3): 253-273

[2] SunS-C, DuanZ-Y, YangD-Y. Optimal paths planning in dynamic transportation networks with random link travel times [J]. Journal of Central South University, 2014, 21(4): 1616-1623

[3] ZhangW-Y, GuanW, SongL-Y, et al. . Alpha-reliable combined mean traffic equilibrium model with stochastic travel times [J]. Journal of Central South University, 2013, 20(12): 3770-3778

[4] ShenL, ShaoH, WuT, et al. . An energy-efficient reliable path finding algorithm for stochastic road networks with electric vehicles [J]. Transportation Research Part C, 2019, 102: 450-473

[5] ShenL, ShaoH, WuT, et al. . Finding the reliable shortest path with correlated link travel times in signalized traffic networks under uncertainty [J]. Transportation Research Part E, 2020, 144: 102159

[6] HanF, ZhaoX-M, ChengL. Traffic assignment problem under tradable credit scheme in a bimodal stochastic transportation network: A cumulative prospect theory approach [J]. Journal of Central South University, 2020, 27(1): 180-197

[7] YangZ-Z, GaoZ-Y. Finding reliable paths considering the earliest arrival time and the latest departure time with 3-parameter lognormal travel times [J]. IEEE Transactions on Vehicular Technology, 2020, 69(10): 10457-10468

[8] BarrachinaJ, GarridoP, FogueM, et al. . Reducing emergency services arrival time by using vehicular communications and evolution strategies [J]. Expert Systems with Applications, 2014, 41(4): 1206-1217

[9] ChenY-Z, ShenS-F, ChenT, et al. . Path optimization study for vehicles evacuation based on dijkstra algorithm [J]. Procedia Engineering, 2014, 71159-165

[10] ZhaoJ-D, GuoY-J, DuanX-H. Dynamic path planning of emergency vehicles based on travel time prediction [J]. Journal of Advanced Transportation, 2017, 2017: 9184891

[11] ZengZ-L, YiW, WangS-A, et al. . Emergency vehicle routing in urban road networks with multistakeholder cooperation [J]. Journal of Transportation Engineering Part A-Systems, 2021, 147(10): 04021064

[12] MinW-L, YuL, ChenP, et al. . On-demand greenwave for emergency vehicles in a time-varying road network with uncertainties [J]. IEEE Transactions on Intelligent Transportation Systems, 2020, 2173056-3068

[13] LiQ-P, TuW, ZhuoL. Reliable rescue routing optimization for urban emergency logistics under travel time uncertainty [J]. ISPRS International Journal of Geo-Information, 2018, 7(2): 77

[14] ZhangZ-H, HeQ, GouJ-Z, et al. . Analyzing travel time reliability and its influential factors of emergency vehicles with generalized extreme value theory [J]. Journal of Intelligent Transportation Systems, 2019, 2311-11

[15] ChenB-Y, LamW H K, SumaleeA, et al. . Finding reliable shortest paths in road networks under uncertainty [J]. Networks and Spatial Economics, 2013, 13(2): 123-148

[16] ZhangW-Y, GuanW, FanL-L. A self-regulating pairwise swapping algorithm to search reliability-based user equilibrium [J]. Journal of Central South University, 2018, 25(8): 2002-2013

[17] YanD-M, GuoJ-H. A stochastic user equilibrium model solving overlapping path and perfectly rational issues [J]. Journal of Central South University, 2021, 28(5): 1584-1600

[18] LiY-L, ChungS H. Disaster relief routing under uncertainty: A robust optimization approach [J]. IISE Transactions, 2019, 51(8): 869-886

[19] ZhangY-L, ShenZ J M, SongS-J. Lagrangian relaxation for the reliable shortest path problem with correlated link travel times [J]. Transportation Research Part B, 2017, 104501-521

[20] ZhengF-F, LiJ, van ZuylenH, et al. . Urban travel time reliability at different traffic conditions [J]. Journal of Intelligent Transportation Systems, 2018, 22(2): 106-120

[21] HallR W. Travel outcome and performance: The effect of uncertainty on accessibility [J]. Transportation Research Part B, 1983, 17(4): 275-290

[22] YinY-F, IedaH. Assessing performance reliability of road networks under nonrecurrent congestion [J]. Transportation Research Record, 2001, 1771: 148-155

[23] HencheyM J, BattaR, BlattA, et al. . A study of situationally aware routing for emergency responders [J]. Journal of the Operational Research Society, 2015, 66(4): 570-578

[24] MondalS, GuptaA. Speed distribution for interrupted flow facility under mixed traffic [J]. Physica A, 2021, 570: 125798

[25] WangW, WuY-W. Is uncertainty always bad for the performance of transportation systems? [J]. Communications in Transportation Research, 2021, 1100021

[26] WuJ-M, KulcsárB, AhnS, et al. . Emergency vehicle lane pre-clearing: From microscopic cooperation to routing decision making [J]. Transportation Research Part B, 2020, 141223-239