非完全图作为VRP的地图,使用OR工具。

huangapple go评论127阅读模式
英文:

Non complete graph as map for VRP with or tools

问题

我必须解决一个车辆路径问题,我想在Python中使用OR工具来处理。

问题是地图并不完整,也就是说,并不是每个节点都通过边连接到所有其他节点。

根据文档,我看到我需要创建一个距离矩阵或距离回调函数,但我应该如何编码边不存在的信息呢?
或者我是否需要计算地图上到相应节点的最短路径,然后用该计算路径的距离填充距离矩阵。

所有这些似乎就好像有一些我没有注意到的明显解决方案。

英文:

I have to solve a vehicle routing problem and I want to use or tools in python for that.

The problem is the map in which the routing should be done is not complete in a sense that not each node is connected to all other nodes by an edge.

From what I see in the documentation I have to create a distance matrix or distance callback but how do I encode the information of an edge not being present?
Or do I have to calculate the shortest path in the map to the respective node and so fill the distance matrix with the distance of that calculated path.

All this seems as if there was some obvious solution to this I’m not seeing.

答案1

得分: 1

你正在解决的问题是VRP,而不是TSP。
在这个意义上,距离矩阵表示从一个节点到另一个节点的最短路径,而不是两个节点之间是否存在边缘。

VRP问题的解决方案将访问距离矩阵的所有节点一次。但它不禁止多次访问底层道路网络的多个边缘。

现在,如果两个节点确实没有连接(在完全图上),那么你可以设置足够大的距离来表示不可能。

英文:

The problem you are solving is a VRP, not a TSP.
In that sense, the distance matrix indicates the shortest path from one node to another, not if there is an edge between the two nodes.

A solution of the VRP problem will visit all nodes of the distance matrix once. But it does not forbid visiting multiple edges of the underlying road network multiple times.

Now, if two nodes are really not connected (on the complete graph), then you can put a distance that is large enough to indicate it is not possible.

答案2

得分: 0

由于TSP假设是一个完全图,您可以使用Floyd–Warshall算法来计算成对的最短距离(如果您想找到访问所有节点的最短路径),或者您可以为所有不存在的边添加足够大的权重。然后,在这个矩阵上计算最短路径。

英文:

Since the TSP assumes a complete graph you could use Floyd–Warshall to compute the pairwise shortest distances (if you want to find the shortest path that visits all nodes) or you add a large enough weight for all edges, that are non-existent. On this matrix you then compute the shortest path.

huangapple
  • 本文由 发表于 2023年5月30日 07:34:12
  • 转载请务必保留本文链接:https://go.coder-hub.com/76360827.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定