Online Dispatching and Routing Model for Emergency Vehicles with Area Coverage Constraints

Abstract

Response time plays a crucial role in reducing the loss of assets and lives caused by emergencies. Good dispatch strategies for emergency response vehicles result in more efficient service, and route guidance can help reduce vehicles’ travel times. Because of a limited number and type of emergency response vehicles at each station, service area gaps will be created: they cannot be properly covered by the remaining emergency response vehicles when some vehicles are dispatched. Future emergency calls in these areas may experience longer response times than usual. In this paper, an optimization model is developed that, given real-time traffic information, can assist dispatchers of emergency response vehicle in assigning multiple emergency response vehicles to incidents and in determining the routes that avoid congestion spots in the transportation networks. This model accounts for the service area coverage concerns (when several vehicles are busy) by relocation and redistribution of the remaining vehicles among stations. The results show that coordination of different types of vehicles, relocation of vehicles for better area coverage, and use of a time-dependent shortest path algorithm in this model significantly improve the performance of the emergency response system.

Get full access to this article

View all access options for this article.

References

Cote

A. E.

Fire Protection Handbook (18th Ed.). National Fire Protection Association, Quincy, Mass., 1997.

Tian

and Haghani

An Optimization Model for Real-Time Emergency Vehicle Dispatching and Routing. Presented at 82nd Annual Meeting of the Transportation Research Board, Washington, D.C., 2003.

Fisher

Jaikumar

L. R.

and Wassenhove

L. N.

A Multiplier Adjustment Method for the Generalized Assignment Problems. Management Science, Vol. 32, 1986, pp. 1095–1103.

Martello

Pulleyblank

W. R.

Toth

and de Werra

Balanced Optimization Problems. Operations Research Letters, Vol. 3, 1984, pp. 275–278.

Ross

G. T.

and Soland

M. S.

A Branch and Bound Algorithm for the Generalized Assignment Problem. Mathematical Programming, Vol. 8, 1975, pp. 91–103.

Burkard

and Cela

Linear Assignment Problems and Extensions, 1998. sherry.ifi.unizh.ch/burkard98linear.html. Accessed Dec. 2003.

Osman

I. H.

Heuristics for the Generalized Assignment Problem, Simulated Annealing and Tabu Search Approaches. OR Spectrum, Vol. 17, 1995, pp. 221–225.

Lorena

Narciso

M. G.

and Beasley

J. E.

A Constructive Genetic Algorithm for the Generalized Assignment Problem. 2002. www.lac.inpe.br/∼marcos/arsig2/cga_revised.pdf. Accessed Feb. 2004.

Chu

P. C.

and Beasley

J. E.

A Genetic Algorithm for the Generalized Assignment Problem. Camp Operations Research, Vol. 24, No. 1 1997, pp. 17–23.

10.

Pierskalla

W. P.

The Tri-substitution Method for the Three-Multidimensional Assignment Problem. Canadian ORS Journal, Vol. 5, 1967, pp. 71–81.

11.

Balas

and Saltzman

M. J.

An Algorithm for the Three-Index Assignment Problem. Operations Research, Vol. 39, 1991, pp. 150–161.

12.

Burkard

R. W.

Rudolf

and Woeginger

G. J.

Three-Dimensional Axial Assignment Problems with Decomposable Cost Coefficients. Discrete Applied Mathematics, Vol. 65, 1996, pp. 123–139.

13.

Hakimi

Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph. Operations Research, Vol. 12, 1964, pp. 450–459.

14.

Daskin

and Stern

E. H.

A Hierarchical Objective Set Covering Model for Emergency Medical Service Vehicle Deployment. Transportation Science, Vol. 15, 1981, pp. 137–152.

15.

Pirkul

and Schilling

D. A.

The Siting of Emergency Service Facilities with Workload Capacities and Backup Service. Management Science, Vol. 34, No. 7 1988, pp. 896–908.

16.

ReVelle

and Hogan

A Reliability-Constrained Siting Model with Local Estimates of Busy Fractions. Environment and Planning B: Planning and Design, Vol. 15, 1988, pp. 143–152.

17.

ReVelle

Extension and Prediction in Emergency Service Siting Models. European Journal of Operational Research, Vol. 40, 1989, pp. 58–69.

18.

ReVelle

A Perspective on Location Science. Location Science, Vol. 5, No. 1 1997, pp. 3–13.

19.

Ziliaskopoulos

and Mahmassani

Time Dependent, Shortest-Path Algorithm for Real-Time Intelligent Vehicle Highway System Applications. In Transportation Research Record 1408, TRB, National Research Council, Washington, D.C., 1993, pp. 94–100.