01659730

Component

Taxi ride sharing is one of the most promising solutions to many urban transportation issues, such as traffic congestion, gas insufficiency, air pollution, limited parking space and unaffordable parking charge, taxi shortage in peak hours, etc. Despite the enormous demands of such service and its exciting social benefits, there is still a shortage of successful automated operations of ride sharing systems around the world. Two of the bottlenecks are: (1) on-time delivery is not guaranteed; (2) matching and scheduling drivers and passengers is a NP-hard problem, and optimization based models do not support real time scheduling on large scale systems. This study tackles the challenge of timely delivery of passengers in a large scale ride sharing system, where there are hundreds and even thousands of passengers and drivers to be matched and scheduled. The authors first formulate it as a mixed linear integer programming problem, which obtains the theoretical optimum, but at an unacceptable runtime cost even for a small system. The authors then introduce the greedy agglomeration and Monte Carlo simulation based algorithm. The effectiveness and efficiency of the new algorithm are fully evaluated: (1) Comparison with solving optimization model is conducted on small ride sharing cases. The greedy agglomerative algorithm can always achieve the same optimal solutions that the optimization model offers, but is three orders of magnitude faster. (2) Case studies on large scale systems are also included to validate its performance. (3) The proposed greedy algorithm is straightforward for parallelization to utilize distributed computing resources. (4) Two important details are discussed: selection of the number of Monte Carlo simulations and proper calculation of delays in the greedy agglomeration step. The authors find out from experiments that the sufficient number of simulations to achieve a “sufficiently optimal solution” is linearly related to the product of the number of vehicles and the number of passengers. Experiments also show that enabling margins and counting early delivery as negative delay leads to more accurate solutions than counting delay only.

This paper was sponsored by TRB committee ABJ70 Standing Committee on Artificial Intelligence and Advanced Computing Applications.

18-06786

English

25p

2018

Transportation Research Board 97th Annual Meeting

Digital/other

Figures; References; Tables

Algorithms; Case studies; Monte Carlo method; Optimization; Passengers; Ridesharing; Scheduling; Taxi services; Taxicab drivers; Traffic delays; Travel time

Passenger Transportation; Planning and Forecasting; Public Transportation

Transportation Research Board Annual Meeting 2018 Paper #18-06786

TRIS, TRB, ATRI

Jan 8 2018 11:45AM