Patient Scheduler Knowledge Source

The purpose of the Patient Scheduler knowledge source is to find feasible routes for patients and to schedule them, producing patient itineraries. The Patient Scheduler allocates patients to existing missions, ASFs, and MTFs by searching for feasible routes in the airport/mission-leg network (described earlier).

This knowledge source uses a specialization of DITOPS' beam search algorithm to perform a geographical search of feasible routes and potential destinations. At any particular airport, the search tree is expanded to those airports which are targeted by a temporally feasible mission leg. Each destination is checked for the existence of the required medical facility and a check is also made that to verify if the destination is not already part of the patient's itinerary, to avoid ``loops.'' If the patient's itinerary exceeds a certain number of hours, a rest-over-night using an ASF is added to the itinerary. When an airfield with the required medical facility is reached, a medical treatment operation using the MTF facility is added to the patient's itinerary. The search can be parametrized by defining the beam width, the maximum accepted number of legs in a patient's itinerary, and the maximum number of hours an itinerary may have. If a search tree violates some of these limits or if there are no missions that can satisfy the patient's requirement the search will fail and return no itinerary for a patient. In this case, a one leg mission taking the patient from his origin to a destination with the required medical specialty will be added. If the patient requires a medical specialty that cannot be satisfied by any of the available hospitals, the patient will not be allocated and an error message will be issued.

The search is guided by a heuristic evaluation function that uses a weighted combination of several different user-defined preferences. In the examples we created, we were using preferences that minimize:

Travel time:

the number of hours from the ready date to the arrival at the hospital.

Number of legs:

total number of connections and rest overnight.

Arrival time:

the time the patient arrives to the medical facility.

Departure time:

the time of the first flight since the patient is ready.

The relative importance of these evaluation function components is configurable by the user and can be changed dynamically according to the evolving situation.

The search algorithm can be described as:

1. Initialization: Set ORIGIN, START-TIME and MEDICAL-SPECIALTY to the origin, ready-date and medical specialty required by the patient respectively. Add ORIGIN to ITINERARY.
2.   IF ORIGIN has hospital with MEDICAL-SPECIALTY, reserve hospital and return ITINERARY. By reserve hospital we mean create a medical-treatment operation that reserves the hospital for the patient.
3. ELSE IF flying-time > MAX-FLYING-TIME or number-of-legs > MAX-NUMBER-OF-LEGS return EMPTY. MAX-FLYING-TIME is the maximum total flying time allowed and MAX-NUMBER-OF-LEGS is the maximum number of legs allowed in a patient's itinerary.
4. ELSE IF flying-time > MAX-HOURS-BEFORE-RON, reserve ASF and add rest-over-night operation to ITINERARY. MAX-HOURS-BEFORE-RON is the maximum time a patient can fly before she/he needs to rest for a certain period of time in an ASF facility.
5. ELSE set LEGS to the set of all legs leaving ORIGIN such that leg-start-time START-TIME and the leg destination is not part of ITINERARY.
   1. IF LEGS is not empty
      1. Set ORIGIN to the leg destination
      2. Set START-TIME to the leg end-time.
      3. Add ORIGIN to ITINERARY
      4. GOTO step 2
   2. ELSE return EMPTY
6. If search returned EMPTY do:
   1. Create a new one leg mission going from patient origin to the closer airfield that has an MTF with the required medical specialty.
   2. Set ORIGIN to the destination of the added mission.
   3. Add ORIGIN to ITINERARY
   4. GOTO step 2

The algorithm described above will take any origin and any medical specialty and will always find a feasible itinerary provided there is at least one MTF with the required medical specialty. As a consequence of this, the same algorithm can be used in the generative and reactive case.

In the reactive case, we assume there is an inconsistency in the patient's itinerary. This inconsistency can be overlapping legs, a missing MTF, or gaps in the sequence of destinations. The analysis method verifies the patient's itinerary and identifies the consistent part of it if there is any. The Patient Scheduler removes the inconsistent part, maybe the complete itinerary, and generates a new consistent itinerary from the last reachable destination.

The automatic addition of missions is a feature that is not always desired since the system assumes that resources are available and that missions can be created at any time. To overcome this problem, after the system finishes scheduling, it is possible to inspect and cancel all automatically added missions. When canceling added missions, all the patients allocated on that missions will be completely unscheduled. The user can then add new missions and try to allocate the now unscheduled patients. The system also provides the feature of unscheduling patients one at a time, unscheduling all late patients, or unscheduling all patients.