Group Consistent Dial-A-Ride using Adaptive Large Neighborhood Search

The dial-a-ride problem (DARP) consists of scheduling and routing vehicles such
that all users will be picked up and delivered within their specified time windows.
Each user or customer has a pick-up location and a delivery location and has a
time window that specifies the earliest pickup time as well as the latest delivery.
Furthermore, the problem must consider the capacity constraints of the vehicles.
A real-life example of the DARP is the transportation of school children to and
from school, which is a service offered through the municipality to selected
children. Varying the driver, driving time, and other passengers can be stressful -
especially for children. This work considers the Group Consistent DARP (GC-DARP)
which seeks to ensure that each user drives with a limited amount of different
users. In this formulation of the GC-DARP, all users have some schedules. A
schedule is one or more travel requests (with a defined pickup, delivery, and time
window) that have a known set of repetition - i.e. weekly, every other week, once
every 4 weeks, etc. The schedule can at maximum consist of an outbound and
inbound travel request each day, depending on whether or not a return trip is
desired. The problem must then not only consider trips with proximity in both
time and location, but also the consistency and frequency with which the trips will
be driven. We use the Adaptive Large Neighborhood Search (ALNS) to solve this
problem for instances with up to 200 different schedules.