skip to main content


Title: A Continuous Model for Designing Corridor Systems with Modular Autonomous Vehicles Enabling Station-wise Docking
The “asymmetry” between spatiotemporally varying passenger demand and fixed-capacity transportation supply has been a long-standing problem in urban mass transportation (UMT) systems around the world. The emerging modular autonomous vehicle (MAV) technology offers us an opportunity to close the substantial gap between passenger demand and vehicle capacity through station-wise docking and undocking operations. However, there still lacks an appropriate approach that can solve the operational design problem for UMT corridor systems with MAVs efficiently. To bridge this methodological gap, this paper proposes a continuum approximation (CA) model that can offer near-optimal solutions to the operational design for MAV-based transit corridors very efficiently. We investigate the theoretical properties of the optimal solutions to the investigated problem in a certain (yet not uncommon) case. These theoretical properties allow us to estimate the seat demand of each time neighborhood with the arrival demand curves, which recover the “local impact” property of the investigated problem. With the property, a CA model is properly formulated to decompose the original problem into a finite number of subproblems that can be analytically solved. A discretization heuristic is then proposed to convert the analytical solution from the CA model to feasible solutions to the original problem. With two sets of numerical experiments, we show that the proposed CA model can achieve near-optimal solutions (with gaps less than 4% for most cases) to the investigated problem in almost no time (less than 10 ms) for large-scale instances with a wide range of parameter settings (a commercial solver may even not obtain a feasible solution in several hours). The theoretical properties are verified, and managerial insights regarding how input parameters affect system performance are provided through these numerical results. Additionally, results also reveal that, although the CA model does not incorporate vehicle repositioning decisions, the timetabling decisions obtained by solving the CA model can be easily applied to obtain near-optimal repositioning decisions (with gaps less than 5% in most instances) very efficiently (within 10 ms). Thus, the proposed CA model provides a foundation for developing solution approaches for other problems (e.g., MAV repositioning) with more complex system operation constraints whose exact optimal solution can hardly be found with discrete modeling methods.  more » « less
Award ID(s):
1638355
NSF-PAR ID:
10359723
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
Transportation Science
Volume:
56
Issue:
1
ISSN:
0041-1655
Page Range / eLocation ID:
1 to 30
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. null (Ed.)
    Since passenger demand in urban transit systems is asymmetrically distributed across different periods in a day and different geographic locations across the cities, the tradeoff between vehicle operating costs and service quality has been a persistent problem in transit operational design. The emerging modular vehicle technology offers us a new perspective to solve this problem. Based on this concept, we propose a variable-capacity operation approach with modular transits for shared-use corridors, in which both dispatch headway and vehicle capacity are decision variables. This problem is rigorously formulated as a mixed integer linear programming model that aims to minimize the overall system cost, including passenger waiting time costs and vehicle operating costs. Because the proposed model is linear, the state-of-the-art commercial solvers (e.g., Gurobi) can be used to obtain the optimal solution of the investigated problem. With numerical experiments, we demonstrate the feasibility of the mathematical model, verify the effectiveness of the proposed model in reducing overall system costs in transit systems, as well as the robustness of the proposed model with different parameter settings. 
    more » « less
  2. null (Ed.)
    Although urban transit systems (UTS) often have fixed vehicle capacity and relatively constant departure headways, they may need to accommodate dramatically fluctuating passenger demands over space and time, resulting in either excessive passenger waiting or vehicle capacity and energy waste. Therefore, on the one hand, optimal operations of UTS rely on accurate modeling of passenger queuing dynamics, which is particularly complex on a multistop transit corridor. On the other hand, capacities of transit vehicles can be made variable and adaptive to time-variant passenger demand so as to minimize energy waste, especially with the emergence of modular vehicle technologies. This paper investigates operations of a multistop transit corridor in which vehicles may have different capacities across dispatches. We specify skewed time coordinates to simplify the problem structure while incorporating traffic congestion. Then, we propose a mixed integer linear programming model that determines the optimal dynamic headways and vehicle capacities over the study time horizon to minimize the overall system cost for the transit corridor. In particular, the proposed model considers a realistic multistop first-in, first-out (MSFIFO) rule that gives the same boarding priority to passengers arriving at a station in the same time interval yet with different destinations. A customized dynamic programming (DP) algorithm is proposed to solve this model efficiently. To circumvent the rapid increase of the state space of a typical DP algorithm, we analyze the theoretical properties of the investigated problem and identify upper and lower bounds to a feasible solution. The bounds largely reduce the state space during the DP iterations and greatly improve the efficiency of the proposed DP algorithm. The state dimensions are also reduced with the MSFIFO rule such that all queues with different destinations at the same origin can be tracked with a single boarding position state variable at each stage. A hypothetical example and a real-world case study show that the proposed DP algorithm greatly outperforms a state-of-the-art commercial solver (Gurobi) in both solution quality and time. 
    more » « less
  3. Ride-pooling, which accommodates multiple passenger requests in a single trip, has the potential to substantially enhance the throughput of mobility-on-demand (MoD) systems. This paper investigates MoD systems that operate mixed fleets composed of “basic supply” and “augmented supply” vehicles. When the basic supply is insufficient to satisfy demand, augmented supply vehicles can be repositioned to serve rides at a higher operational cost. We formulate the joint vehicle repositioning and ride-pooling assignment problem as a two-stage stochastic integer program, where repositioning augmented supply vehicles precedes the realization of ride requests. Sequential ride-pooling assignments aim to maximize total utility or profit on a shareability graph: a hypergraph representing the matching compatibility between available vehicles and pending requests. Two approximation algorithms for midcapacity and high-capacity vehicles are proposed in this paper; the respective approximation ratios are [Formula: see text] and [Formula: see text], where p is the maximum vehicle capacity plus one. Our study evaluates the performance of these approximation algorithms using an MoD simulator, demonstrating that these algorithms can parallelize computations and achieve solutions with small optimality gaps (typically within 1%). These efficient algorithms pave the way for various multimodal and multiclass MoD applications.

    History: This paper has been accepted for the Transportation Science Special Issue on Emerging Topics in Transportation Science and Logistics.

    Funding: This work was supported by the National Science Foundation [Grants CCF-2006778 and FW-HTF-P 2222806], the Ford Motor Company, and the Division of Civil, Mechanical, and Manufacturing Innovation [Grants CMMI-1854684, CMMI-1904575, and CMMI-1940766].

    Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2021.0349 .

     
    more » « less
  4. Public transit agencies struggle to maintain transit accessibility with reduced resources, unreliable ridership data, reduced vehicle capacities due to social distancing, and reduced services due to driver unavailability. In collaboration with transit agencies from two large metropolitan areas in the USA, we are designing novel approaches for addressing the afore-mentioned challenges by collecting accurate real-time ridership data, providing guidance to commuters, and performing operational optimization for public transit. We estimate rider-ship data using historical automated passenger counting data, conditional on a set of relevant determinants. Accurate ridership forecasting is essential to optimize the public transit schedule, which is necessary to improve current fixed lines with on-demand transit. Also, passenger crowding has been a problem for public transportation since it deteriorates passengers’ wellbeing and satisfaction. During the COVID-19 pandemic, passenger crowding has gained importance since it represents a risk for social distancing violations. Therefore, we are creating optimization models to ensure that social distancing norms can be adequately followed while ensuring that the total demand for transit is met. We will then use accurate forecasts for operational optimization that includes (a) proactive fixed-line schedule optimization based on predicted demand, (b) dispatch of on-demand micro-transit, prioritizing at-risk populations, and (c) allocation of vehicles to transit and cargo trips, considering exigent vehicle maintenance requirements (i.e., disinfection). Finally, this paper presents some initial results from our project regarding the estimation of ridership in public transit. 
    more » « less
  5. null (Ed.)
    Public transit agencies struggle to maintain transit accessibility with reduced resources, unreliable ridership data, reduced vehicle capacities due to social distancing, and reduced services due to driver unavailability. In collaboration with transit agencies from two large metropolitan areas in the USA, we are designing novel approaches for addressing the afore-mentioned challenges by collecting accurate real-time ridership data, providing guidance to commuters, and performing operational optimization for public transit. We estimate rider-ship data using historical automated passenger counting data, conditional on a set of relevant determinants. Accurate ridership forecasting is essential to optimize the public transit schedule, which is necessary to improve current fixed lines with on-demand transit. Also, passenger crowding has been a problem for public transportation since it deteriorates passengers’ wellbeing and satisfaction. During the COVID-19 pandemic, passenger crowding has gained importance since it represents a risk for social distancing violations. Therefore, we are creating optimization models to ensure that social distancing norms can be adequately followed while ensuring that the total demand for transit is met. We will then use accurate forecasts for operational optimization that includes \textit(a) proactive fixed-line schedule optimization based on predicted demand, \textit(b) dispatch of on-demand micro-transit, prioritizing at-risk populations, and \textit(c) allocation of vehicles to transit and cargo trips, considering exigent vehicle maintenance requirements (\textiti.e., disinfection). Finally, this paper presents some initial results from our project regarding the estimation of ridership in public transit. 
    more » « less