A Matching Algorithm for Dynamic Ridesharing | Zendy

Maximilian Schreieck | Zendy; Hazem Safetli | Zendy; Sajjad Ali Siddiqui | Zendy; Christoph Pflügler | Zendy; Manuel Wiesche | Zendy; Helmut Krcmar | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

A Matching Algorithm for Dynamic Ridesharing

Author(s) -

Maximilian Schreieck,

Hazem Safetli,

Sajjad Ali Siddiqui,

Christoph Pflügler,

Manuel Wiesche,

Helmut Krcmar

Publication year - 2016

Publication title -

transportation research procedia

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.657

H-Index - 40

eISSN - 2352-1465

pISSN - 2352-1457

DOI - 10.1016/j.trpro.2016.12.087

Subject(s) - notice , matching (statistics) , computer science , service (business) , set (abstract data type) , transport engineering , constraint (computer aided design) , algorithm , map matching , blossom algorithm , operations research , engineering , business , global positioning system , telecommunications , mathematics , statistics , mechanical engineering , marketing , political science , law , programming language

Ridesharing is an important component of sustainable urban transportation as it increases vehicle utilization while reducing road utilization. By sharing rides, drivers offer free seats in their vehicles to passengers who want to travel in similar directions. Traditional ridesharing approaches are suitable for long-distance travel, especially inter-city travel, yet they are not flexible enough for short routes within cities. The aim of our research is to develop a service that enables dynamic ridesharing as part of sustainable urban mobility. Dynamic ridesharing refers to a service that automatically matches ride requests and ride offers on short notice without prior agreement between driver and passenger. We present the implementation and evaluation of a dynamic ridesharing service. The implementation part requires an automated matching algorithm that checks whether a driver can take a passenger with him without violating the maximum detour constraint he has set. As this matching algorithm needs to automatically match a relatively large number of ride offers and ride requests in real-time, we focused on building a high-performance algorithm. After implementing the algorithm, we evaluated its performance on a data set with random ride offers in and around the Munich city that is matched with different ride requests. For 10,000 rides in the system, it took less than 0.4 seconds on average to identify the best match.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research