Dynamic transportation of patients in hospitals

This study analyzes and solves a patient transportation problem arising in large hospitals. The aim is to provide an efficient and timely transport service to patients between several locations in a hospital campus. Transportation requests arrive in a dynamic fashion and the solution methodology must therefore be capable of quickly inserting new requests in the current vehicle routes. Contrary to standard dial-a-ride problems, the problem under study includes several complicating constraints which are specific to a hospital context. The study provides a detailed description of the problem and proposes a two-phase heuristic procedure capable of handling its many features. In the first phase a simple insertion scheme is used to generate a feasible solution, which is improved in the second phase with a tabu search algorithm. The heuristic procedure was extensively tested on real data provided by a German hospital. Results show that the algorithm is capable of handling the dynamic aspect of the problem and of providing high-quality solutions. In particular, it succeeded in reducing waiting times for patients while using fewer vehicles.