A math-heuristic and exact algorithm for first-mile ridesharing problem with passenger service quality preferences
Ping He (TU Delft - Transport Engineering and Logistics, Shanghai Jiao Tong University)
Jian Gang Jin (Shanghai Jiao Tong University)
Martin Trépanier (Centre interuniversitaire de recherche sur les réseaux d’entreprise, la logistique et le transport (CIRRELT), Polytechnique Montreal)
Frederik Schulte (TU Delft - Transport Engineering and Logistics)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
With the growing demand for high-quality mobility services, transportation service providers need to offer transit services that not only fulfill passengers’ basic travel needs but also ensure an appealing quality of service. During rush hours, fleet sizes are often insufficient to cater to all passenger preferences on service quality, such as ride time and number of co-riders, leading to the sacrifice of service quality for some passengers. Motivated by these practices, we investigate a first-mile ridesharing problem incorporating passenger service quality preferences. This problem involves intricate decisions about the match between requests and vehicles, vehicle routing, and route schedules. To solve this problem, we first develop an arc-based mixed-integer linear programming (MILP) model for this problem. For obtaining near-optimal solutions within practical computation time requirements, we reformulate the MILP model as a trip-based set-partitioning model and propose a math-heuristic algorithm. This algorithm builds upon the column-generation algorithm and tailored bidirectional labeling algorithms with novel dominance rules. Additionally, we introduce a proposition to determine the best schedule for each ridesharing route. To obtain the optimal solution for large-scale instances, we introduce a branch-and-price exact algorithm. Computational experiments based on real-world road networks and randomly generated instances confirm the effectiveness and efficiency of the proposed approaches, demonstrating that the proposed matheuristic finds near-optimal solutions within 40 s for all instances. The results also show that the presented approach significantly improves the quality of first-mile services for prioritized riders, with the ratio of satisfied requests increasing by 23% even when the fleet is generally insufficient.