Automated taxis’ dial-a-ride problem with ride-sharing considering congestion-based dynamic travel times

Automated taxis’ dial-a-ride problem with ride-sharing considering congestion-based dynamic travel times

Liang, X. (TU Delft Transport and Planning)
Correia, Gonçalo (TU Delft Transport and Planning)
An, Kun (Tongji University; Monash University)
van Arem, B. (TU Delft Transport and Planning)

2020

In this paper, we study the dial-a-ride problem of ride-sharing automated taxis (ATs) in an urban road network, considering the traffic congestion caused by the ATs. This shared automated mobility system is expected to provide a seamless door-to-door service for urban travellers, much like what the existing transportation network companies (TNC) do, but with decreased labour cost and more flexible relocation operations due to the vehicles’ automation. We propose an integer non-linear programming (INLP) model that optimizes the routing of the ATs to maximize the system profit, depending on dynamic travel times, which are a non-linear function of the ATs’ flows. It is important to involve traffic congestion in such a routing problem since for a growing number of ATs circulating in the city their number will lead to delays. The model is embedded within a rolling horizon framework, which divides a typical day into several horizons to deal with the real-time travel demand. In each horizon, the routing model is solved with the demand at that interval and assuring the continuity of the trips between horizons. Nevertheless, each horizon model is hard to solve given its number of constraints and decision variables. Therefore, we propose a solution approach based on a customized Lagrangian relaxation algorithm, which allows identifying a near-optimal solution for this difficult problem. Numerical experiments for the city of Delft, The Netherlands, are used to demonstrate the solution quality of the proposed algorithm as well as obtaining insights about the AT system performance. Results show that the solution algorithm can solve the proposed model for hard instances. Ride-sharing makes the AT system more capable to provide better service regarding delay time and the number of requests that can be attended by the system. The delay penalty on the profit objective function is an effective control parameter on guaranteeing the service quality while maintaining system profitability.

Automated vehicles
Dial-a-ride problem
Dynamic travel time
Lagrangian relaxation
Ride-sharing
Rolling horizon

http://resolver.tudelft.nl/uuid:14983127-da91-470e-81cb-62a36f9d9591

https://doi.org/10.1016/j.trc.2020.01.024

2020-08-07

0968-090X

Transportation Research. Part C: Emerging Technologies, 112, 260-281

Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Institutional Repository

journal article

© 2020 X. Liang, Gonçalo Correia , Kun An, B. van Arem