You are here

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

Authors: 

Gilles Simonin, Barry O'Sullivan

Publication Type: 
Refereed Conference Meeting Proceeding
Abstract: 
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
Proceedings: 
-
Digital Object Identifer (DOI): 
-
Publication Date: 
27/08/2014
Volume: 
-
Issue: 
-
Pages: 
-
Conference Location: 
Czech Republic
Institution: 
National University of Ireland, Cork (UCC)
Open access repository: 
No
Publication document: