How Keolis Santé improves patient transport efficiency with Hexaly

Customer stories Transportation Routing

Léa Optimization Scientist June 10, 2024

Keolis Santé is a French company specializing in patient transport. It aims at tackling the challenges of medical transportation in France and innovating in the service of patient mobility. Keolis Santé is part of the Keolis Group, one of the leaders in the shared mobility market around the world.

Medical transport is increasingly important in ensuring access to care for patients unable to travel independently. The patient transport business comprises many aspects in which optimization needs can arise. For example, it could benefit from optimized vehicle routes, improved and more reliable access to patient care, and improved working conditions for ambulance drivers thanks to more predictable schedules. This case study focuses on the operational planning of non-emergency patient transport carried out the following day, a challenging optimization problem whose resolution Keolis Santé chose to entrust to Hexaly.

Keolis Santé’s patient transport problem

The patient transport services considered here are provided by approved taxis and non-emergency medical vehicles. Unlike emergency ambulance services, these missions are easily predictable one day in advance. It is then possible to plan and optimize the affectation of patients to vehicles and drivers and the routes driven by each vehicle for the following day.

A Dial-A-Ride Problem

The problem consists in assigning vehicles to employees and creating mission rounds for each employee. The underlying optimization problem is related to the Dial-A-Ride Problem. Indeed, one of the key features of non-emergency patient transport is the possibility of transporting several people in the same vehicle at the same time. Shared rides can be highly cost-efficient, for example, when missions have origins or destinations in the same area. Several kinds of constraints apply to shared and simultaneous rides. For example, the number of patients simultaneously present in the same vehicle cannot exceed a certain limit. There are also constraints on the duration of the resulting detours and compliance with the mission’s time windows.

Complex regulation constraints

For non-emergency patient transport missions, vehicles are driven by a single employee. There are several vehicle depots: each vehicle starts and ends its tour at its assigned depot. Some missions require specific vehicle characteristics or employee skills and, therefore, result in additional compatibility constraints in the model.

Employees’ schedules are also subject to numerous contractual and regulatory constraints, such as breaks. Indeed, regulations in the field of patient transport in France require employees to take meal breaks within given time windows and regulatory breaks to avoid long working periods. These constraints are very complex and make the problem much harder to solve than a regular Dial-A-Ride Problem.

Resolution using Hexaly Optimizer

Keolis Santé’s patient transport problem comprises many constraints that are hard to satisfy. To ensure feasibility, the model relies on Hexaly Optimizer‘s ability to lexicographically optimize several objectives. Thanks to this feature, the fulfillment of mission, employee, and vehicle constraints can be turned into soft constraints. This ensures that the solver always provides the user with a schedule including all the missions. For example, when a punctual imbalance between workload and available resources makes it impossible to respect all the constraints, the solver returns a solution minimizing constraint violations.

A typical instance of the problem corresponds to a geographical sector of about one or two French departments. A sector then represents a daily volume of 500 missions to be planned, with around 50 employees and vehicles available. For such an instance, Hexaly Optimizer offers near-optimal solutions in only five minutes of computation, allowing the users to rerun the optimization process in real time to adapt to possible changes in demand and resources.

Why Hexaly?

The Keolis Santé team was particularly convinced by Hexaly’s ability to carry out every aspect of the project, from the resolution of the problem to the visualization of the optimized solution in an easy-to-use web application. They were very satisfied with the solver’s performance, both in terms of solution quality and resolution speed. They also greatly appreciated the flexibility of the web application, enabling them to fine-tune parameters and constraints to adapt to the specifications of each region. In particular, users can impose certain decisions on the optimization engine to allow for “human constraints” that cannot be mathematically modeled.

The optimization tool developed by Hexaly brought significant gains to the Keolis Santé team as soon as they started using it in production. The quality of the employee schedules and vehicle tours has improved in terms of revenue per hour, percentage of shared rides, and distance traveled with patients on board. The tool also enabled substantial organizational changes. Indeed, the schedules are now computed very quickly, saving 4 to 6 hours of manual computation in each regulation center. Dispatchers can then instead focus on adjustments to address last-minute incidents and contingencies. The drivers’ working conditions have also improved as they have better visibility of their work hours.

The optimization engine helps us complete our patient transport missions more efficiently. Not only does it provide excellent quality schedules, but it also saves us a lot of time that we can then dedicate to other high-value-added tasks. It even helps us carry out tactical reasoning and better plan our resource management in the medium term.

Adnane Kassamaly Chief Digital Officer, Keolis Sante

Please look at our customers’ webpage to discover more industry case studies.