You are here

Optimisation for the ride-sharing problem


Gilles Simonin, Barry O'Sullivan

Publication Type: 
Refereed Conference Meeting Proceeding
he 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 \emph{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.
Conference Name: 
Digital Object Identifer (DOI): 
Publication Date: 
Conference Location: 
National University of Ireland, Cork (UCC)
Open access repository: 
Publication document: