Typical ride matching processes in a Dial-a-Ride problem involve complex algorithms to match riders at multiple origins with multiple destinations (many-to-many). However, researchers have simplified this process in the many-to-one scenario where one common origin/destination is defined for all users (institutional context: universities, hospitals, etc.).
This paper presents the results of research that aims at developing a many-to-one ride matching approach based on the Capacitated Vehicle Routing Problem with Time Windows. The problem is context-related to the ridesharing specifics, including unit demand, asymmetric network, narrow time windows at departure, and common arrival time at destination. New heuristics are proposed based on different traversals of hierarchical spanning trees derived from the all-pairs shortest path matrix (distance or travel time matrix). A tree type is selected depending on the solution strategy, where the Proximity Clustering Tree (PCT) is used to prioritize matching passengers within proximity clusters, and the Minimum Deviation Tree (MDT) is used to match passengers along route with minimum deviations. Results are compared with exact solutions and other known methods, and in most cases have shown near optimal solutions with substantially reduced computational efforts.
| Subject : | : | Abstracts |
| Topics | : | Vehicle routing with time windows |
| PDF version | : |  PDF version |
