Ridesharing benefits the economy and the environment. In multi-hop ridesharing, passengers are permitted to switch vehicles within a single trip, extending the flexibility of conventional ridesharing. Nonetheless, vehicle dispatch is a difficult issue in multi-hop ridesharing. We subdivide the vehicle dispatching problem into the vehicle pairing problem and the request selection problem within a vehicle pair. To address these subproblems, we propose a two-stage framework for vehicle pair dispatching. In the initial stage, we model the vehicle pairing problem as a maximum vehicle-vehicle matching problem in a general graph, which differs from the conventional vehicle-request matching problem in a bipartite graph. The vehicle pairing algorithm is proposed to efficiently solve the vehicle pairing problem. In the second stage, we model the request selection problem as a multidimensional knapsack problem (d-KP) and propose an LP-relaxation request selection algorithm with an approximation ratio 1/5. Experiments conducted on a real-world dataset demonstrate the economic benefit of our proposed two-stage framework.
Two-stage Vehicle Pair Dispatch in Multi-hop Ridesharing
2023-05-24
2235362 byte
Conference paper
Electronic Resource
English
ArXiv | 2018
|RIDESHARING SUPPORT SYSTEM, RIDESHARING SUPPORT METHOD, AND RIDESHARING SUPPORT DEVICE
European Patent Office | 2019
|Ridesharing management device, ridesharing management method, and program
European Patent Office | 2024
|NTIS | 1982
|