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: Bilevel Optimization for On-Demand Multimodal Transit Systems
This study explores the design of an On-Demand Multimodal Transit System (ODMTS) that includes segmented mode switching models that decide whether potential riders adopt the new ODMTS or stay with their personal vehicles. It is motivated by the desire of transit agencies to design their network by taking into account both existing and latent demand, as quality of service improves. The paper presents a bilevel optimization where the leader problem designs the network and each rider has a follower problem to decide her best route through the ODMTS. The bilevel model is solved by a decomposition algorithm that combines traditional Benders cuts with combinatorial cuts to ensure the consistency of mode choices by the leader and follower problems. The approach is evaluated on a case study using historical data from Ann Arbor, Michigan, and a user choice model based on the income levels of the potential transit riders.  more » « less
Award ID(s):
1854684
PAR ID:
10225993
Author(s) / Creator(s):
Editor(s):
Hebrard E., Musliu N.
Date Published:
Journal Name:
Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2020. Lecture Notes in Computer Science, vol 12296. Springer,
Issue:
12296
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. ; ; (, Decision Analysis)
    null (Ed.)
    Traditionally, in the bilevel optimization framework, a leader chooses her actions by solving an upper-level problem, assuming that a follower chooses an optimal reaction by solving a lower-level problem. However, in many settings, the lower-level problems might be nontrivial, thus requiring the use of tailored algorithms for their solution. More importantly, in practice, such problems might be inexactly solved by heuristics and approximation algorithms. Motivated by this consideration, we study a broad class of bilevel optimization problems where the follower might not optimally react to the leader’s actions. In particular, we present a modeling framework in which the leader considers that the follower might use one of a number of known algorithms to solve the lower-level problem, either approximately or heuristically. Thus, the leader can hedge against the follower’s use of suboptimal solutions. We provide algorithmic implementations of the framework for a class of nonlinear bilevel knapsack problem (BKP), and we illustrate the potential impact of incorporating this realistic feature through numerical experiments in the context of defender-attacker problems. 
    more » « less
  3. ; ; (, INFORMS Journal on Computing)
    We consider a bilevel network interdiction problem where the follower aims to maximize the amount of flow from the source node to the sink node, and the leader aims to minimize the number of arcs from a critical set that have positive flow on them, that is, active arcs, in the maximum flow solution obtained by the follower. This problem is motivated by an application in human trafficking disruption. We consider both the optimistic and pessimistic variants of this bilevel optimization problem and develop their respective single-level reformulations. We present a tailored solution method to the pessimistic problem, which solves the problem to optimality for one practically important class of networks. Through computational experiments on randomly generated layered network instances, we show the effectiveness of the proposed methods and demonstrate that the tailored method is orders of magnitude faster than existing approaches in the literature. We also conduct computational experiments on randomly generated test instances inspired by domestic human trafficking networks and draw domain-specific insights. 
    more » « less
  4. ; ; (, 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
  5. ; ; ; (, 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
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email