Efficient Routing of Emergency Vehicles under Uncertain Urban Traffic Conditions
- 1 Department of Management, Bar-Ilan University, Ramat Gan, Israel.
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.
- 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
- 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. doi:10.1016/0022-247X(66)90009-6
- 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. doi:10.1145/321921.321934
- 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
- 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