Efficient Routing of Emergency Vehicles under Uncertain Urban Traffic Conditions

Amir Elalouf

Department of Management, Bar-Ilan University, Ramat Gan, Israel..

DOI: 10.4236/jssm.2012.53029                

Abstract

Emergency-vehicle drivers who aim to reach their destinations through the fastest possible routes cannot rely solely on expected average travel times. Instead, the drivers should combine this travel-time information with the characteristics of data variation and then select the best or optimal route. The problem can be formulated on a graph in which the origin point and destination point are given. To each arc in the graph a random variable is assigned, characterized by the expected time to traverse the arc and the variance of that time. The problem is then to minimize the total origin-destination expected time, subject to the constraint that the variance of the travel time does not exceed a given threshold. This paper proposes an exact pseudo-polynomial algorithm and an ε-approximation algorithm (so-called FPTAS) for this problem. The model and algorithms were tested using real-life data of travel times under uncertain urban traffic conditions and demonstrated favorable computational results.

Keywords

Fast Routing Algorithm; FPTAS; Dynamic Programming

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	C. Toregas, R. Swain, C. ReVelle and L. Bergman, “The Location of Emergency Service Facilities,” Operations Research, Vol. 19, No. 6, 1971, pp. 1363-1373. doi:10.1287/opre.19.6.1363
[2]	R. Larson, “A Hypercube Queuing Model for Facility Location and Redistricting in Urban Emergency Services,” Computers and Operations Research, Vol. 1, No. 1, 1974, pp. 67-95. doi:10.1016/0305-0548(74)90076-8
[3]	R. Larson, “Approximating the Performance of Urban Emergency Service Systems,” Operations Research, Vol. 23, No. 5, 1975, pp. 845-868. doi:10.1287/opre.23.5.845
[4]	K. Cooke and E. Halsey, “The Shortest Route through a Network with Time-Dependent Internodal Transit Times,” Journal of Mathematical Analysis and Applications, Vol. 14, No. 3, 1966, pp. 493-498. doi:10.1016/0022-247X(66)90009-6
[5]	A. Ziliaskopoulos and H. Mahmassani, “Time Dependent, Shortest-Path Algorithm for Real-Time Intelligent Vehicle Highway System Applications,” Transportation Research Record, Vol. 1408, 1993, pp. 94-100.
[6]	J. Goldberg and L. Paz, “Locating Emergency Vehicle Bases When Service Time Depends on Call Location,” Transportation Science, Vol. 28, No. 4, 1991, pp. 264280. doi:10.1287/trsc.25.4.264
[7]	M. Ben-Akiva, E. Cascetta and H. Gunn, “An On-Line Dynamic Traffic Prediction Model for an Inter-Urban Motorway Network,” In: N. H. Gartner and G. Improta, Eds., Urban Traffic Networks: Dynamic Flow Modeling and Control, Springer, Berlin, 1995, pp. 83-122.
[8]	Y. Hadas and A. Ceder, “Shortest Path of Emergency Vehicles under Uncertain Urban Traffic Conditions,” Transportation Research Record, Vol. 1560, No. 1, 1996, pp. 34-39. doi:10.3141/1560-06
[9]	S. Sahni, “Algorithms for Scheduling Independent Tasks,” Journal of the ACM, Vol. 23, No. 1, 1976, pp. 116-127. doi:10.1145/321921.321934
[10]	G. V. Gens and E. V. Levner, “Fast Approximation Algorithms for Job Sequencing with Deadlines,” Discrete Applied Mathematics, Vol. 3, No. 4, 1981, pp. 313-318. doi:10.1016/0166-218X(81)90008-1
[11]	E. Levner, A. Elalouf and T. C. E. Cheng, “An Improved FPTAS for Mobile Agent Routing with Time Constraints,” Journal of Universal Computer Science, Vol. 17, No. 13, 2011, pp. 1854-1862.
[12]	A. Elalouf, E. Levner and T.C.E Cheng, “Efficient Routing of Mobile Agents for Agent-Based Integrated Enterprise Management: A General Acceleration Technique,” Lecture Notes in Business Information Processing, Vol. 88, 2011, pp. 1-20. doi:10.1007/978-3-642-24175-8_1
[13]	T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, “Introduction to Algorithms,” MIT Press, Cambridge, 2001.
[14]	F. Ergun, R. Sinha and L. Zhang, “An Improved FPTAS for Restricted Shortest Path,” Information Processing Letters, Vol. 83, No. 5, 2002, pp. 287-291. doi:10.1016/S0020-0190(02)00205-3
[15]	R. Gibson and E. Schuyler, “Google Maps Hacks: Tips & Tools for Geographic Searching and Remixing (Hacks),” O’Reilly Media, Inc., 2006
[16]	A. Brooke, D. Kendrick and A. Meeraus, “GAMS: A User’s Guide,” The Scientific Press, Redwood City, 1998.
[17]	S. Andrews, H. Wang, D. Ni, S. Gao and J. Collura, “Development and Implementation of an Adapted Evacuation Planning Methodology in the Framework of Emergency Management and Disaster Response: A Case Study Using TransCAD,” Journal of Transportation and Security, Vol. 2, No. 4, 2010, pp. 352-368. doi:10.1080/19439962.2010.517743
[18]	M. Pinedo, “Scheduling: Theory, Algorithms, and Systems,” Prentice Hall, Englewood Cliffs, 1995.
[19]	J. R. Evans, “An Efficient Implementation of the WagnerWhitin Algorithm for Dynamic Lot-Sizing,” Journal of Operations Management, Vol. 5, No. 2, 1985, pp. 229-235. doi:10.1016/0272-6963(85)90009-9
[20]	A. D. Klose, “Facility Location Models for Distribution System Design,” European Journal of Operational Research, Vol. 162, No. 1, 2005, pp. 4-29. doi:10.1016/j.ejor.2003.10.031