@article{721,
  author = {Noémie Périvier and Chamsi Hssaine and Samitha Samaranayake and Siddhartha Banerjee},
  title = {Real-time Approximate Routing for Smart Transit Systems},
  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.},
  year = {2021},
  journal = {Proceedings of the ACM on Measurement and Analysis of Computing Systems},
  volume = {5},
  chapter = {1},
  pages = {30},
  month = {06},
  issn = {2476-1249},
  url = {https://par.nsf.gov/biblio/10295624},
  doi = {10.1145/3460091},
}