Web-based and mobile navigation systems motivated a large body of work on routing algorithms that took place in the last decade. The development of these algorithms has been influenced by the developments of the underlying technology. As computer memories got bigger, more detailed maps with broader coverage, and real-time traffic data and public transit data became available in electronic form, additional demands have been placed on routing algorithms. Both larger problems and more difficult problems needed to be solved quickly, and new algorithms have been developed to solve these problems. We discuss these algorithms and current challenges in the area.

Andrew Goldberg

Andrew Goldberg

Principal Researcher, Microsoft Research

Andrew V. Goldberg is a Principal Researcher at Microsoft Research—Silicon Valley. His research interests include design, analysis, and experimental evaluation of algorithms, data structures, algorithm engineering, and computational game theory. Goldberg received his PhD degree in Computer Science from M.I.T. in 1987. Before joining Microsoft, he worked for Stanford University, NEC Research Institute, and InterTrust STAR Lab. His graph algorithms are taught in computer science and operations research classes and their implementations are widely used in industry and academia. Goldberg received a number of awards, including the NSF Presidential Young Investigator Award, the ONR Young Investigator Award, and the Mathematical Programming Society A.W. Tucker Prize. He is an ACM Fellow.