A fresh look at the Traveling Salesman Problem with a Center.
Luo, Yuchen; Golden, Bruce; Poikonen, Stefan; Zhang, Rui. A fresh look at the Traveling Salesman Problem with a Center. Computers & Operations Research. Jul2022, Vol. 143, pN.PAG-N.PAG.ÌýÌýÌýÌý
In the traveling salesman problem (TSP), one has to find the shortest tour through a number of locations in a region. Since the objective is to minimize the length of a tour, edges in the optimal tour may be far away from the geometric center of the region. However, for some practical applications such as police patrol, we prefer to obtain a tour that is short in length and stays close to a high-crime (centrally located) neighborhood. We formulate this problem as the Traveling Salesman Problem with a Center (TSPC), in which we minimize an energy function including L (the length of a tour) and C (the distance from a tour to the center, defined by some metric). To address the TSPC, we propose a metric to measure C rather accurately and also introduce the idea of a triangular path, in which the vehicle no longer travels in a straight line between two nodes. Finally, we show that under identical circumstances, the tour with triangular paths remains closer to the center than a tour using all direct edges both in a Euclidean graph and in a grid network. • Propose a novel average distance measure for the distance from a tour to the center. • Introduce two new variants of the energy function to smooth the phase transition. • Propose the concept of triangular paths to get closer to the center. • Present our findings in both Euclidean graphs and grid networks. • Derive efficient computational approaches for finding optimal or near-optimal solutions.ÌýÌýÌýÌý
Ìý