Print Email Facebook Twitter A scalable approach to real-time taxi ridesharing Title A scalable approach to real-time taxi ridesharing Author Vaandrager, Willem (TU Delft Electrical Engineering, Mathematics and Computer Science) Contributor Spaan, Matthijs (mentor) Alonso Mora, Javier (mentor) Tintarev, Nava (graduation committee) Zijp, Erik (graduation committee) Degree granting institution Delft University of Technology Programme Computer Science Date 2018-10-16 Abstract In an increasing urbanizing world the need for efficient transportation methods is growing. Ridesharing, sharing a taxi trip with multiple passengers, has been proposed as an effective way to contribute towards solving the traffic problems that arise in city centers. Current solutions to the problem are often more focused on optimality, and a fast algorithm is required to handle large quantities of passengers in real-time applications. We propose an algorithm that combines fast and efficient heuristics with clustering and parallelization techniques that is able to solve large problem instances within several seconds. The small response time of the algorithm is able to provide feedback to the customer rapidly, which makes it very suitable for ridesharing in real-time.A segmentation of the customers is implemented to speed up the search. This method divides the customers into subareas based on pickup location such that each subproblem contains a similar number of customers. This division also bounds the size of each subproblem to ensure a solution can be found in real-time. The primary search strategy uses a combination of effective local search heuristics to improve solutions for these subproblems rapidly. A technique reminiscent of variable neighborhood search is also implemented for diversification that can solve smaller instances to a greater degree. The full approach can handle problems containing over 5,000 requests and can effectively manage on-demand ridesharing in Manhattan where the current demand for yellow taxis has tripled. Subject RidesharingRoute planningTaxiClusteringScalability To reference this document use: http://resolver.tudelft.nl/uuid:9ff242b0-1dae-42d3-858d-3d906eb6d651 Part of collection Student theses Document type master thesis Rights © 2018 Willem Vaandrager Files PDF Master_Thesis_Willem_Vaandrager.pdf 5.03 MB Close viewer /islandora/object/uuid:9ff242b0-1dae-42d3-858d-3d906eb6d651/datastream/OBJ/view