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.
Cite this paper
A. Elalouf, "Efficient Routing of Emergency Vehicles under Uncertain Urban Traffic Conditions," Journal of Service Science and Management, Vol. 5 No. 3, 2012, pp. 241-248. doi: 10.4236/jssm.2012.53029.
 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.
 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
 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
 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.
 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.
 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
 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.
 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
 S. Sahni, “Algorithms for Scheduling Independent Tasks,” Journal of the ACM, Vol. 23, No. 1, 1976, pp. 116-127.
 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.
 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.
 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
 T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, “Introduction to Algorithms,” MIT Press, Cambridge, 2001.
 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.
 R. Gibson and E. Schuyler, “Google Maps Hacks: Tips & Tools for Geographic Searching and Remixing (Hacks),” O’Reilly Media, Inc., 2006
 A. Brooke, D. Kendrick and A. Meeraus, “GAMS: A User’s Guide,” The Scientific Press, Redwood City, 1998.
 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.
 M. Pinedo, “Scheduling: Theory, Algorithms, and Systems,” Prentice Hall, Englewood Cliffs, 1995.
 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.
 A. D. Klose, “Facility Location Models for Distribution System Design,” European Journal of Operational Research, Vol. 162, No. 1, 2005, pp. 4-29.