Highlights A new methodology to partition the bipartite graph in the ride-matching problem. The partitioning forms sub-problems that are uniform within tolerance in size. An entire trip is considered to be the object in partitioning. The iterative solution algorithm terminates in a finite number of steps. The iterative solution algorithm obtains strictly superior partitions with iterations.

    Abstract A dynamic ridesharing system is a platform that connects drivers who use their personal vehicles to travel with riders who are in need of transportation, on a short notice. Since each driver/rider may have several potential matches, to achieve a high performance level, the ridesharing operator needs to make the matching decisions based on a global view of the system that includes all active riders and drivers. Consequently, the ride-matching problem that needs to be solved can become computationally expensive, especially when the system is operating over a large region, or when it faces high demand levels during certain hours of the day. This paper develops a graph partitioning methodology based on the bipartite graph that arises in the one-to-one ride-matching problem. The proposed method decomposes the original graph into multiple sub-graphs with the goal of reducing the overall computational complexity of the problem as well as providing high quality solutions. We further show that this methodology can be extended to more complex ride-matching problems in a dynamic ride-sharing system. Using numerical experiments, we showcase the advantages of the new partitioning method for different forms of ride-matching problems. Moreover, a sensitivity analysis is conducted to show the impact of different parameters on the quality of our solution.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Trip-based graph partitioning in dynamic ridesharing


    Contributors:


    Publication date :

    2020-02-08


    Size :

    22 pages




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    Markets for Dynamic Ridesharing?

    Deakin, Elizabeth / Frick, Karen Trapenberg / Shively, Kevin M. | Transportation Research Record | 2010


    Optimization of Dynamic Ridesharing Systems

    Di Febbraro, A | Online Contents | 2013


    RIDESHARING SUPPORT SYSTEM, RIDESHARING SUPPORT METHOD, AND RIDESHARING SUPPORT DEVICE

    MORIOKA WATARU | European Patent Office | 2019

    Free access

    Optimization of Dynamic Ridesharing Systems

    Di Febbraro, A. / Gattorna, E. / Sacco, N. | Transportation Research Record | 2013


    Mobilität + Umwelt: Dynamic ridesharing services

    Strauss, Christoph | Online Contents | 2006