1
$\begingroup$

In the classical traveling salesman problem, we are given a graph of cities with distances between each city and are asked to find the shortest path that traverses all of the cities. Meaning that the number of cities we visit is fixed, and we are optimizing over the distance.

Suppose instead we have a given threshold of $d$ miles that our salesman can at most travel, and we want to maximize the number of cities he can visit without exceeding $d$. Meaning that the distance is fixed, and we optimize over number of cities. Is there any literature on this variant of TSP?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Seems to be a dual formulation of the "subset-tour problem", where you minimize the length, subject to the requirement of visiting $k$ cities. $\endgroup$
    – Jukka Kohonen
    Commented Feb 8, 2023 at 18:34
  • $\begingroup$ @JukkaKohonen I see, so I would just increase $k$ until the minimum length surpasses the prescribed threshold on the distance. Thanks! $\endgroup$
    – MathManiac5772
    Commented Feb 8, 2023 at 18:37
  • 3
    $\begingroup$ Search for orienteering problem $\endgroup$
    – RobPratt
    Commented Feb 8, 2023 at 20:28

0

Reset to default

You must log in to answer this question.