0
$\begingroup$

In the Dubins TSP (DTSP for short), one needs to visit a set of given points in the plane, and return to the starting point, minimizing the distance of such a trajectory. The difference with the Euclidean TSP (ETSP for short) however is that the visiting entity is curvature constrained by some $r$, meaning the vehicle can, at any moment in time, either go straight, or move on the edge of some circle of radius $r'\geq r$.

Consider the following theorem, by Le Ny et al. (Theorem 2 in http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.84.982&rep=rep1&type=pdf) which we will call Theorem 1 in this post :

A trajectory based on an ETSP optimal visit order, is not necessarily an optimal trajectory for the DTSP.

(I changed the wording of their theorem to suit this post)

Suppose the next theorem, Theorem 2 :

There exists instances for which the optimal DTSP visit order creates a crossing ETSP trajectory.

My question is : Does Theorem 2 imply Theorem 1 ?
The idea is as follows. Since some instances have the optimal DTSP visit order creating a crossing ETSP trajectory $T$, this ETSP trajectory $T$ is not optimal (due to the triangle inequality). This in turn implies that some optimal ETSP trajectory $T*$ on these instances (or their corresponding optimal ETSP visit order) cannot be adapted and optimized to obtain the optimal DTSP trajectory. If it could, then $T = T*$, which is a contradiction, since $T$ admits a crossing trajectory.

$\endgroup$
1
$\begingroup$

No, theorem 2 does not imply theorem 1 unless you also prove for that instance that every optimal DTSP visit order creates a crossing ETSP trajectory. There might be another optimal DTSP $|T'| = |T|$ visit order that does not result in a crossing ETSP so that we have $T* = T'$.

$\endgroup$
  • $\begingroup$ It is for this reason I used " THE optimal DTSP visit order " in Theorem 2, not just " an optimal DTSP visit order ". So, assuming there exists only one unique optimal DTSP visit order creating a crossing ETSP trajectory, Theorem 2 should imply Theorem 1 ? $\endgroup$ – J. Schmidt Jul 8 at 12:28
  • 1
    $\begingroup$ @J.Schmidt If it is unique, then yes. $\endgroup$ – orlp Jul 8 at 13:01
  • $\begingroup$ @orip You answered my question, but I would like to know also if Theorem 2 is considered "stronger" than Theorem 1 (again, assuming only one optimal DTSP visit order exists) $\endgroup$ – J. Schmidt Jul 9 at 9:55
  • $\begingroup$ @J.Schmidt Yes it's stronger under that assumption because it implies the other theorem but not the other way around. However I'm not convinced that the assumption holds at all. $\endgroup$ – orlp Jul 9 at 10:07
  • $\begingroup$ @orip I was thinking it holds for some dense points on the edge of two circles of radius $r$, gathered close to form an 8-like form (without the middle of the 8), i.e. something like this : imgur.com/ZUpreV0 $\endgroup$ – J. Schmidt Jul 9 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.