The dial-a-ride problem is a classic challenge in transportation and continues
to be relevant across a large spectrum of applications, e.g. door-to-door
transportation services, patient transportation, etc.
Recently a new variant of the dial-a-ride problem, called ride-sharing,
has received attention due to emergence of the use of smartphone-based
applications that support location-aware transportation services.
The general dial-a-ride problem involves complex constraints on a
time-dependent network.
The ride-sharing problem differs in that riders (resp. drivers) specify
transportation requests (resp. offers) between journey origins and
destinations.
The two sets of users, namely riders and drivers, have different constraints;
the riders have time windows for pickup and delivery, while drivers have a
starting time window, a deadline by which to reach the destination,
and a vehicle capacity.
The challenge is to maximise the overall utility of the participants in
the system, which can be defined in a variety of ways.

This application problem has many variations that consider different
constraints and objectives, e.g. maximising assignments, total waiting times,
total lateness, or finding a balanced allocation of riders between the drivers.
We study variants of the ride-sharing problem from computational complexity and
approximation perspectives.
The aim of our work is to develop efficient heuristics to obtain satisfiable
solutions to variants of the ride-sharing problem.

Acknowledgement

This contribution has emanated from research conducted with the financial support
of Science Foundation Ireland (SFI) under Grant Number SFI/12/RC/2289.