University Library
  • Login
A gateway to Melbourne's research publications
Minerva Access is the University's Institutional Repository. It aims to collect, preserve, and showcase the intellectual output of staff and students of the University of Melbourne for a global audience.
View Item 
  • Minerva Access
  • Engineering and Information Technology
  • Computing and Information Systems
  • Computing and Information Systems - Theses
  • View Item
  • Minerva Access
  • Engineering and Information Technology
  • Computing and Information Systems
  • Computing and Information Systems - Theses
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

    Scalable ride-sharing through geometric algorithms and multi-hop matching

    Thumbnail
    Download
    Final thesis file (3.506Mb)

    Citations
    Altmetric
    Author
    Xu, Yixin
    Date
    2020
    Affiliation
    Computing and Information Systems
    Metadata
    Show full item record
    Document Type
    PhD thesis
    Access Status
    Open Access
    URI
    http://hdl.handle.net/11343/265854
    Description

    © 2020 Yixin Xu

    Abstract
    Thanks to the ubiquitous access to the Internet, on-demand ride-sharing service has emerged to provide timely and convenient rides to passengers. Ride-sharing creates a win-win situation for all participants involved and brings substantial environmental benefits, thus becoming a prevalent transportation mode. A fundamental problem of ride-sharing is determining how to dispatch vehicles to passengers. Efficiency and optimality are two core requirements for dispatching algorithms. Long response times would significantly impact the user experience, while sub-optimal matching results would substantially lower the operational efficiency. Finding optimal matches in a short time is challenging due to a large number of involved participants, the highly dynamic scenario, and the expensive road network distance computation. This thesis proposes efficient and scalable algorithms to enable fast and high-quality dispatching. We observe that vehicles and passengers can only visit limited areas to ensure their latest arrival times. The limited areas can be used to quickly filter out infeasible vehicles. Such areas can be easily indexed and updated if represented as rectangles. Inspired by this key observation, we first propose an efficient algorithm to solve a basic problem in ride-sharing -- how to quickly prune infeasible vehicles for passengers. Our algorithm ensures the finding of all possible candidates since we compute and index the confined visiting areas using ellipses, and the ellipses provide tight bound regardless of the underlying network. The effective pruning leads to only a small number of candidates remained, which substantially reduces the complexity of selecting the optimal matches and the overall matching time. We further investigate multi-hop ride-sharing algorithms that allow transfers on a user's trip. The algorithms search for possible transfers between vehicles by detecting whether the visiting areas of vehicles overlap. The proposed algorithms prune the combinations of vehicles and transfer points, thus overcoming the efficiency bottleneck and achieving real-time responses. We propose exact algorithms that guarantee the finding of optimal matches. We further improve the matching time using speed-up strategies. The enabled multi-hop trips largely enhance the flexibility of real-world ride-sharing, increase the number of successfully matched requests, and reduce the travel distance of vehicles. Lastly, we facilitate quick assigning of nearest pick-up/drop-off locations for passengers by proposing an efficient and scalable all nearest neighbor algorithm in road networks. We exploit the property of the problem such that finding a nearest neighbor only consumes constant time while only one graph traversal is required during the preprocessing phase. The proposed algorithms in this thesis achieve orders of magnitude faster running time compared to the state-of-the-art algorithms. The auxiliary indices are lightweight and eliminate the high preprocessing and update cost for the highly dynamic scenarios.
    Keywords
    Ride-sharing; Road network; Real-time algorithm; Spatial database

    Export Reference in RIS Format     

    Endnote

    • Click on "Export Reference in RIS Format" and choose "open with... Endnote".

    Refworks

    • Click on "Export Reference in RIS Format". Login to Refworks, go to References => Import References


    Collections
    • Minerva Elements Records [53102]
    • Computing and Information Systems - Theses [408]
    Minerva AccessDepositing Your Work (for University of Melbourne Staff and Students)NewsFAQs

    BrowseCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects
    My AccountLoginRegister
    StatisticsMost Popular ItemsStatistics by CountryMost Popular Authors