线路旅行推销员 (TSP)、扫雪

Question

在典型的 TSP 算法中，我们有多个点，并且希望以最佳的行进顺序行进。点是家庭、顾客等，基本上是地图上的一个点。

我用线代替点。扫雪就是一个很好的例子，你可以在多条街道上行驶。最大的区别是，对于每次旅行，结束点与起点不同。我的尝试是假设起点作为每次旅行的唯一节点。但显然，每当你的路线/线路很长时，你最终都会到达距离起点很远的地方。而且这个解决方案已经远非最佳了。

我查看了一些提供路线优化的公司。他们的解决方案就是将线分成接近的点；并将每条线视为彼此靠近的节点。我认为当你必须穿过街道的两侧，或者每当你靠近另一条街道时，这是行不通的。

我想知道是否有建模技巧或其他方法来解决这个问题？

Answer 1

实际上，您在问题中提出了四个完全不同的挑战，由两个主要挑战和两个子挑战组成。

挑战一：单向街道遍历

在这种情况下，面临的挑战是在给定一组仅需要沿一个方向穿过的街道的情况下找到最佳路线。这个挑战本身可以进一步细分为两个挑战。

挑战1A：单向街道穿越，强制完成

在这个挑战中，推销员需要遍历整条街道，然后才能前往下一条街道。对于这一挑战，每条街道都可以通过其两个端点进行建模，并且可以通过 TSP 算法进行一次修改来解决该问题。当算法选择考虑街道的一个端点时，推销员会重新定位到街道的另一端点，并且两个端点都标记为已完成。

挑战 1B：单向街道穿越，可选择旁路行驶

与挑战 1A 类似，不同之处在于允许推销员离开一条街道，以便穿过一条或多条其他街道，然后返回完成当前街道。对于这个挑战，每条街道都可以建模为一系列要访问的点，解决方案是标准的 TSP 算法。

挑战二：双向街道遍历

在这种情况下，面临的挑战是在给定一组需要双向穿过或至少两侧都有兴趣点的街道的情况下找到最佳路线。这个挑战本身可以进一步细分为两个挑战。

挑战2A：强制完成的双向街道遍历

这是邮递员问题和/或混合运输模式问题。想象一个假想的邮递员，他从一辆装满邮件的卡车开始。在每条街道上，一些邮件都会被装入邮递员步行到每家每户的袋子中。邮递员在街道的一侧投递邮件，然后返回卡车，同时在街道的另一侧投递邮件。换句话说，旅行推销员需要返回其出发地，以便继续使用替代的运输方式。对于这一挑战，每条街道都可以通过其两个端点进行建模，并且可以通过 TSP 算法进行一次修改来解决该问题。一旦算法考虑了街道的一个端点，另一个端点就会从考虑中删除。

挑战 2B：双向街道穿越并乱穿马路

这是四个挑战中最困难的一个。这里的问题是，前往地理位置较近的地点可能无法提供最佳解决方案。例如，在乡村道路上，乱穿马路可能是合法且安全的。然而，在四车道的林荫大道上，乱穿马路可能是非法的，而且极其危险。此外，在等待交通中断时可能会出现相当长的时间延迟，从而导致人们试图乱穿马路。为了解决这个问题，必须修改TSP算法以包含成本函数。在正常的 TSP 算法中，两点之间的行驶成本与两点之间的距离成正比。但对于这一挑战，算法必须首先考虑每对点，并计算在这两点之间移动的成本。然后可以使用标准 TSP 算法根据这些成本找到最佳路由。