A Partition-Based Match Making Algorithm for Dynamic Ridesharing

被引:92
作者
Pelzer, Dominik [1 ]
Xiao, Jiajian [1 ]
Zehe, Daniel [1 ]
Lees, Michael H. [2 ]
Knoll, Alois C. [3 ]
Aydt, Heiko [1 ]
机构
[1] TUM CREATE, Modeling & Optimizat Architectures & Infrastruct, Singapore 138602, Singapore
[2] Univ Amsterdam, Fac Sci, Sect Computat Sci, NL-1012 Amsterdam, Netherlands
[3] Tech Univ Munich, Dept Informat, D-80333 Munich, Germany
基金
新加坡国家研究基金会;
关键词
Network partitioning; optimization algorithm; dynamic ridesharing; taxi sharing; multi-agent systems; A-RIDE PROBLEM; ADAPTIVE PREDICTIVE CONTROL; DELIVERY PROBLEM; CLASSIFICATION SCHEME; HEURISTIC ALGORITHM; TIME WINDOWS; PICKUP; OPTIMIZATION; SERVICE; SYSTEM;
D O I
10.1109/TITS.2015.2413453
中图分类号
TU [建筑科学];
学科分类号
0813 ;
摘要
Ridesharing offers the opportunity to make more efficient use of vehicles while preserving the benefits of individual mobility. Presenting ridesharing as a viable option for commuters, however, requires minimizing certain inconvenience factors. One of these factors includes detours which result from picking up and dropping off additional passengers. This paper proposes a method which aims to best utilize ridesharing potential while keeping detours below a specific limit. The method specifically targets ridesharing systems on a very large scale and with a high degree of dynamics which are difficult to address using classical approaches known from operations research. For this purpose, the road network is divided into distinct partitions which define the search space for ride matches. The size and shape of the partitions depend on the topology of the road network as well as on two free parameters. This allows optimizing the partitioning with regard to sharing potential utilization and inconvenience minimization. Match making is ultimately performed using an agent-based approach. As a case study, the algorithm is applied to investigate the potential for taxi sharing in Singapore. This is done by considering about 110 000 daily trips and allowing up to two sharing partners. The outcome shows that the number of trips could be reduced by 42% resulting in a daily mileage savings of 230 000 km. It is further shown that the presented approach exceeds the mileage savings achieved by a greedy heuristic by 6% while requiring 30% lower computational efforts.
引用
收藏
页码:2587 / 2598
页数:12
相关论文
共 61 条
[1]   Optimization for dynamic ride-sharing: A review [J].
Agatz, Niels ;
Erera, Alan ;
Savelsbergh, Martin ;
Wang, Xing .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2012, 223 (02) :295-303
[2]   A survey on pickup and delivery problems: Part II: Transportation between pickup and delivery locations [J].
Parragh S.N. ;
Doerner K.F. ;
Hartl R.F. .
Journal für Betriebswirtschaft, 2008, 58 (2) :81-117
[3]  
[Anonymous], 2013, STAT IN BRIEF
[4]  
[Anonymous], 2006, J. fur Betriebswirtschaft, DOI DOI 10.1007/S11301-008-0036-4
[5]   An exact method for the car pooling problem based on Lagrangean column generation [J].
Baldacci, R ;
Maniezzo, V ;
Mingozzi, A .
OPERATIONS RESEARCH, 2004, 52 (03) :422-439
[6]   Static pickup and delivery problems: a classification scheme and survey [J].
Berbeglia, Gerardo ;
Cordeau, Jean-Francois ;
Gribkovskaia, Irina ;
Laporte, Gilbert .
TOP, 2007, 15 (01) :1-31
[7]   Dynamic pickup and delivery problems [J].
Berbeglia, Gerardo ;
Cordeau, Jean-Francois ;
Laporte, Gilbert .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2010, 202 (01) :8-15
[8]  
Bezdek J. C., 1973, FUZZY MATH PATTERN C
[9]   CLASSIFICATION IN VEHICLE-ROUTING AND SCHEDULING [J].
BODIN, L ;
GOLDEN, B .
NETWORKS, 1981, 11 (02) :97-108
[10]  
Bodin L. D., 1975, COMPUTERS URBAN SOC, V1, P11, DOI DOI 10.1016/0305-7097(75)90003-4.