  Patient transportation systems are instrumental in lowering access barriers
in primary care by taking patients to their GPs. As part of this setting, each
transportation request of a chronic or walk-in patient consists of an outbound
trip to the GP and an inbound trip back home. The economic sustainability of
patient transportation systems mainly depends on their utilization and how well
transportation requests can be bundled through ride sharing. To ease the
latter, we consider a flexible scheduling of chronic patients in which only a
certain range for an appointment is fixed a priori while the exact time is
determined by the scheduling of the outbound trip. This leads to a novel
extension of the dial-a-ride problem that we call the dial-a-ride problem with
combined requests and flexible scheduling (DARPCF). In this paper, we introduce
two heuristics for the DARPCF that exploit this increased flexibility. Both
approaches initially compute so-called mini-clusters of outbound requests.
Then, the mini-clusters are linked by (i) solving a traveling salesman problem
and creating routes of outbound rides with a splitting procedure or by (ii)
using a rolling horizon approach and solving bipartite matching problems for
the vehicle assignment. Our computational study shows that by using the
presented algorithms with the flexible scheduling of chronic appointments, the
average number of served requests can be increased by 16% compared to a
non-flexible setting.
