A column-generation matheuristic approach for optimizing first-mile ridesharing services with publicly- and privately-owned autonomous vehicles
P. He (Shanghai Jiao Tong University, TU Delft - Transport Engineering and Logistics)
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)
F. 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
The burden of first-mile connection to public transit stations is a key barrier that discourages riders from taking public transportation. Public transit agencies typically operate a modest fleet of vehicles to provide first-mile services due to the high operating costs, thus failing to adequately meet the first-mile travel demands, especially during peak hours. At the same time, private cars are underutilized and have a lot of idle time. With the emergence of self-driving vehicles, new opportunities for addressing the current dilemma arise, such as integrating idle private self-driving vehicles to provide first-mile services, which is beneficial for public transportation agencies to provide high-quality services at low costs. This study investigates the first-mile ridesharing problem in which public transit agencies utilize idle privately-owned autonomous vehicles to dynamically inflate their fleet. This problem is more challenging in decision-making than conventional first-mile problems, as it involves decisions on heterogeneous fleet scheduling, vehicle routing, and time scheduling, all while taking into account the service quality for riders. To address this problem, an arc-based mixed-integer linear programming (MILP) model and a trip-based set-partitioning model are developed, both aiming to minimize total operational costs. To identify promising trips, we propose a tailored labeling algorithm with a novel dominance rule, along with a time window shift algorithm to determine the best schedule. To yield high-quality solutions in a short computation time, a tailored column-generation matheuristic algorithm is introduced. A branch-and-price exact algorithm and an adaptive large neighborhood search algorithm are developed to assess the matheuristic algorithm. Numerical experiments are conducted to demonstrate the effectiveness and applicability of the proposed models and algorithms. Experiments also show that this kind of ridesharing service can provide low-cost and high-quality services for the first-mile problem.