Search for: All records

The offline pickup and delivery problem with time windows (PDPTW) is a classical combinatorial optimization problem in the transportation community, which has proven to be very challenging computationally. Due to the complexity of the problem, practical problem instances can be solved only via heuristics, which trade-off solution quality for computational tractability. Among the various heuristics, a common strategy is problem decomposition, that is, the reduction of a large-scale problem into a collection of smaller sub-problems, with spatial and temporal decompositions being two natural approaches. While spatial decomposition has been successful in certain settings, effective temporal decomposition has been challenging due to the difficulty of stitching together the sub-problem solutions across the decomposition boundaries. In this work, we introduce a novel temporal decomposition scheme for solving a class of PDPTWs that have narrow time windows, for which it is able to provide both fast and high-quality solutions. We utilize techniques that have been popularized recently in the context of online dial-a-ride problems along with the general idea of rolling horizon optimization. To the best of our knowledge, this is the first attempt to solve offline PDPTWs using such an approach. To show the performance and scalability of our framework, we use the optimization of paratransit services as a motivating example. Due to the lack of benchmark solvers similar to ours (i.e., temporal decomposition with an online solver), we compare our results with an offline heuristic algorithm using Google OR-Tools. In smaller problem instances (with an average of 129 requests per instance), the baseline approach is as competitive as our framework. However, in larger problem instances (approximately 2,500 requests per instance), our framework is more scalable and can provide good solutions to problem instances of varying degrees of difficulty, while the baseline algorithm often fails to find a feasible solution within comparable compute times. 

The rise of on-demand mobility technologies over the past decade has sparked interest in the integration of traditional transit and on-demand systems. One of the main reasons behind this is the potential to address a fundamental trade-off in transit: the ridership versus coverage dilemma. However, unlike purely fixed systems or purely on-demand systems, integrated systems are not well understood; their planning and operational problems are significantly more challenging, and their broader implications are the source of a heated debate. Motivated by this debate, we introduce the dynamicity gap, a general concept that quantifies the attainable benefit of allowing (but not requiring) dynamic components in the response strategy to a multistage optimization problem. Although computing the dynamicity gap exactly may be intractable, we develop an analytical framework with which to approximate it as a function of problem input parameters. The framework allows us to certify the value of dynamism (i.e., a dynamicity gap greater than one) for certain combinations of problem input parameters. We showcase our approach with two sets of computational experiments, from which we gain both qualitative and quantitative insights about the settings in which the integration of transit and on-demand systems may certifiably be a worthwhile investment. Funding: This work was partially supported by the National Science Foundation [Grants DMS-1839346 and CNS-1952011]. Part of this research was performed while the authors were visiting the Institute for Pure and Applied Mathematics, which is supported by the National Science Foundation [Grant DMS-1925919]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2022.1193 . 

This work considers the sensitivity of commute travel times in US metro areas due to potential changes in commute patterns, for example caused by events such as pandemics. Permanent shifts away from transit and carpooling can add vehicles to congested road networks, increasing travel times. Growth in the number of workers who avoid commuting and work from home instead can offset travel time increases. To estimate these potential impacts, 6-9 years of American Community Survey commute data for 118 metropolitan statistical areas are investigated. For 74 of the metro areas, the average commute travel time is shown to be explainable using only the number of passenger vehicles used for commuting. A universal Bureau of Public Roads model characterizes the sensitivity of each metro area with respect to additional vehicles. The resulting models are then used to determine the change in average travel time for each metro area in scenarios when 25% or 50% of transit and carpool users switch to single occupancy vehicles. Under a 25% mode shift, areas such as San Francisco and New York that are already congested and have high transit ridership may experience round trip travel time increases of 12 minutes (New York) to 20 minutes (San Francisco), costing individual commuters $1065 and $1601 annually in lost time. The travel time increases and corresponding costs can be avoided with an increase in working from home. The main contribution of this work is to provide a model to quantify the potential increase in commute travel times under various behavior changes, that can aid policy making for more efficient commuting. 

We construct an agent-based SEIR model to simulate COVID-19 spread at a 16000-student mostly non-residential urban university during the Fall 2021 Semester. We find that mRNA vaccine coverage at 100% combined with weekly screening testing of 25% of the campus population make it possible to safely reopen to in-person instruction. Our simulations exhibit a right-skew for total infections over the semester that becomes more pronounced with less vaccine coverage, less vaccine effectiveness and no additional preventative measures. This suggests that high levels of infection are not exceedingly rare with campus social connections the main transmission route. Finally, we find that if vaccine coverage is 100% and vaccine effectiveness is above 80%, then a safe reopening is possible even without facemask use. This models possible future scenarios with high coverage of additional “booster” doses of COVID-19 vaccines. 

Many transit agencies operating paratransit and microtransit ser-vices have to respond to trip requests that arrive in real-time, which entails solving hard combinatorial and sequential decision-making problems under uncertainty. To avoid decisions that lead to signifi-cant inefficiency in the long term, vehicles should be allocated to requests by optimizing a non-myopic utility function or by batching requests together and optimizing a myopic utility function. While the former approach is typically offline, the latter can be performed online. We point out two major issues with such approaches when applied to paratransit services in practice. First, it is difficult to batch paratransit requests together as they are temporally sparse. Second, the environment in which transit agencies operate changes dynamically (e.g., traffic conditions can change over time), causing the estimates that are learned offline to become stale. To address these challenges, we propose a fully online approach to solve the dynamic vehicle routing problem (DVRP) with time windows and stochastic trip requests that is robust to changing environmental dynamics by construction. We focus on scenarios where requests are relatively sparse-our problem is motivated by applications to paratransit services. We formulate DVRP as a Markov decision process and use Monte Carlo tree search to evaluate actions for any given state. Accounting for stochastic requests while optimizing a non-myopic utility function is computationally challenging; indeed, the action space for such a problem is intractably large in practice. To tackle the large action space, we leverage the structure of the problem to design heuristics that can sample promising actions for the tree search. Our experiments using real-world data from our partner agency show that the proposed approach outperforms existing state-of-the-art approaches both in terms of performance and robustness. 

Vehicle routing problems (VRPs) can be divided into two major categories: offline VRPs, which consider a given set of trip requests to be served, and online VRPs, which consider requests as they arrive in real-time. Based on discussions with public transit agencies, we identify a real-world problem that is not addressed by existing formulations: booking trips with flexible pickup windows (e.g., 3 hours) in advance (e.g., the day before) and confirming tight pickup windows (e.g., 30 minutes) at the time of booking. Such a service model is often required in paratransit service settings, where passengers typically book trips for the next day over the phone. To address this gap between offline and online problems, we introduce a novel formulation, the offline vehicle routing problem with online bookings. This problem is very challenging computationally since it faces the complexity of considering large sets of requests—similar to offline VRPs—but must abide by strict constraints on running time—similar to online VRPs. To solve this problem, we propose a novel computational approach, which combines an anytime algorithm with a learning-based policy for real-time decisions. Based on a paratransit dataset obtained from our partner transit agency, we demonstrate that our novel formulation and computational approach lead to significantly better outcomes in this service setting than existing algorithms. 

During the Covid-19 pandemic a key role is played by vaccination to combat the virus. There are many possible policies for prioritizing vaccines, and different criteria for optimization: minimize death, time to herd immunity, functioning of the health system. Using an age-structured population compartmental finite-dimensional optimal control model, our results suggest that the eldest to youngest vaccination policy is optimal to minimize deaths. Our model includes the possible infection of vaccinated populations. We apply our model to real-life data from the US Census for New Jersey and Florida, which have a significantly different population structure. We also provide various estimates of the number of lives saved by optimizing the vaccine schedule and compared to no vaccination.

 

The performance of multimodal mobility systems relies on the seamless integration of conventional mass transit services and the advent of Mobility-on-Demand (MoD) services. Prior work is limited to individually improving various transport networks' operations or linking a new mode to an existing system. In this work, we attempt to solve transit network design and pricing problems of multimodal mobility systems en masse. An operator (public transit agency or private transit operator) determines frequency settings of the mass transit system, flows of the MoD service, and prices for each trip to optimize the overall welfare. A primal-dual approach, inspired by the market design literature, yields a compact mixed integer linear programming (MILP) formulation. However, a key computational challenge remains in allocating an exponential number of hybrid modes accessible to travelers. We provide a tractable solution approach through a decomposition scheme and approximation algorithm that accelerates the computation and enables optimization of large-scale problem instances. Using a case study in Nashville, Tennessee, we demonstrate the value of the proposed model. We also show that our algorithm reduces the average runtime by 60% compared to advanced MILP solvers. This result seeks to establish a generic and simple-to-implement way of revamping and redesigning regional mobility systems in order to meet the increase in travel demand and integrate traditional fixed-line mass transit systems with new demand-responsive services.