Parameterized algorithms for generalized traveling salesman problems in road networks

Abstract

The Generalized Traveling Salesman (Path) Problem involves finding a minimum-cost tour (or path) through exactly one location from each of a set of generalized location categories (e.g., gas stations, coffee shops). This problem type has many practical applications in personal navigation and logistics. While NP-hard in general, this problem also admits fixed-parameter tractable (FPT) algorithms with run times of the form f(k)n^O(1) for some function f (independent of the problem size, n) with respect to the number of location categories, k (typically very small in practice). We present both exact and approximate FPT algorithms for this problem. Experimental results on the road network of North America (with over 50 million edges) show that we can optimally solve nationwide queries with up to 7 categories and millions of optional category locations in sub-second time. Our approximate solutions improve this even further down to millisecond query times, resulting in only negligible relative error with respect to optimality, on average.