Efficient many-to-many path planning and the Traveling Salesman Problem on road networks

摘要

To compute optimal paths between locations in road networks is an important operation for e.g. transport business. Efficient algorithms for path planning usually assume a single start and a single target. In some scenarios, however, we want to compute all shortest paths from a set of starts to a set of targets. If we use the one-to-one planning in a loop, we consider each path as an independent computation. The drawback: we cannot take benefit of similarities between planning steps. In this paper, we present an approach that addresses this problem and provides a many-to-many path planning. An example that is heavily based on many-to-many path planning: given a home depot and a set of delivery points, what is the optimal round-trip that starts at the home depot, approaches each delivery point and turns back to the home depot. This problem is known as the Traveling Salesman Problem, but usually it is not applied to realroad networks. In this paper we describe the efficient many-to-many path planning that is based on A*. It significantly reduces the number of visited crossings due to computation similarities. We adapt the approach to provide a solution for the Traveling Salesman Problem on road networks.