language-agnostic - 创建公交路线

Question

什么是可用于创建公交路线的好算法或算法类别？

我正在考虑用于解决旅行推销员或哈密顿路径问题的算法，但实际上，它们都没有真正解决如何在两站之间移动的问题。

我希望算法至少具有以下特征:

产生一个相对优化的路径(我理解这个问题可能是 NP 完全的，所以一个好的启发式是可以的)

可以处理具有不同权重的路径部分(例如在路径的该部分上行进的时间)

可以强制使用给定的起点和终点(我不认为这个会有这样的问题)

可以执行此操作的代码或类似的代码将受到赞赏(尤其是在 C# 中)，但一个好的算法本身就可以了。

注:虽然有很多算法可以找到两点之间的最短路径，但我不知道我希望停止的顺序。因此，除非我应该使用两种算法的组合(我怀疑是这种情况)，否则这些算法不会做我想要的(如果您认为它们可以，请解释)。

编辑:假设我知道需要进行的所有停靠点。

Answer 1

这样做的方法似乎涉及使用 Floyd-Warshall 算法，然后使用用于解决旅行商问题的算法。

这解决了所有“可选”顶点(交叉点)的问题，并使用旅行商算法来确定应该点击停靠点的顺序。