创建公交路线
什么是好的算法或可用于创建公交路线的算法类别？
我正在思考用于解决旅行推销员或哈密顿路径问题的算法，但事实上，两者都没有真正解决如何在两个站点之间移动的问题。
我希望该算法至少具有以下特征：
- 产生相对优化的路径（我知道问题可能是 NP 完全问题，因此良好的启发式就可以了）
- 可以处理具有不同权重的路径部分（例如，时间）穿过路径的那部分）
- 可以强制使用给定的起点和终点（我不认为这会是一个问题）
可以执行此操作的代码或类似的代码将不胜感激（尤其是在 C# 中） ），但是一个好的算法本身就可以了。
注意：虽然有很多算法可以找到两点之间的最短路径，但我不知道我希望停止的顺序。因此，除非我应该使用两种算法的组合（我怀疑是这种情况），否则这些算法不会做我想要的事情（如果您认为它们会做，请解释）。
编辑：假设我知道所有需要停靠的站点。
What is a good algorithm, or class of algorithms that can be used to create a bus route?
I was thinking something along the lines of algorithms that are used to solve the Traveling Salesman, or Hamiltonian path problems, but in truth, neither really addresses the issue of how to move between two stops.
I would like the algorithm to have at least the following characteristics:
- produces a relatively optimized path (I understand that the problem is probably NP complete, so a good heuristic is fine)
- Can deal with parts of the path having different weights (eg time to travel over that part of the path)
- Can be forced to use a given starting and ending point (I don't think this one will be such a problem)
Code that can do this, or something like this would be appreciated (especially in C#), but a good algorithm by itself would be fine.
Note: While there are many algorithms that can find the shortest path between two points, I do not know the order in which I wish to stop. As such, unless I should be using a combination of two algorithms (which I doubt is the case), those algorithms do not do what I want (if you think that they do, please explain).
Edit: Assume I know all of the stops that need to be made.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
似乎实现此目的的方法涉及使用 Floyd-Warshall 算法，然后使用用于解决旅行商问题的算法。
这解决了所有“可选”顶点（交叉点）的问题，并使用旅行商算法来确定应到达停靠点的顺序。
It seems that a way to do this involves using the Floyd-Warshall algorithm, and then using an algorithm that is used to solve the traveling salesman problem.
This solves the problem of all the "optional" vertices (the intersections) and the uses the traveling salesman algorithm to determine the order in which the stops should be hit.
您可以在此处使用旅行推销员算法并进行一些小的修改/假设，以解决点#2（具有不同权重的路径的一部分）。
假设从点“A”到点“B”的路径有 2 个权重（例如，某个时间点的流量）
即使它是一条路径，我们也可以通过假设“虚拟顶点”点“C”来简化问题位于“A”和“B”之间，每个边都有固定的权重。
A-----权重=10------ C ------权重=15-----B
在这个新图上，运行旅行商算法。
You can probably use the travelling salesman algorithm with a small modification/assumption here, to address point #2 (part of path having different weights).
Lets say Path from point "A" to Point "B" has 2 weights (say, traffic at some point of time)
Even though its a single path, we can simplify the problem by assuming a "virtual vertex", point "C" that is between "A" and "B", which will have fixed weights in each of the edges.
A-------Weight=10------ C ------Weight=15------B
On this new graph, run the Travelling salesman algorithm.
我使用了 Djikstra 的算法： http://en.wikipedia.org/wiki/Dijkstras_algorithm
沿着边缘行驶的成本不仅与距离有关，还与“下一个”公共汽车从给定节点出发之前的时间有关。注意：当公交车停在某个节点时，您可能已经在公交车上了。
I've used Djikstra's algorithm: http://en.wikipedia.org/wiki/Dijkstras_algorithm
The cost of travelling along an edge is not just the distance, but also related to the time until the "next" bus departs from the given node. Note: you might already be on the bus when it stops at a node.
巴士路线是由人而不是计算机创建的。只有人们知道谁需要去哪里旅行以及多久旅行一次。您至少需要这样的数据来考虑找到最适合人们需求的路线集。就此而言，我认为你的问题定义不明确。
Bus routes are created by people, not computers. Only people know who needs to travel where and how often. You need at least such data to think about finding the set of routes that will be optimal to people's needs. In respect to that I think your question is underdefined.