无回程且指定起止城市的旅行推销员

Question

我正在寻找以下问题的名称：旅行推销员问题（每个城市恰好访问一次），但不返回起始城市并在结束时访问给定城市。也就是说，我想指定起始城市和结束城市，并且不想回到起始城市。 谢谢！！！

Answer 1

我怀疑它有自己的名字，因为它与普通的 TSP 基本同构。

• 从标准 TSP 到此：给定 TSP 的有向加权图，具有起始/结束节点，将起始/结束节点分为起始节点和结束节点，所有出边都在起始节点上，所有入边都在起始节点上。末端节点上的边。
• 从此到标准TSP：从端节点删除所有出边；从结束节点到开始节点（现在是开始/结束节点）添加一条边。

Answer 2

您所描述的问题，即您想要访问每个城市一次，并指定起始城市和结束城市，并且不返回起始城市，通常称为“开放旅行商问题”（开放 TSP）。在标准旅行商问题（TSP）中，目标是找到最短路线，该路线恰好访问每个城市一次并返回出发城市。 Open TSP 放宽了返回起始城市的要求，允许不同的结束城市。