The dial-a-ride problem in primary care with flexible scheduling

Abstract Patient transportation systems are instrumental in lowering access barriers in primary care by taking patients to their general practitioners (GPs). However, the economic sustainability of such transportation systems based on ride sharing strongly depends on how well transportation requests can be bundled. We consider a dial-a-ride setting where the transportation requests consist of a ride to the GP and back. Patients may be chronic or “walk-in” patients, with the latter requiring transportation on short notice. In the general setting, the GPs fix appointments without consideration of the transportation. In our flexible scheduling setting, for chronic patients only an appointment range is fixed a priori, and the exact time is determined when the vehicle routes are computed. To tackle this setting, we propose a novel extension of the dial-a-ride problem, the dial-a-ride problem with combined requests and flexible scheduling (DARPCF). We introduce a heuristic for the DARPCF, called MCLIH, that is designed to exploit this increased flexibility. Initially, MCLIH computes so-called mini-clusters of outbound requests. Then, the mini-clusters are linked by solving a traveling salesman problem and creating routes of outbound rides with a splitting procedure. Our computational study shows that in rural regions with MCLIH and the flexible scheduling of chronic appointments, the average number of served transportation requests can be increased by $$38\%$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>38</mml:mn> <mml:mo>%</mml:mo> </mml:mrow> </mml:math> compared to a non-flexible setting.