Patient transport scheduling system goes live at Ornge

The province of Ontario is about the size of France and Spain combined.  Medical transport throughout the province is provided by Ornge, a nonprofit organization employing 8 helicopters, 24 fixed wing aircraft (of which 20 are available on contract), 3 critical care transfer units on land, and more than 400 paramedics, physicians and others to get patients to and from medical treatment centers. On an average day Ornge flies or drives more than 10,000 miles to transport patients, and each year Ornge transports more than 20,000 patients. 

Since 2007 ORIE has worked with Ornge on a series of Master of Engineering (M. Eng.) projects to help them improve the logistics of the service.  After an early project focused on the basing of helicopters to be dispatched for emergencies, work shifted to the daily task of scheduling the non-emergency medical transport planned for the following day.  Now a full-fledged system, developed through ORIE efforts, is in its final testing phase before being rolled out for routine use, to optimize routes on a daily basis.

The Flight Planning Optimization Tool developed by ORIE in partnership with Ornge uses OR modeling as the basis for developing daily schedules from financial and aviation data.  Doing so involves solving a challenging optimization problem: to find the best routes for aircraft, some of which can carry two patients, escorts or family members, and to determine the sequence of pickups and dropoffs along the way.   

M.Eng. and Ph.D. Students Spearhead the Effort

Using results from an M. Eng. project that supplied proof of concept, then-Ph.D. student Tim Carnes first redeveloped the code to make it run quickly.  He came up with a clever way of enumerating possible routes in order to efficiently construct an auxiliary optimization problem that can be solved, using commercial software, to obtain the desired optimal schedule. "This made it conceivable for the first time to compute solutions to the scheduling problem that Ornge faces daily," according to Henderson. 

A follow-on M. Eng.project refined the cost data, after which computer science Ph.D. student Alex Fix added features to make the system more realistic (such as avoiding the transport of multiple patients when one of them is infectious) in order to put the system into production at the Ornge headquarters near Toronto. 

Carnes and Professors David Shmoys and Shane Henderson have worked together in advising the M. Eng. medical transport projects.  The Ornge project lead is Dr. Russell MacDonald, Medical Director for R&D and an Associate Professor at the University of Toronto. Mahvareh Ahghari is the Ornge project supervisor.  Together MacDonald and Ahghari identify problems, propose potential projects, guide the work from an operational perspective, and then help lead implementation of the finished project at Ornge. 

Carnes, now a post doctoral fellow at MIT, incorporated some of the results of his work with Ornge in his Ph.D. thesis.   He was a finalist in the INFORMS George Nicholson Student Paper competition for a paper, based on this part of his thesis, that deals with both the daily planning problem for Ornge as well as further work on a longer term problem that is also of interest to Ornge.

Significant Results

According to Dr. MacDonald, "our very conservative estimates suggest the tool will yield annual 6-figure savings to our organization."  It also enables staff to plan routes and aircraft in minutes and not hours, saving time for the Ornge Communication Centre staff.  "Most importantly, it will improve the efficiency within our system, making aircraft and staff more readily available for patients with life-threatening emergencies."

Prior to development of the tool, the process of determining routes relied on the discretion of the flight planners, aided by software that finds the cheapest aircraft for a planned route.  Test runs of the new approach, using more than 30 sample days of historical data, reduced total travel distance by 12% and reduced the number of flight legs with no patients on board ("empty legs") by 21%, according to Ahghari.

Henderson, who has overseen the ORIE relationship with Ornge, says "it's been a great collaboration. They are great people to work with."  He sees potential for further improvement, including a new M.Eng. project -- fourth in the series -- being co-advised by Shmoys and Professor Mike Todd.  This project deals with impacts of disruptions in planned schedules due to weather or medical emergencies.  Airlines call doing so the "schedule repair problem" and use methods that may be transferable to scheduling for Ornge.  Since disruptions occur fairly often, a future extension might be to build that possibility into the initial schedules so as to facilitate schedule repairs as necessary. 

A Model Approach

Henderson sees the ORIE - Ornge relationship as a model for working with organizations.   In particular, he likes the idea of  "using the M. Eng. project approach to work with an organization and come up with a useful solution to a real problem they have --  while at the same time working in parallel with a Ph.D. student to develop new theory and a more advanced approach to a broader class of real problems  to which the organizations problem belongs."

MacDonald and Ahghari have written that "this project is a wonderful example of applying operations research theory in complicated real-world practices.  We started with a simplified model and gradually added layers of complexity through multiple projects, so now the current model meets the real-world requirements provides a tool with enormous value to Ornge.  The Cornell advisors have played an amazingly great role in this success by linking different projects and guiding the entire effort towards a final product."