Real-time management of intra-hospital patient transport requests.

This paper addresses the management of patients' transportation requests within a hospital, a very challenging problem where requests must be scheduled among the available porters so that patients arrive at their destination timely and the resources invested in patient transport are kept as low as possible. Transportation requests arrive during the day in an unpredictable manner, so they need to be scheduled in real-time. To ensure that the requests are scheduled in the best possible manner, one should also reconsider the decisions made on pending requests that have not yet been completed, a process that will be referred to as rescheduling. This paper proposes several policies to trigger and execute the rescheduling of pending requests and three approaches (a mathematical formulation, a constructive heuristic, and a local search heuristic) to solve each rescheduling problem. A simulation tool is proposed to assess the performance of the rescheduling strategies and the proposed scheduling methods to tackle instances inspired by a real mid-size hospital. Compared to a heuristic that mimics the way requests are currently handled in our partner hospital, the best combination of scheduling method and rescheduling strategy produces an average 5.7 minutes reduction in response time and a 13% reduction in the percentage of late requests. Furthermore, since the total distance walked by porters is substantially reduced, our experiments demonstrate that it is possible to reduce the number of porters - and therefore the operating costs - without reducing the current level of service.