Toward Microtransit: Design and Operations of Reservation-based Systems
Static public transit infrastructure remains unresponsive to ever-changing mobility landscapes, contributing to transit ridership decline and compounding urban congestion. Simultaneously, the rapid growth of ride-sharing suggests that flexible, on-demand mobility services meet a critical need of urb...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2023
|
| Online Access: | https://hdl.handle.net/1721.1/152801 https://orcid.org/0000-0002-9497-4943 |
| _version_ | 1826195125383987200 |
|---|---|
| author | Cummings, Kayla |
| author2 | Jacquillat, Alexandre |
| author_facet | Jacquillat, Alexandre Cummings, Kayla |
| author_sort | Cummings, Kayla |
| collection | MIT |
| description | Static public transit infrastructure remains unresponsive to ever-changing mobility landscapes, contributing to transit ridership decline and compounding urban congestion. Simultaneously, the rapid growth of ride-sharing suggests that flexible, on-demand mobility services meet a critical need of urban travelers, despite their high fares. This context creates opportunities to design new hybrid microtransit services that shepherd the digital capabilities and operating flexibility of ride-sharing into the realm of high-capacity public transit. In this thesis, we discuss new strategic optimization frameworks for microtransit planning and operations. We develop decomposition algorithms to achieve insights at scale, and we evaluate new decision-making prototypes for transportation planners over case studies based on real-world data. We examine how these new microtransit technologies enable widespread coverage, rapid welfare gains for travelers, sustainable financial health for transportation operators, and reduced environmental footprints. Furthermore, we introduce new optimization frameworks for decision-making in other reservation-based, platformed systems, namely for server installation under demand uncertainty in cloud data centers.
In Chapter 2, we examine opportunities for transit agencies to outsource mobility services to mobility-on-demand providers. We formulate a fare-setting model via large-scale, mixed-integer, non-convex optimization to jointly set discounted fares across the integrated network, subject to commuters' travel choices. We formulate a novel two-stage decomposition with a new solution approach combining tailored coordinate descent, parsimonious second-stage evaluations, and interpolations using special ordered sets. We learn that alliance priorities inform optimal fare designs: flat fares decrease total vehicle miles, while geographically informed discounts improve passenger happiness. The model improves system utilization and lowers prices for low-income and long-distance commuters, and our revenue allocation mechanism aligns profit-oriented private operators with public transit priorities.
In Chapter 3, we optimize employee driver itineraries for door-to-door, reservation-based transportation services that capture vehicle rerouting capabilities following operating disruptions. We formalize the problem via two-stage stochastic optimization with a tight, network-based recourse model. Our activated Benders decomposition algorithm exploits linking relationships between the first-stage and second-stage problems to accelerate and strengthen Benders cuts. Using data from a major paratransit platform, we show that our algorithm scales to real-world instances, outperforming several benchmarks in terms of computational times, solution quality, and solution guarantees. From a practical standpoint, the model mitigates operating costs by strategically adding slack to driver itineraries, creating flexibility and robustness against supply and demand uncertainty.
In Chapter 4, we optimize the design and operations of a microtransit system that relies on reference lines and performs on-demand deviations in response to passenger demand. Our two-stage stochastic optimization for microtransit network design model leverages a novel subpath-based representation of microtransit operations in a load-expanded network to streamline on-demand deviations between checkpoint stops. We develop a double decomposition algorithm combining Benders decomposition and subpath-based column generation using a tailored label-setting algorithm. Our method scales to large practical instances based on Manhattan taxi data, with up to 100 candidate lines and hundreds of stops. Comparisons with transit and ride-sharing benchmarks suggest that microtransit can promote efficient, equitable, and sustainable mobility: high demand coverage, low operating costs, high level of service, higher accessibility, and limited environmental footprint.
Chapter 5 addresses an online resource allocation problem to optimize cloud data center configurations under demand uncertainty. We propose an integer optimization formulation for an offline hardware installation problem to maximize demand coverage under capacity constraints, reflecting real-world data center operations. To handle the online dynamics, we adjust the formulation to reserve capacity for a single-sample approximation of the dynamic decision-making problem, as opposed to multi-scenario sample average approximation. This tractable approach is accompanied by (i) theoretical results showing that single-sample approximation provides strong performance guarantees, as well as (ii) computational results using real-world data showing the cost benefits. The proposed solution has been deployed in Microsoft data centers worldwide to support data center managers’ decision-making for the rack placement process and alleviate inefficiencies in data center operations. |
| first_indexed | 2024-09-23T10:07:35Z |
| format | Thesis |
| id | mit-1721.1/152801 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T10:07:35Z |
| publishDate | 2023 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1528012023-11-03T03:51:51Z Toward Microtransit: Design and Operations of Reservation-based Systems Cummings, Kayla Jacquillat, Alexandre Vaze, Vikrant Massachusetts Institute of Technology. Operations Research Center Static public transit infrastructure remains unresponsive to ever-changing mobility landscapes, contributing to transit ridership decline and compounding urban congestion. Simultaneously, the rapid growth of ride-sharing suggests that flexible, on-demand mobility services meet a critical need of urban travelers, despite their high fares. This context creates opportunities to design new hybrid microtransit services that shepherd the digital capabilities and operating flexibility of ride-sharing into the realm of high-capacity public transit. In this thesis, we discuss new strategic optimization frameworks for microtransit planning and operations. We develop decomposition algorithms to achieve insights at scale, and we evaluate new decision-making prototypes for transportation planners over case studies based on real-world data. We examine how these new microtransit technologies enable widespread coverage, rapid welfare gains for travelers, sustainable financial health for transportation operators, and reduced environmental footprints. Furthermore, we introduce new optimization frameworks for decision-making in other reservation-based, platformed systems, namely for server installation under demand uncertainty in cloud data centers. In Chapter 2, we examine opportunities for transit agencies to outsource mobility services to mobility-on-demand providers. We formulate a fare-setting model via large-scale, mixed-integer, non-convex optimization to jointly set discounted fares across the integrated network, subject to commuters' travel choices. We formulate a novel two-stage decomposition with a new solution approach combining tailored coordinate descent, parsimonious second-stage evaluations, and interpolations using special ordered sets. We learn that alliance priorities inform optimal fare designs: flat fares decrease total vehicle miles, while geographically informed discounts improve passenger happiness. The model improves system utilization and lowers prices for low-income and long-distance commuters, and our revenue allocation mechanism aligns profit-oriented private operators with public transit priorities. In Chapter 3, we optimize employee driver itineraries for door-to-door, reservation-based transportation services that capture vehicle rerouting capabilities following operating disruptions. We formalize the problem via two-stage stochastic optimization with a tight, network-based recourse model. Our activated Benders decomposition algorithm exploits linking relationships between the first-stage and second-stage problems to accelerate and strengthen Benders cuts. Using data from a major paratransit platform, we show that our algorithm scales to real-world instances, outperforming several benchmarks in terms of computational times, solution quality, and solution guarantees. From a practical standpoint, the model mitigates operating costs by strategically adding slack to driver itineraries, creating flexibility and robustness against supply and demand uncertainty. In Chapter 4, we optimize the design and operations of a microtransit system that relies on reference lines and performs on-demand deviations in response to passenger demand. Our two-stage stochastic optimization for microtransit network design model leverages a novel subpath-based representation of microtransit operations in a load-expanded network to streamline on-demand deviations between checkpoint stops. We develop a double decomposition algorithm combining Benders decomposition and subpath-based column generation using a tailored label-setting algorithm. Our method scales to large practical instances based on Manhattan taxi data, with up to 100 candidate lines and hundreds of stops. Comparisons with transit and ride-sharing benchmarks suggest that microtransit can promote efficient, equitable, and sustainable mobility: high demand coverage, low operating costs, high level of service, higher accessibility, and limited environmental footprint. Chapter 5 addresses an online resource allocation problem to optimize cloud data center configurations under demand uncertainty. We propose an integer optimization formulation for an offline hardware installation problem to maximize demand coverage under capacity constraints, reflecting real-world data center operations. To handle the online dynamics, we adjust the formulation to reserve capacity for a single-sample approximation of the dynamic decision-making problem, as opposed to multi-scenario sample average approximation. This tractable approach is accompanied by (i) theoretical results showing that single-sample approximation provides strong performance guarantees, as well as (ii) computational results using real-world data showing the cost benefits. The proposed solution has been deployed in Microsoft data centers worldwide to support data center managers’ decision-making for the rack placement process and alleviate inefficiencies in data center operations. Ph.D. 2023-11-02T20:17:28Z 2023-11-02T20:17:28Z 2023-09 2023-08-28T21:38:28.560Z Thesis https://hdl.handle.net/1721.1/152801 https://orcid.org/0000-0002-9497-4943 In Copyright - Educational Use Permitted Copyright retained by author(s) https://rightsstatements.org/page/InC-EDU/1.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Cummings, Kayla Toward Microtransit: Design and Operations of Reservation-based Systems |
| title | Toward Microtransit: Design and Operations of Reservation-based Systems |
| title_full | Toward Microtransit: Design and Operations of Reservation-based Systems |
| title_fullStr | Toward Microtransit: Design and Operations of Reservation-based Systems |
| title_full_unstemmed | Toward Microtransit: Design and Operations of Reservation-based Systems |
| title_short | Toward Microtransit: Design and Operations of Reservation-based Systems |
| title_sort | toward microtransit design and operations of reservation based systems |
| url | https://hdl.handle.net/1721.1/152801 https://orcid.org/0000-0002-9497-4943 |
| work_keys_str_mv | AT cummingskayla towardmicrotransitdesignandoperationsofreservationbasedsystems |