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
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
- NSF-PAR ID:
- 10225993
- 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
-
-
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
-
more » « less
Abstract We study a class of bilevel spanning tree (BST) problems that involve two independent decision‐makers (DMs), the leader and the follower with different objectives, who jointly construct a spanning tree in a graph. The leader, who acts first, selects an initial subset of edges that do not contain a cycle, from the set under her control. The follower then selects the remaining edges to complete the construction of a spanning tree, but optimizes his own objective function. If there exist multiple optimal solutions for the follower that result in different objective function values for the leader, then the follower may choose either the one that is the most (optimistic version) or least (pessimistic version) favorable to the leader. We study BST problems with the sum‐ and bottleneck‐type objective functions for the DMs under both the optimistic and pessimistic settings. The polynomial‐time algorithms are then proposed in both optimistic and pessimistic settings for BST problems in which at least one of the DMs has the bottleneck‐type objective function. For BST problem with the sum‐type objective functions for both the leader and the follower, we provide an equivalent single‐level linear mixed‐integer programming formulation. A computational study is then presented to explore the efficacy of our reformulation.
-
This work describes the design of real-time dance-based interaction with a humanoid robot, where the robot seeks to promote physical activity in children by taking on multiple roles as a dance partner. It acts as a leader by initiating dances but can also act as a follower by mimicking a child’s dance movements. Dances in the leader role are produced by a sequence-to-sequence (S2S) Long Short-Term Memory (LSTM) network trained on children’s music videos taken from YouTube. On the other hand, a music orchestration platform is implemented to generate background music in the follower mode as the robot mimics the child’s poses. In doing so, we also incorporated the largely unexplored paradigm of learning-by-teaching by including multiple robot roles that allow the child to both learn from and teach to the robot. Our work is among the first to implement a largely autonomous, real-time full-body dance interaction with a bipedal humanoid robot that also explores the impact of the robot roles on child engagement. Importantly, we also incorporated in our design formal constructs taken from autism therapy, such as the least-to-most prompting hierarchy, reinforcements for positive behaviors, and a time delay to make behavioral observations. We implemented a multimodal child engagement model that encompasses both affective engagement (displayed through eye gaze focus and facial expressions) as well as task engagement (determined by the level of physical activity) to determine child engagement states. We then conducted a virtual exploratory user study to evaluate the impact of mixed robot roles on user engagement and found no statistically significant difference in the children’s engagement in single-role and multiple-role interactions. While the children were observed to respond positively to both robot behaviors, they preferred the music-driven leader role over the movement-driven follower role, a result that can partly be attributed to the virtual nature of the study. Our findings support the utility of such a platform in practicing physical activity but indicate that further research is necessary to fully explore the impact of each robot role.more » « less
-
null (Ed.)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.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/https://doi.org/10.1007/978-3-030-58942-4_4
