Improving the non-urgent sanitary transportation

Timothée Chane-Haï, Samuel Vercraene, Céline Robardet, Thibaud MonteiroICCAD 2023 · DOI

This paper, presented at ICCAD 2023, tackles a common logistical headache in healthcare: how to get patients to and from their appointments efficiently without making them spend their entire day in a van.

TL;DR

The authors introduce the Round-Trip Dial-A-Ride Problem (RT-DARP), a new optimization model that links a patient's morning and afternoon trips through a shared "maximum daily ride time" constraint. By solving these trips together using a specialized metaheuristic, they achieved an average cost reduction of 3.67% while ensuring a more equitable and higher quality of service for patients.

What Problem Does This Paper Address?

In non-urgent sanitary transportation (like shuttles for disabled children or the elderly), providers usually solve the "morning problem" and the "afternoon problem" separately. This is a standard Dial-A-Ride Problem (DARP).

However, this "siloed" approach has a major flaw: it ignores the cumulative experience of the user. A patient might get stuck in a long, circuitous route in the morning and another long route in the afternoon. While each trip might technically fall under a maximum limit, the total daily travel time becomes exhausting and unfair.

The authors aim to create a dependency between these two trips. If a patient has a long ride in the morning, the system should prioritize a shorter, more direct ride in the afternoon to stay within a total daily "time budget."

Methods

The researchers formulated this as a Mixed Integer Program (MIP) and developed a solution using a Small and Large Neighborhood Search (SLNS) metaheuristic.

  • The Model: The core innovation is the inclusion of a daily maximum ride time ($L_u$) for each user $u$. This links the decision variables of the morning routes to those of the afternoon routes.
  • The Algorithm (SLNS): Unlike a standard Large Neighborhood Search that chooses removal sizes randomly, SLNS focuses on many "small" iterations (removing just a few users) for fast intensification. It only triggers a "large" move (diversification) when the search hits a plateau.
  • Feasibility Speedups: Checking if a new stop can be added to a route is computationally expensive ($O(n^2)$). The authors developed a pre-processing procedure that calculates "ride time thresholds." If an afternoon trip is already long, the system instantly knows which morning detours are forbidden, allowing it to prune the search space much faster.

Datasets

Since the RT-DARP is a new variant, no standard benchmarks existed. The authors generated a new benchmark suite:

  • 24 Instances: Ranging from 100 to 400 users.
  • Spatial Layout: Pickup and drop-off locations are randomly distributed on a (-10, 10) grid.
  • Time Windows: Modeled after real-world scenarios, with morning drop-offs around 8:00 AM and afternoon pickups around 4:00 PM.
  • Comparison: They compared their RT-DARP results against a "2-DARP" approach (where morning and afternoon are solved independently).

Key Insights and Ideas

  • The "Trade-off" Effect: By linking the trips, the algorithm can "spend" a user's time budget where it is most efficient for the fleet. If one route is particularly crowded, the system can give a user a longer ride there, provided it compensates with a direct ride on their other trip.
  • Managerial Flexibility: The results show that the RT-DARP formulation allows providers to improve the Quality of Service (QoS) without increasing costs. Essentially, you can tighten the ride-time constraints for patients and still end up with a cheaper or equal-cost solution compared to the traditional independent modeling.
  • Fairness by Design: The shared constraint naturally prevents the "double-long-trip" scenario, leading to more equitable treatment of patients across the service area.

Key Results

  • Cost Savings: The RT-DARP formulation outperformed the separate 2-DARP approach in every single test case. On average, total transportation costs were reduced by 3.67%.
  • Peak Efficiency: In instances with 200 users and tight ride-time constraints, the cost reduction reached as high as 6.27%.
  • Better Service for Less: The data indicates that an RT-DARP schedule with a strict ride-time coefficient (1.4) costs roughly the same as a traditional 2-DARP schedule with a much looser coefficient (1.5). This means patients get home faster for the same operational price.

Limitations and Future Work

While the results are promising, the authors acknowledge a few areas for expansion:

  • Fleet Homogeneity: The current model assumes an infinite fleet of identical vehicles. Real-world medical transport often involves a mix of vehicles (e.g., those with wheelchair ramps vs. standard cars).
  • User Heterogeneity: The model doesn't yet account for specific patient needs, such as requiring a specific type of medical staff on board.
  • Real-World Validation: The next logical step is testing the RT-DARP on real-world data from providers like GIHP (the French transport company that inspired the study) to see how it handles unpredictable traffic and cancellations.

Summary updated

BibTeX
@inproceedings{chanehai2023improving,
  author = {Timothée Chane-Haï and Samuel Vercraene and Céline Robardet and Thibaud Monteiro},
  title = {{Improving the non-urgent sanitary transportation}},
  booktitle = {ICCAD},
  year = {2023},
  doi = {10.1109/iccad57653.2023.10152350},
}
Figure