{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T17:24:20Z","timestamp":1764350660590,"version":"3.41.0"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,6,1]],"date-time":"2021-06-01T00:00:00Z","timestamp":1622505600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100006754","name":"Army Research Laboratory","doi-asserted-by":"publisher","award":["W911NF-17-1-0094"],"award-info":[{"award-number":["W911NF-17-1-0094"]}],"id":[{"id":"10.13039\/100006754","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1839346, CNS-1952011, ECCS-1847393, CNS-1955997"],"award-info":[{"award-number":["DMS-1839346, CNS-1952011, ECCS-1847393, CNS-1955997"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2021,6]]},"abstract":"<jats:p>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-\u03b5 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 \u0142ineplanningproblem 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.<\/jats:p>","DOI":"10.1145\/3460091","type":"journal-article","created":{"date-parts":[[2021,6,4]],"date-time":"2021-06-04T14:44:15Z","timestamp":1622817855000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Real-time Approximate Routing for Smart Transit Systems"],"prefix":"10.1145","volume":"5","author":[{"given":"No\u00e9mie","family":"P\u00e9rivier","sequence":"first","affiliation":[{"name":"Columbia University, New York, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chamsi","family":"Hssaine","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Samitha","family":"Samaranayake","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Siddhartha","family":"Banerjee","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,6,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1611675114"},{"key":"e_1_2_1_2_1","volume-title":"Pricing and optimization in shared vehicle systems: An approximation framework. arXiv preprint arXiv:1608.06819","author":"Banerjee Siddhartha","year":"2016","unstructured":"Siddhartha Banerjee , Daniel Freund , and Thodoris Lykouris . 2016. Pricing and optimization in shared vehicle systems: An approximation framework. arXiv preprint arXiv:1608.06819 ( 2016 ). Siddhartha Banerjee, Daniel Freund, and Thodoris Lykouris. 2016. Pricing and optimization in shared vehicle systems: An approximation framework. arXiv preprint arXiv:1608.06819 (2016)."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219617.3219619"},{"key":"e_1_2_1_4_1","unstructured":"Alexandre Barra Luis Carvalho Nicolas Teypaz Van-Dat Cung and Ronaldo Balassiano. 2007. Solving the transit network design problem with constraint programming.  Alexandre Barra Luis Carvalho Nicolas Teypaz Van-Dat Cung and Ronaldo Balassiano. 2007. Solving the transit network design problem with constraint programming."},{"volume-title":"Linear network optimization: algorithms and codes","author":"Bertsekas Dimitri P","key":"e_1_2_1_5_1","unstructured":"Dimitri P Bertsekas . 1991. Linear network optimization: algorithms and codes . MIT press . Dimitri P Bertsekas. 1991. Linear network optimization: algorithms and codes. MIT press."},{"key":"e_1_2_1_6_1","volume-title":"The ellipsoid method: A survey. Operations research 29, 6","author":"Bland Robert G","year":"1981","unstructured":"Robert G Bland , Donald Goldfarb , and Michael J Todd . 1981. The ellipsoid method: A survey. Operations research 29, 6 ( 1981 ), 1039--1091. Robert G Bland, Donald Goldfarb, and Michael J Todd. 1981. The ellipsoid method: A survey. Operations research 29, 6 (1981), 1039--1091."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.21105\/joss.00215"},{"key":"e_1_2_1_8_1","volume-title":"12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.","author":"Bornd\u00f6rfer Ralf","year":"2012","unstructured":"Ralf Bornd\u00f6rfer 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. Ralf Bornd\u00f6rfer 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."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.1060.0161"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2018.1822"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335312"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0191-2615(86)90047-0"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1080\/03052150210909"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.9"},{"volume-title":"Column generation","author":"Desaulniers Guy","key":"e_1_2_1_15_1","unstructured":"Guy Desaulniers , Jacques Desrosiers , and Marius M Solomon . 2006. Column generation . Vol. 5 . Springer Science & Business Media . Guy Desaulniers, Jacques Desrosiers, and Marius M Solomon. 2006. Column generation. Vol. 5. Springer Science & Business Media."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1979.190"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(02)00291-2"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1061\/(ASCE)0733-947X(2006)132:2(122)"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2013.01.001"},{"key":"e_1_2_1_20_1","volume-title":"Surge in Ridership Pushes New York Subway to Limit. The New York Times","author":"Fitzsimmons Emma G.","year":"2016","unstructured":"Emma G. Fitzsimmons . 2016. Surge in Ridership Pushes New York Subway to Limit. The New York Times ( 2016 ). Emma G. Fitzsimmons. 2016. Surge in Ridership Pushes New York Subway to Limit. The New York Times (2016)."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1110.0499"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12469-016-0127-x"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tra.2008.03.011"},{"key":"e_1_2_1_24_1","unstructured":"LLC Gurobi Optimization. 2021. Gurobi Optimizer Reference Manual. http:\/\/www.gurobi.com  LLC Gurobi Optimization. 2021. Gurobi Optimizer Reference Manual. http:\/\/www.gurobi.com"},{"key":"e_1_2_1_25_1","volume-title":"Lyft Shuttle mimics mass transit with fixed routes and fares. The Verge","author":"Hawkins AJ","year":"2017","unstructured":"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 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"},{"key":"e_1_2_1_26_1","volume-title":"Microtransit Gives City Agencies a Lift During the Pandemic. Wired","author":"Johnson Doug","year":"2020","unstructured":"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\/ 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\/"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0928-8"},{"key":"e_1_2_1_28_1","volume-title":"Near optimal control of a ride-hailing platform via mirror backpressure. arXiv preprint arXiv:1903.02764","author":"Kanoria Yash","year":"2019","unstructured":"Yash Kanoria and Pengyu Qian . 2019. Near optimal control of a ride-hailing platform via mirror backpressure. arXiv preprint arXiv:1903.02764 ( 2019 ). Yash Kanoria and Pengyu Qian. 2019. Near optimal control of a ride-hailing platform via mirror backpressure. arXiv preprint arXiv:1903.02764 (2019)."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/EEEIC.2017.7977646"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tre.2019.07.002"},{"key":"e_1_2_1_31_1","volume-title":"Network design and transportation planning: Models and algorithms. Transportation science 18, 1","author":"Magnanti Thomas L","year":"1984","unstructured":"Thomas L Magnanti and Richard T Wong . 1984. Network design and transportation planning: Models and algorithms. Transportation science 18, 1 ( 1984 ), 1--55. Thomas L Magnanti and Richard T Wong. 1984. Network design and transportation planning: Models and algorithms. Transportation science 18, 1 (1984), 1--55."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055412"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-008-0388-0"},{"key":"e_1_2_1_34_1","volume-title":"8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08)","author":"Nachtigall Karl","year":"2008","unstructured":"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\u00fcr Informatik. 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\u00fcr Informatik."},{"key":"e_1_2_1_35_1","volume-title":"As Overnight Subway Shutdown Continues. Gothamist","author":"Offenhartz Jake","year":"2020","unstructured":"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 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"},{"volume-title":"Computer-Aided Transit Scheduling","author":"Pape Uwe","key":"e_1_2_1_36_1","unstructured":"Uwe Pape , Yean-Suk Reinecke , and Erwin Reinecke . 1995. Line network planning . In Computer-Aided Transit Scheduling . Springer , 1--7. Uwe Pape, Yean-Suk Reinecke, and Erwin Reinecke. 1995. Line network planning. In Computer-Aided Transit Scheduling. Springer, 1--7."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1403657111"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3224425"},{"key":"e_1_2_1_39_1","volume-title":"Planning the route system for urban buses. Computers & operations research 1, 2","author":"Silman Lionel Adrian","year":"1974","unstructured":"Lionel Adrian Silman , Zeev Barzily , and Ury Passy . 1974. Planning the route system for urban buses. Computers & operations research 1, 2 ( 1974 ), 201--211. Lionel Adrian Silman, Zeev Barzily, and Ury Passy. 1974. Planning the route system for urban buses. Computers & operations research 1, 2 (1974), 201--211."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2017.08.016"},{"key":"e_1_2_1_41_1","volume-title":"We're Desperate': Transit Cuts Felt Deepest in Low-Income Areas . The New York Times","author":"Verma Pranshu","year":"2020","unstructured":"Pranshu Verma . 2020. ' We're Desperate': Transit Cuts Felt Deepest in Low-Income Areas . The New York Times ( 2020 ). Pranshu Verma. 2020. 'We're Desperate': Transit Cuts Felt Deepest in Low-Income Areas . The New York Times (2020)."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-013-0359-4"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:JMMA.0000020425.99217.cd"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.7.3.410"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5038\/2375-0901.7.1.4"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1061\/(ASCE)0887-3801(2006)20:1(57)"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3460091","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3460091","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3460091","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:28Z","timestamp":1750195708000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3460091"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6]]},"references-count":46,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["10.1145\/3460091"],"URL":"https:\/\/doi.org\/10.1145\/3460091","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2021,6]]},"assertion":[{"value":"2021-06-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}