Henderson and Topaloglu Garner an NSF Grant for Emergency Services Improvement

In medical emergencies, minutes matter.  The closer the nearest available ambulance, the more quickly an accident, stroke or heart attack victim can get treatment. In 2001 the British Medical Journal showed that an additional 3000 heart attack victims in the UK could be saved each year if 90% of calls were dealt with in 8 minutes. 

But positioning ambulances in order to respond that quickly is a complex, dynamic problem - once an ambulance completes a run, the best place to send it next depends on the state of the system at the time, and the needs for service continue to evolve. It may even be worthwhile to relocate some ambulances that are not currently being dispatched to service so as to cover gaps in coverage resulting from the movement of those that are.

The National Science Foundation (NSF) has awarded ORIE Professors Shane Henderson and Huseyin Topaloglu a grant totalling nearly $300,000 to develop a new approach to optimizing ambulance deployment and similar problems arising in transportation logistics, supply chain management and revenue management. They propose to build links between two important classes of computational techniques so problems can be addressed through a combination of the two classes. 

One class of techniques, about which Topaloglu and his thesis advisor Warren Powell have written extensively, is known as approximate dynamic programming (ADP). Another class, simulation optimization (SO), has been a special interest of Henderson's. The primary goal of the research program is to "strengthen the links between ADP and SO and to exploit these links, primarily in the context of emergency-services systems," according to the proposal to the NSF.

"The ambulance folks are stretched thin, budget-wise," says Henderson.  Ambulance services in cities around the world currently  use a software package called Siren Predict  from Optima Corporation to simulate the arrival of emergency calls and help assess response scenarios, and Optima's Siren Live to make "re-deployment recommendations based on current vehicle locations and status, vehicle types, base/standby locations and status, staff shift information and call information.."

Henderson and Topaloglu hope to move their results to full implementation through their relationship with Optima, which was developed by a team at the University of Auckland, New Zealand, where Henderson got his undergraduate degree. "A channel to implementation helps keep things real," says Henderson.   A key step leading to the proposal to the NSF was the 'proof of concept' computer program developed by Mateo Restrepo, a Ph.D. student in Cornell's Center for Applied Mathematics from Colombia.

In addition to the joint grant with Huseyin, the National Science Foundation has also awarded a grant to a collaboration between Henderson and Professor Raghu Pasupathy of Virginia Tech that  focuses on the design, analysis and assessment of algorithms for simulation optimization. They hope to use statistical techniques in software that would figure out whether particular simulation problems have special structure that can be exploited in algorithms and to develop new measures of the efficiency of simulation algorithms.  The researchers propose to establish a libary of test problems to help evaluate and compare competing algorithms and drive further inquiry. The results of this research are expected to bear on the emergency services work that Henderson and Topaloglu propose to carry out under NSF auspices.  

The use of computer simulation for manufacturing and service industries was pioneered, among others, by emeritus ORIE faculty members Richard W. Conway and William L. Maxwell in the middle of the last century.  A given digital simulation run can answer 'what if' questions by yielding the cost and effectiveness of a particular set of decisions and policies in a complex and uncertain situation, for example the number and location of service agents such as ambulances and the rules for their redeployment in the course of the day. But determining 'how to' best operate, i.e. which set of decisions and policies is best, requires repeated simulation runs, typically through trial and error. Simulation optimization (SO) incorporates techniques that automatically use the output from completed simulation runs to determine which new set of decisions and policies should be tested by the next simulation run, essentially using the simulation runs as function evaluations in an optimization procedure. 

Approximate dynamic programming (ADP)  builds on the basic dynamic programming approach due to Richard Bellman that has been known for more than 50 years. This basic approach works well on problems that can be represented a sequence of states of a system that evolves over time as a result of decisions made at each state, the resulting transitions between states (which can have a random component), and the cost or benefit values for each state -- provided that the number of states is relatively small.  In this form, dynamic programming works by calculating backwards from the end of the time period and requires keeping track of the values for a substantial proportion of the possible states. 

As a result dynamic programming is subject to "the curse of dimensionality" as the number of possible states grows.  For the ambulance example, the number of variables required to specify the state of the system, including the outcomes of uncertain service demands and the range of possible decisions, soon renders basic dynamic programming impractical even on the fastest computers, not the least because it becomes impossible to efficiently record all of the possible states and their values (which measure, as a cost to be minimized,  the expected number of ambulance cases that are not reached within a specified time threshhold).  Powell, Topaloglu and others have proposed an alternative approach for dynamic programming  in which the ultimate values assigned to the nodes are approximated by limiting them to a particular functional form, such as a sum of terms depending only on certain attributes of the problem. 

Topaloglu points out that "ADP methods provide a lot of flexibility and power when attacking large-scale optimization problems that take place under uncertainty. However, there is no single ADP method that works for all problem classes. For the class to which the ambulance problem belongs, we first have to select the right ADP approach and then tweak it, probably quite a bit, to compute good answers quickly. During the course of this tweaking process, we expect to gain new theoretical and computation insights about ADP."

Both ADP and SO can be brought to bear on the problem of improving the ability of ambulance services to respond quickly to emergencies. By building on the strengths of each, Henderson and Topaloglu hope to "crack this problem," enabling the saving of lives while contributing insights to both operations research techniques.