Chris Harrelson

Chris Harrelson

Authored Publications
Sort By
  • Title
  • Title, descending
  • Year
  • Year, descending
    Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns
    Hannah Bast
    Erik Carlsson
    Veselin Raychev
    Algorithms - ESA 2010, 18th Annual European Symposium. Proceedings, Part I, Springer, pp. 290-301
    Preview abstract We show how to route on very large public transportation networks (up to half a billion arcs) with average query times of a few milliseconds. We take into account many realistic features like: traffic days, walking between stations, queries between geographic locations instead of a source and a target station, and multi-criteria cost functions. Our algorithm is based on two key observations: (1) many shortest paths share the same transfer pattern, i.e., the sequence of stations where a change of vehicle occurs; (2) direct connections without change of vehicle can be looked up quickly. We precompute the respective data; in practice, this can be done in time linear in the network size, at the expense of a small fraction of non-optimal results. We have accelerated public transportation routing on Google Maps with a system based on our ideas. We report experimental results for three data sets of various kinds and sizes. View details
    The k-Traveling Repairmen Problem
    Jittat Fakcharoenphol
    ACM Transactions on Algorithms, 3, no. 4 (2007), pp. 1-16
    Preview