You are here

Optimisation for the Ride-Sharing Problem: a Complexity-based Approach


Gilles Simonin, Barry O'Sullivan

Publication Type: 
Refereed Conference Meeting Proceeding
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. In ride-sharing riders (resp. drivers) specify transportation requests (resp. offers) between journey origins and destinations. The two sets of participants, namely riders and drivers, have different constraints; the riders have time windows for pickup and delivery, while drivers have a starting time window, a 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. In this paper we study variations of the ride-sharing problem, under different notions of utility, from a computational complexity perspective, and identify a number of tractable and intractable cases. These results provide a basis for the development of efficient methods and heuristics for solving problems of real-world scale.
Conference Name: 
ECAI 2014
Digital Object Identifer (DOI): 
Publication Date: 
Conference Location: 
Czech Republic
National University of Ireland, Cork (UCC)
Open access repository: 
Publication document: