skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: On the Value of Dynamism in Transit Networks
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 .  more » « less
Award ID(s):
2144127 1952011 1839346
PAR ID:
10399027
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
Transportation Science
ISSN:
0041-1655
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; (, Transportation Science)
    This paper studies how to integrate rider mode preferences into the design of on-demand multimodal transit systems (ODMTSs). It is motivated by a common worry in transit agencies that an ODMTS may be poorly designed if the latent demand, that is, new riders adopting the system, is not captured. This paper proposes a bilevel optimization model to address this challenge, in which the leader problem determines the ODMTS design, and the follower problems identify the most cost efficient and convenient route for riders under the chosen design. The leader model contains a choice model for every potential rider that determines whether the rider adopts the ODMTS given her proposed route. To solve the bilevel optimization model, the paper proposes an exact decomposition method that includes Benders optimal cuts and no-good cuts to ensure the consistency of the rider choices in the leader and follower problems. Moreover, to improve computational efficiency, the paper proposes upper and lower bounds on trip durations for the follower problems, valid inequalities that strengthen the no-good cuts, and approaches to reduce the problem size with problem-specific preprocessing techniques. The proposed method is validated using an extensive computational study on a real data set from the Ann Arbor Area Transportation Authority, the transit agency for the broader Ann Arbor and Ypsilanti region in Michigan. The study considers the impact of a number of factors, including the price of on-demand shuttles, the number of hubs, and access to transit systems criteria. The designed ODMTSs feature high adoption rates and significantly shorter trip durations compared with the existing transit system and highlight the benefits of ensuring access for low-income riders. Finally, the computational study demonstrates the efficiency of the decomposition method for the case study and the benefits of computational enhancements that improve the baseline method by several orders of magnitude. Funding: This research was partly supported by National Science Foundation [Leap HI Proposal NSF-1854684] and the Department of Energy [Research Award 7F-30154]. 
    more » « less
  2. ; ; ; (, Manufacturing & Service Operations Management)
    Problem definition: We study a feature-based pricing problem with demand censoring in an offline, data-driven setting. In this problem, a firm is endowed with a finite amount of inventory and faces a random demand that is dependent on the offered price and the features (from products, customers, or both). Any unsatisfied demand that exceeds the inventory level is lost and unobservable. The firm does not know the demand function but has access to an offline data set consisting of quadruplets of historical features, inventory, price, and potentially censored sales quantity. Our objective is to use the offline data set to find the optimal feature-based pricing rule so as to maximize the expected profit. Methodology/results: Through the lens of causal inference, we propose a novel data-driven algorithm that is motivated by survival analysis and doubly robust estimation. We derive a finite sample regret bound to justify the proposed offline learning algorithm and prove its robustness. Numerical experiments demonstrate the robust performance of our proposed algorithm in accurately estimating optimal prices on both training and testing data. Managerial implications: The work provides practitioners with an innovative modeling and algorithmic framework for the feature-based pricing problem with demand censoring through the lens of causal inference. Our numerical experiments underscore the value of considering demand censoring in the context of feature-based pricing. Funding: The research of E. Fang is partially supported by the National Science Foundation [Grants NSF DMS-2346292, NSF DMS-2434666] and the Whitehead Scholarship. The research of C. Shi is partially supported by the Amazon Research Award. Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2024.1061 . 
    more » « less
  3. ; ; (, INFORMS Journal on Computing)
    This paper reconsiders the On-Demand Multimodal Transit Systems (ODMTS) Design with Adoptions problem (ODMTS-DA) to capture the latent demand in on-demand multimodal transit systems. The ODMTS-DA is a bilevel optimization problem, for which Basciftci and Van Hentenryck proposed an exact combinatorial Benders decomposition. Unfortunately, their proposed algorithm only finds high-quality solutions for medium-sized cities and is not practical for large metropolitan areas. The main contribution of this paper is to propose a new path-based optimization model, called P-Path, to address these computational difficulties. The key idea underlying P-Path is to enumerate two specific sets of paths which capture the essence of the choice model associated with the adoption behavior of riders. With the help of these path sets, the ODMTS-DA can be formulated as a single-level mixed-integer programming model. In addition, the paper presents preprocessing techniques that can reduce the size of the model significantly. P-Path is evaluated on two comprehensive case studies: the midsize transit system of the Ann Arbor – Ypsilanti region in Michigan (which was studied by Basciftci and Van Hentenryck) and the large-scale transit system for the city of Atlanta. The experimental results show that P-Path solves the Michigan ODMTS-DA instances in a few minutes, bringing more than two orders of magnitude improvements compared with the existing approach. For Atlanta, the results show that P-Path can solve large-scale ODMTS-DA instances (about 17 millions variables and 37 millions constraints) optimally in a few hours or in a few days. These results show the tremendous computational benefits of P-Path which provides a scalable approach to the design of on-demand multimodal transit systems with latent demand. History: Accepted by Andrea Lodi, Design & Analysis of Algorithms—Discrete. Funding: This work was partially supported by National Science Foundation Leap-HI [Grant 1854684] and the Tier 1 University Transportation Center (UTC): Transit - Serving Communities Optimally, Responsively, and Efficiently (T-SCORE) from the U.S. Department of Transportation [69A3552047141]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0014 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0014 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ . 
    more » « less
  4. ; ; ; (, Transportation Science)
    We study the problem of jointly pricing and designing a smart transit system, where a transit agency (the platform) controls a fleet of demand-responsive vehicles (cars) and a fixed line service (buses). The platform offers commuters a menu of options (modes) to travel between origin and destination (e.g., direct car trip, a bus ride, or a combination of the two), and commuters make a utility-maximizing choice within this menu, given the price of each mode. The goal of the platform is to determine an optimal set of modes to display to commuters, prices for these modes, and the design of the transit network in order to maximize the social welfare of the system. In this work, we tackle the commuter choice aspect of this problem, traditionally approached via computationally intensive bilevel programming techniques. In particular, we develop a framework that efficiently decouples the pricing and network design problem: Given an efficient (approximation) algorithm for centralized network design without prices, there exists an efficient (approximation) algorithm for decentralized network design with prices and commuter choice. We demonstrate the practicality of our framework via extensive numerical experiments on a real-world data set. We moreover explore the dependence of metrics such as welfare, revenue, and mode usage on (i) transfer costs and (ii) cost of contracting with on-demand service providers and exhibit the welfare gains of a fully integrated mobility system. Funding: This work was supported by the National Science Foundation [Awards CMMI-2308750, CNS-1952011, and CMMI-2144127]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2022.0452 . 
    more » « less
  5. ; ; (, Mathematics of Operations Research)
    In this paper, we study the generalized subdifferentials and the Riemannian gradient subconsistency that are the basis for non-Lipschitz optimization on embedded submanifolds of [Formula: see text]. We then propose a Riemannian smoothing steepest descent method for non-Lipschitz optimization on complete embedded submanifolds of [Formula: see text]. We prove that any accumulation point of the sequence generated by the Riemannian smoothing steepest descent method is a stationary point associated with the smoothing function employed in the method, which is necessary for the local optimality of the original non-Lipschitz problem. We also prove that any accumulation point of the sequence generated by our method that satisfies the Riemannian gradient subconsistency is a limiting stationary point of the original non-Lipschitz problem. Numerical experiments are conducted to demonstrate the advantages of Riemannian [Formula: see text] [Formula: see text] optimization over Riemannian [Formula: see text] optimization for finding sparse solutions and the effectiveness of the proposed method. Funding: C. Zhang was supported in part by the National Natural Science Foundation of China [Grant 12171027] and the Natural Science Foundation of Beijing [Grant 1202021]. X. Chen was supported in part by the Hong Kong Research Council [Grant PolyU15300219]. S. Ma was supported in part by the National Science Foundation [Grants DMS-2243650 and CCF-2308597], the UC Davis Center for Data Science and Artificial Intelligence Research Innovative Data Science Seed Funding Program, and a startup fund from Rice University. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email