从理想到真实。后勤领域的Dijkstra

Question

我有一个运输公司的程序，其中最优路线由Dijkstra计算。城市是顶点，路线是边缘。去寻找边缘的重量。我把地图上的城市和线连接起来，然后测量它。然后我接受它作为边缘的重量。但在现实生活中，路线并不是笔直的。那我该怎么解决呢？在这里输入图像描述

在我的项目中，我必须通过创建软件来解决物流问题。有人能告诉我该解决什么问题吗？

Answer 1

正如你已经发现的，问题并不像看上去那么简单。首先，只连接主要城市是个坏主意，因为它们可能没有直接连接到高速公路(如果不是美国的话)。

，这是你目前的想法：

​

我想建议的是让每一个小城市都有意义，并将其作为顶点添加到Dijkstra中。

​

​

现在，我们可以看到，在现实世界中，哪一种方式确实存在。只要看一下我们的图表，我们就可以推测，使用底部路径应该更有效。但如果我们发现了这个

​

​

我们现在可以很容易地得出结论，上面的路径实际上要好得多，因为你可以达到底层路径速度的两倍。这是非常精确的分类吗？不，不是的。我们可能会想一想每条路上的流量是什么，动态地改变边缘的权重。但是，对于您的基本实现来说，这可能太多了。

我最终要做的是想一想，我几乎可以一个人收集什么数据，或者几乎没有什么帮助。所以我绝对可以：

• 以某种方式从A点报废一些关于到达B点的实际方法的数据；好的参考资料不是Google，就是必应地图API；
• 聚集沿途的小城市，寻找从A点到B点的真实世界道路；
• 试着找出速度限制在哪里(如果有任何数据库)

实际上，您可能希望完全进入Google Maps或Bing Maps，让它们为您提供可能的最佳道路。他们都有你需要的任何道路的实际数据。你不可能像他们那样收集那么多的数据。如果你觉得这是你能做到的，你就把所有的东西都放在盘子里。

如果不是，我将采用混合的方式--从任何maps中获取一些重要数据，然后将其用于我的Dijkstra算法，然后使用这些数据编写一个简单的算法，用于根据可能的修饰符(速度限制、流量(如果API提供)等)来测量每个边缘的实际权重。