A Partition-Based Match Making Algorithm for Dynamic Ridesharing

作者：Pelzer Dominik^*; Xiao Jiajian; Zehe Daniel; Lees Michael H; Knoll Alois C; Aydt Heiko

来源：IEEE Transactions on Intelligent Transportation Systems, 2015, 16(5): 2587-2598.

DOI：10.1109/TITS.2015.2413453

• Network partitioning
• optimization algorithm
• dynamic ridesharing
• taxi sharing
• multi-agent systems

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.

• 出版日期2015-10