Journal
COMPUTERS & OPERATIONS RESEARCH
Volume 143, Issue -, Pages -Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2022.105748
Keywords
Integer programming; Traveling salesman problem; Heuristics
Ask authors/readers for more resources
In this article, the author introduces a problem called TSPC, which aims to find a path that is both short and close to the center. To address this problem, the author proposes a new metric and the concept of triangular paths.
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available