Online Stochastic Planning for Taxi and Ridesharing
Publication Type:
Refereed Conference Meeting Proceeding
Abstract:
In this paper we consider the problem of on-line
stochastic ride-sharing and taxi-sharing with time windows.
We study a scenario in which people needing a taxi, or a
ride, assign their source and destination points plus other
restrictions (such as earlier time to departure and maximum
time to reach a destination); at the same time, there are taxis
or drivers interested in providing a ride (also with departure
and destination points, vehicle capacity and time restrictions).
We model the time window restrictions as a soft constraint (a
reasonable delay might be acceptable in a realistic scenario),
and consider the problem as an on-line continual planning
problem, in which additional ride requests may arrive while
plans for previous ride-matching are being executed. Finally,
such new requests may arrive at each time step with some
probability. The aim is to maximize the shared trips while
minimising the expected travel delay for each trip. In this
paper we propose an on-line stochastic optimization planning
approach in which instead of myopically optimising for the
offered trips and requested trips that are known, incorporate
information that partially describes the stochastic future into
the model in order to improve the quality of the solution. We
prove the effectiveness of the method in a real world scenario
using a number of instances extracted from a travel survey
in north-eastern Illinois (USA) conducted by the Chicago
Metropolitan Agency for Planning.
Conference Name:
ICTAI 2014, IEEE International Conference on Tools with Artificial Intelligence
Proceedings:
,-,
Digital Object Identifer (DOI):
10.na
Publication Date:
09/11/2014
Conference Location:
Cyprus
Research Group:
Institution:
National University of Ireland, Cork (UCC)
Open access repository:
No
Publication document: