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.

    Highlights The first-mile ridesharing problem with public and private autonomous vehicles is introduced. Passengers’ requirements for service quality, such as the latest arrival time and the maximum ride time, are considered. An arc-based mixed-integer programming model and a trip-based set-partitioning model are proposed. A branch-and-price algorithm and a tailored column-generation matheuristic algorithm are designed. A tailored labeling algorithm with a novel dominance rule and a time schedule algorithm for routes are proposed.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    A column-generation matheuristic approach for optimizing first-mile ridesharing services with publicly- and privately-owned autonomous vehicles


    Contributors:


    Publication date :

    2024-02-03




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    Optimizing first-mile ridesharing services to intercity transit hubs

    He, Ping / Jin, Jian Gang / Schulte, Frederik et al. | Elsevier | 2023


    Analyzing Energy and Mobility Impacts of Privately-owned Autonomous Vehicles

    Cokyasar, Taner / Auld, Joshua / Javanmardi, Mahmoud et al. | IEEE | 2020


    RIDESHARING MANAGEMENT FOR AUTONOMOUS VEHICLES

    HARDEE CHRISTOPHER J / JOROFF STEVEN R / NESBITT PAMELA A et al. | European Patent Office | 2018

    Free access

    Mechanism design for on-demand first-mile ridesharing

    Bian, Zheyong / Liu, Xiang / Bai, Yun | Elsevier | 2020