Background: Efficient transport of non-emergency patients is crucial for ambulance service providers to cope with increased demand resulting from aging Western societies. This paper deals with the optimization of the patient transport operations of the Red Cross of Lower Austria, which is the main provider in this state. Different quality levels of the provided service - expressed by time windows, feasible maximum ride times and exclusive transports - are tested and analyzed on real-life instances to show daily impacts on the provider's resources. Comparisons of the developed solution approach to the recorded manual schedule prove its advantages. In contrast to previous work in this field, non-static service times that depend on the combination of patients, their transport mode, the vehicle type as well as the pickup or delivery locations are used. These service times are based on statistical analyses that have been performed on an anonymized dataset with more than 600,000 requests.
Methods: To solve the given problem, a matheuristic solution approach was developed that deals with the exact optimization of combinations of requests as a first stage. Subsequently, the identified combinations are used as an input into a Tabu Search strategy, where the vehicle routing is optimized. Three representative days of the year 2012 were chosen for the four regions of Lower Austria to test five different service levels and the quality of the solution method.
Results: For the standard scenario, the operation time of the manual schedule is reduced in the range from 14.1 % to 19.8 % for all tested instances. Even in the best service scenario, the matheuristic computes better results than the manual schedule. The service level has a high impact on the operation time of providers. The relative savings that are achieved by the algorithm are significantly lowered by introducing higher quality standards. The main reason is that less feasible combinations of patients can be generated. This leads to diminished opportunities for patients to be transported at the same time. The results indicate that the implementation of the developed matheuristic in daily planning decisions could decrease operation times significantly.
Conclusions: Managers have to define minimum standards for the punctuality, exclusive transports and excess ride times. This is crucial in order to find a suitable compromise between the service level and an optimized resource management.
Keywords: Ambulance service; Dial-a-ride problem; Matheuristic; Patient transport; Resource management; Service levels.