Print Email Facebook Twitter A column-generation matheuristic approach for optimizing first-mile ridesharing services with publicly- and privately-owned autonomous vehicles Title A column-generation matheuristic approach for optimizing first-mile ridesharing services with publicly- and privately-owned autonomous vehicles Author He, P. (TU Delft Transport Engineering and Logistics; Shanghai Jiao Tong University) Jin, Jian Gang (Shanghai Jiao Tong University) Trépanier, Martin (Polytechnique Montreal; Centre interuniversitaire de recherche sur les réseaux d’entreprise, la logistique et le transport (CIRRELT)) Schulte, F. (TU Delft Transport Engineering and Logistics) Date 2024 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. Subject Autonomous vehiclesBranch-and-price algorithmColumn-generation matheuristic algorithmFirst-mile ridesharingPublic transportation To reference this document use: http://resolver.tudelft.nl/uuid:78f97eb2-bb20-439a-85b4-9cb0f6d634b0 DOI https://doi.org/10.1016/j.trc.2024.104516 Embargo date 2024-08-10 ISSN 0968-090X Source Transportation Research. Part C: Emerging Technologies, 160 Bibliographical note Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public. Part of collection Institutional Repository Document type journal article Rights © 2024 P. He, Jian Gang Jin, Martin Trépanier, F. Schulte Files file embargo until 2024-08-10