A Double Decomposition Algorithm for Network Planning and Operations in Deviated Fixed-route Microtransit
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908402406391808 |
|---|---|
| author | Martin-Iradi, Bernardo Schmid, Alexandria Cummings, Kayla Jacquillat, Alexandre |
| author_facet | Martin-Iradi, Bernardo Schmid, Alexandria Cummings, Kayla Jacquillat, Alexandre |
| contents | Microtransit offers opportunities to enhance urban mobility by combining the reliability of public transit and the flexibility of ride-sharing. This paper optimizes the design and operations of a deviated fixed-route microtransit system that relies on reference lines but can deviate on demand in response to passenger requests. We formulate a Microtransit Network Design (MiND) model via two-stage stochastic integer optimization, with a first-stage network design and service scheduling structure and a second-stage vehicle routing structure. We derive a tight second-stage relaxation using a subpath-based representation of microtransit operations in a load-expanded network. We develop a double-decomposition algorithm combining Benders decomposition and subpath-based column generation. We prove that the algorithm maintains a valid optimality gap and converges to an optimal solution in a finite number of iterations. Results obtained with real-world data from Manhattan show that the methodology scales to large and otherwise-intractable instances, with up to 10-100 candidate lines and hundreds of stops. Comparisons with transit and ride-sharing suggest that microtransit can provide win-win outcomes toward efficient mobility (high demand coverage, low costs, high level of service), equitable mobility (broad geographic reach) and sustainable mobility (limited environmental footprint). We provide an open-source implementation to enable replication. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_01265 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Double Decomposition Algorithm for Network Planning and Operations in Deviated Fixed-route Microtransit Martin-Iradi, Bernardo Schmid, Alexandria Cummings, Kayla Jacquillat, Alexandre Optimization and Control Microtransit offers opportunities to enhance urban mobility by combining the reliability of public transit and the flexibility of ride-sharing. This paper optimizes the design and operations of a deviated fixed-route microtransit system that relies on reference lines but can deviate on demand in response to passenger requests. We formulate a Microtransit Network Design (MiND) model via two-stage stochastic integer optimization, with a first-stage network design and service scheduling structure and a second-stage vehicle routing structure. We derive a tight second-stage relaxation using a subpath-based representation of microtransit operations in a load-expanded network. We develop a double-decomposition algorithm combining Benders decomposition and subpath-based column generation. We prove that the algorithm maintains a valid optimality gap and converges to an optimal solution in a finite number of iterations. Results obtained with real-world data from Manhattan show that the methodology scales to large and otherwise-intractable instances, with up to 10-100 candidate lines and hundreds of stops. Comparisons with transit and ride-sharing suggest that microtransit can provide win-win outcomes toward efficient mobility (high demand coverage, low costs, high level of service), equitable mobility (broad geographic reach) and sustainable mobility (limited environmental footprint). We provide an open-source implementation to enable replication. |
| title | A Double Decomposition Algorithm for Network Planning and Operations in Deviated Fixed-route Microtransit |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2402.01265 |