Efficient Path Planning Involving Equivalent Places

Abstract

This paper investigates a complication of the classical Traveling Salesman Problem, which arises due to multiple points of interest with functional equivalence. While the classical Traveling Salesman Problem tries to find a shortest tour visiting each point in a set exactly once, we consider the challenge of finding the shortest tour visiting each point of a given set exactly once and exactly one additional point out of a different set of equivalent places. The insertion of a gas station to a traveling salesman problem provides an example. With this paper, we investigate and analyze different algorithms to solve this complex problem by reducing it to the solution of a set of classic Traveling Salesman Problems. Furthermore, we provide an efficient tradeoff between the size of the set of traditional problems still to be solved and the expected error of the algorithm.

Publication
10. GI/ITG KuVS Fachgespräch Ortsbezogene Anwendungen und Dienste (LBAS 2013)