Fast Algorithms for Computing Fixed-Length Round Trips in Real-World Street Networks

This paper proposes several algorithms for calculating fixed-length round trips on directed street networks. Unlike previous approaches, these algorithms do not need to download, process, or store large map databases; instead, the relevant information is collected using a small number of calls to online mapping APIs, with the remaining computation performed on the client side. This is particularly useful when solutions need to span large geographical areas. Our most successful approach is based on multiobjective local search. This makes use of specialised operators that exploit the underlying graph-theoretical properties of the problem, giving run times that are typically less than five seconds