More Web Proxy on the site http://driver.im/

research-article

Public Access

Real-time Approximate Routing for Smart Transit Systems

Authors:

Noémie Périvier,

Chamsi Hssaine,

Samitha Samaranayake,

Siddhartha BanerjeeAuthors Info & Claims

Proceedings of the ACM on Measurement and Analysis of Computing Systems, Volume 5, Issue 2

Article No.: 24, Pages 1 - 30

https://doi.org/10.1145/3460091

Published: 04 June 2021 Publication History

Abstract

We study real-time routing policies in smart transit systems, where the platform has a combination of cars and high-capacity vehicles (e.g., buses or shuttles) and seeks to serve a set of incoming trip requests. The platform can use its fleet of cars as a feeder to connect passengers to its high-capacity fleet, which operates on fixed routes. Our goal is to find the optimal set of (bus) routes and corresponding frequencies to maximize the social welfare of the system in a given time window. This generalizes the Line Planning Problem, a widely studied topic in the transportation literature, for which existing solutions are either heuristic (with no performance guarantees), or require extensive computation time (and hence are impractical for real-time use). To this end, we develop a 1-1/e-ε approximation algorithm for the Real-Time Line Planning Problem, using ideas from randomized rounding and the Generalized Assignment Problem. Our guarantee holds under two assumptions: (i) no inter-bus transfers and (ii) access to a pre-specified set of feasible bus lines. We moreover show that these two assumptions are crucial by proving that, if either assumption is relaxed, the łineplanningproblem does not admit any constant-factor approximation. Finally, we demonstrate the practicality of our algorithm via numerical experiments on real-world and synthetic datasets, in which we show that, given a fixed time budget, our algorithm outperforms Integer Linear Programming-based exact methods.

References

[1]

Javier Alonso-Mora, Samitha Samaranayake, Alex Wallar, Emilio Frazzoli, and Daniela Rus. 2017. On-demand highcapacity ride-sharing via dynamic trip-vehicle assignment. Proceedings of the National Academy of Sciences 114, 3 (2017), 462--467.

[2]

Siddhartha Banerjee, Daniel Freund, and Thodoris Lykouris. 2016. Pricing and optimization in shared vehicle systems: An approximation framework. arXiv preprint arXiv:1608.06819 (2016).

[3]

Siddhartha Banerjee, Yash Kanoria, and Pengyu Qian. 2018. State dependent control of closed queueing networks. In ACM SIGMETRICS '18.

Digital Library

[4]

Alexandre Barra, Luis Carvalho, Nicolas Teypaz, Van-Dat Cung, and Ronaldo Balassiano. 2007. Solving the transit network design problem with constraint programming.

[5]

Dimitri P Bertsekas. 1991. Linear network optimization: algorithms and codes. MIT press.

[6]

Robert G Bland, Donald Goldfarb, and Michael J Todd. 1981. The ellipsoid method: A survey. Operations research 29, 6 (1981), 1039--1091.

[7]

Geoff Boeing. 2017. OSMnx: A Python package to work with graph-theoretic OpenStreetMap street networks. Journal of Open Source Software 2, 12 (2017).

[8]

Ralf Borndörfer and Marika Karbstein. 2012. A direct connection approach to integrated line planning and passenger routing. In 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

[9]

Ralf Borndörfer, Martin Grötschel, and Marc E. Pfetsch. 2007. A Column-Generation Approach to Line Planning in Public Transport. Transportation Science 41, 1 (2007), 123--132.

Digital Library

[10]

Anton Braverman, Jim G Dai, Xin Liu, and Lei Ying. 2019. Empty-car routing in ridesharing systems. Operations Research 67, 5 (2019), 1437--1452.

Digital Library

[11]

Robert Carr and Santosh Vempala. 2000. Randomized metarounding. In Proceedings of the thirty-second annual ACM symposium on Theory of computing. 58--62.

Digital Library

[12]

Avishai Ceder and Nigel H.M. Wilson. 1986. Bus network design. Transportation Research Part B: Methodological 20, 4 (1986), 331 -- 344.

[13]

Partha Chakroborty and Tathagat Wivedi. 2002. Optimal Route Network Design for Transit Systems Using Genetic Algorithms. Engineering Optimization 34, 1 (2002), 83--100.

[14]

Chandra Chekuri and Martin Pal. 2005. A recursive greedy algorithm for walks in directed graphs. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05). IEEE, 245--253.

Digital Library

[15]

Guy Desaulniers, Jacques Desrosiers, and Marius M Solomon. 2006. Column generation. Vol. 5. Springer Science & Business Media.

[16]

D. Dubois, G. Bel, and M. Llibre. 1979. A Set of Methods in Transportation Network Synthesis and Analysis. The Journal of the Operational Research Society 30, 9 (1979), 797--808.

[17]

T. Erlebach and F.C.R. Spieksma. 2003. Interval selection: applications, algorithms, and lower bounds. Journal of Algorithms 46, 1 (Jan. 2003), 27--53. https://doi.org/10.1016/S0196--6774(02)00291--2

[18]

Wei Fan and Randy B. Machemehl. 2006. Using a Simulated Annealing Algorithm to Solve the Transit Route Network Design Problem. Journal of Transportation Engineering 132, 2 (2006), 122--132.

[19]

Reza Zanjirani Farahani, Elnaz Miandoabchi, Wai Yuen Szeto, and Hannaneh Rashidi. 2013. A review of urban transportation network design problems. European Journal of Operational Research 229, 2 (2013), 281--302.

[20]

Emma G. Fitzsimmons. 2016. Surge in Ridership Pushes New York Subway to Limit. The New York Times (2016).

[21]

Lisa Fleischer, Michel X Goemans, Vahab S Mirrokni, and Maxim Sviridenko. 2011. Tight approximation algorithms for maximum separable assignment problems. Mathematics of Operations Research 36, 3 (2011), 416--431.

Digital Library

[22]

Philine Gattermann, Jonas Harbering, and Anita Schöbel. 2017. Line pool generation. Public Transport 9, 1--2 (2017), 7--32.

[23]

Valérie Guihaire and Jin-Kao Hao. 2008. Transit network design and scheduling: A global review. Transportation Research Part A: Policy and Practice 42, 10 (2008), 1251--1273.

[24]

LLC Gurobi Optimization. 2021. Gurobi Optimizer Reference Manual. http://www.gurobi.com

[25]

AJ Hawkins. 2017. Lyft Shuttle mimics mass transit with fixed routes and fares. The Verge (2017). https://www.theverge.com/2017/3/29/15111492/lyft-shuttle-fixed-route-fare-sf-chicago

[26]

Doug Johnson. 2020. Microtransit Gives City Agencies a Lift During the Pandemic. Wired (2020). https://www.wired.com/story/microtransit-gives-city-agencies-a-lift-during-the-pandemic/

[27]

Christos Kalaitzis, Aleksander Madry, Alantha Newman, Luká? Polácek, and Ola Svensson. 2015. On the configuration LP for maximum budgeted allocation. Mathematical Programming 154, 1--2, 427--462.

Digital Library

[28]

Yash Kanoria and Pengyu Qian. 2019. Near optimal control of a ride-hailing platform via mirror backpressure. arXiv preprint arXiv:1903.02764 (2019).

[29]

Tai-Yu Ma. 2017. On-demand dynamic Bi-multi-modal ride-sharing using optimal passenger-vehicle assignments. In 2017 IEEE International Conference on Environment and Electrical Engineering and 2017 IEEE Industrial and Commercial Power Systems Europe (EEEIC/I & CPS Europe). IEEE, 1--5.

[30]

Tai-Yu Ma, Saeid Rasulkhani, Joseph YJ Chow, and Sylvain Klein. 2019. A dynamic ridesharing dispatch and idle vehicle repositioning strategy with integrated transit transfers. Transportation Research Part E: Logistics and Transportation Review 128 (2019), 417--442.

[31]

Thomas L Magnanti and Richard T Wong. 1984. Network design and transportation planning: Models and algorithms. Transportation science 18, 1 (1984), 1--55.

[32]

Pasin Manurangsi. 2017. Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. 954--961.

Digital Library

[33]

Ángel G Marín and Patricia Jaramillo. 2009. Urban rapid transit network design: accelerated Benders decomposition. Annals of Operations Research 169, 1 (2009), 35--53.

[34]

Karl Nachtigall and Karl Jerosch. 2008. Simultaneous network line planning and traffic assignment. In 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08). Schloss Dagstuhl-Leibniz-Zentrum für Informatik.

[35]

Jake Offenhartz. 2020. MTA Will End Free Cab Rides For EssentialWorkers, As Overnight Subway Shutdown Continues. Gothamist (2020). https://gothamist.com/news/mta-will-end-free-cab-rides-essential-workers-overnight-subwayshutdown-continues

[36]

Uwe Pape, Yean-Suk Reinecke, and Erwin Reinecke. 1995. Line network planning. In Computer-Aided Transit Scheduling. Springer, 1--7.

[37]

Paolo Santi, Giovanni Resta, Michael Szell, Stanislav Sobolevsky, Steven H. Strogatz, and Carlo Ratti. 2014. Quantifying the benefits of vehicle pooling with shareability networks. Proceedings of the National Academy of Sciences 111, 37 (2014), 13290--13294.

[38]

Thibault Séjourné, Samitha Samaranayake, and Siddhartha Banerjee. 2018. The price of fragmentation in mobility-ondemand services. Proceedings of the ACM on Measurement and Analysis of Computing Systems 2, 2 (2018), 1--26.

Digital Library

[39]

Lionel Adrian Silman, Zeev Barzily, and Ury Passy. 1974. Planning the route system for urban buses. Computers & operations research 1, 2 (1974), 201--211.

[40]

Mitja Stiglic, Niels Agatz, Martin Savelsbergh, and Mirko Gradisar. 2018. Enhancing urban mobility: Integrating ride-sharing and public transit. Computers & Operations Research 90 (2018), 12--21.

Digital Library

[41]

Pranshu Verma. 2020. 'We're Desperate': Transit Cuts Felt Deepest in Low-Income Areas . The New York Times (2020).

[42]

José Verschae and Andreas Wiese. 2014. On the configuration-LP for scheduling on unrelated machines. Journal of Scheduling 17, 4 (2014), 371--383.

Digital Library

[43]

Quentin K Wan and Hong K Lo. 2003. A mixed integer formulation for multiple-route transit network design. Journal of Mathematical Modelling and Algorithms 2, 4 (2003), 299--308.

[44]

Laurence A. Wolsey. 1982. Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems. Mathematics of Operations Research 7, 3 (1982), 410--425.

Digital Library

[45]

Fang Zhao and Ike Ubaka. 2004. Transit network optimization-minimizing transfers and optimizing route directness. Journal of Public Transportation 7, 1 (2004), 4.

[46]

Fang Zhao and Xiaogang Zeng. 2006. Simulated annealing--genetic algorithm for transit network optimization. Journal of Computing in Civil Engineering 20, 1 (2006), 57--68.

Cited By

Jiang HSamaranayake S(2024)Approximation algorithm for generalized budgeted assignment problems and applications in transportation systemsDiscrete Applied Mathematics10.1016/j.dam.2024.09.020359(383-399)Online publication date: Dec-2024
https://doi.org/10.1016/j.dam.2024.09.020
Fielbaum AJara-Díaz SAlonso-Mora J(2024)Beyond the last mile: different spatial strategies to integrate on-demand services into public transport in a simplified cityPublic Transport10.1007/s12469-023-00348-116:3(855-892)Online publication date: 2-Sep-2024
https://doi.org/10.1007/s12469-023-00348-1
Zhao TLi WQin BWang LZomaya A(2023)Pulsed Power Load Coordination in Mission- and Time-critical Cyber-physical SystemsACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/35731978:1-2(1-27)Online publication date: 7-Mar-2023
https://dl.acm.org/doi/10.1145/3573197
Show More Cited By

Index Terms

Real-time Approximate Routing for Smart Transit Systems
1. Computer systems organization
  1. Dependable and fault-tolerant systems and networks
    1. Redundancy
  2. Embedded and cyber-physical systems
    1. Embedded systems
    2. Robotics
2. Networks
  1. Network properties
    1. Network reliability

Recommendations

Real-time Approximate Routing for Smart Transit Systems
SIGMETRICS '21: Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems

The advent of ride-hailing platforms such as Lyft and Uber has revolutionized urban mobility in the past decade. Given their increasingly important role in today's society, recent years have seen growing interest in integrating these services with mass ...
Real-time Approximate Routing for Smart Transit Systems
SIGMETRICS '21

The advent of ride-hailing platforms such as Lyft and Uber has revolutionized urban mobility in the past decade. Given their increasingly important role in today's society, recent years have seen growing interest in integrating these services with mass ...
Approximate Sparse Recovery: Optimizing Time and Measurements

A Euclidean approximate sparse recovery system consists of parameters $k,N$, an $m$-by-$N$ measurement matrix, $\bm{\Phi}$, and a decoding algorithm, $\mathcal{D}$. Given a vector, ${\mathbf x}$, the system approximates ${\mathbf x}$ by $\widehat {\...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the ACM on Measurement and Analysis of Computing Systems

Proceedings of the ACM on Measurement and Analysis of Computing Systems Volume 5, Issue 2

POMACS

June 2021

424 pages

EISSN:2476-1249

DOI:10.1145/3469656

Editors:
Augustin Chaintreau
Columbia University
,
Leana Golubchik
University of Southern California
,
Zhi-Li Zhang
University of Minnesota

Issue’s Table of Contents

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 June 2021

Published in POMACS Volume 5, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
505
Total Downloads

Downloads (Last 12 months)113
Downloads (Last 6 weeks)16

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jiang HSamaranayake S(2024)Approximation algorithm for generalized budgeted assignment problems and applications in transportation systemsDiscrete Applied Mathematics10.1016/j.dam.2024.09.020359(383-399)Online publication date: Dec-2024
https://doi.org/10.1016/j.dam.2024.09.020
Fielbaum AJara-Díaz SAlonso-Mora J(2024)Beyond the last mile: different spatial strategies to integrate on-demand services into public transport in a simplified cityPublic Transport10.1007/s12469-023-00348-116:3(855-892)Online publication date: 2-Sep-2024
https://doi.org/10.1007/s12469-023-00348-1
Zhao TLi WQin BWang LZomaya A(2023)Pulsed Power Load Coordination in Mission- and Time-critical Cyber-physical SystemsACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/35731978:1-2(1-27)Online publication date: 7-Mar-2023
https://dl.acm.org/doi/10.1145/3573197
Banerjee SHssaine CLuo QSamaranayake S(undefined)Plan Your System and Price for Free: Fast Algorithms for Multimodal Transit OperationsSSRN Electronic Journal10.2139/ssrn.3972423
https://doi.org/10.2139/ssrn.3972423

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents