Ambulance Routing - Emergency Service and Dial-a-ride

Many emergency service providers (e.g., ambulance departments, police, fire departments) and companies who provide non-public maintenance services meet the problem that their fleet of vehicles has to provide three different types of services: 1) Cover a certain region and be prepared for an emergency case. 2) Provide immediate service in an emergency case 3) Provide some regular service (e.g.: dial-a-ride problems -- the pick-up and delivery of patients, predetermined service tasks, periodic pick-ups). In most cases the fleets are heterogeneous and some services can only be provided by specialized vehicles or workers. From the perspective of managing the regular services the objective is minimizing the total travelling distance subject to certain restrictions (e.g. be on time, use the appropriate vehicle, ..). Two types of the transportation services, emergency services as well as regular dial-a-ride services, have to be realized with one fleet. Therefore, specific dynamic aspects influence the schedule for the regular service. When an emergency occurs, the vehicle with the shortest distance to the emergency site is assigned to serve the emergency patient. Often, an ambulance vehicle which should carry out a scheduled transport order, which is not started yet, is rescheduled to serve the emergency patient and another vehicle has to be reassigned to the regular patient. The ambulance vehicle will become available at the hospital after the emergency service. Then it can be used to carry out regular transport orders. Also in this case the schedule for the regular services has to be reoptimized. Besides the constraints in classical Dial-a-Ride Problems we have the following features of our problem: 1) different (hard as well as soft) time constraint types. - e.g. dialysis patients must arrive exactly on time because the dialysis machine is reserved. Other patients only have to arrive within a very wide time window - when the walk- in clinic is open. 2) Heterogeneous fleet - We deal with a heterogeneous fleet concerning capacities of the vehicles and concerning the different available equipment on the vehicles. 3) Dynamic aspects - Some orders are known in advance - because there are a certain percentage of orders which are periodical transport orders. Some patients have regular treatments a number of times per week. A certain percentage of orders arrive in real-time. Furthermore, the vehicle availability changes dynamically. The reason is the disappearance and reappearance of vehicles (emergency requests are serviced with the same fleet). 4) Stochastic aspects - Expected return transport orders (relatively long planning horizon), expected availability of vehicles, expected transport orders (relatively short planning horizon, in some cases emergencies occur and most probably additional vehicles are required.) As solid basis of this project we have studied different types of deterministic routing problems within the context of predecessor projects (partly supported by the OENB under grant 8630). In particular, we have developed competitive "ant colony optimization" and "variable neighbourhood search" algorithms. This experience shall be used to develop powerful algorithms for dial-a-ride problems with additional realistic aspects (dynamic, stochastic). From the software engineering point of view we develop a fully integrated decision support tool for the control center, which provides decision support in real-time. To reach this objective a standardized data model is developed. Moreover the standardized environment enables the solution of different generalizations of the classical Vehicle Routing Problem with different algorithms and using real-world data of geographic information systems. From the operations research and logistics point of view we solve a real-world problem with different (rich) constraints, dynamic aspects and stochastic aspects. To our best knowledge this type of problem especially the appearance and disappearance of vehicles and the usage of information concerning expected transport orders has not been addressed for the DARPs so far.