形式理想到真实。物流中的 Dijkstra
Form ideal to Real . Dijkstra in logistic
我有一个运输公司的程序,其中由 Dijkstra 计算出最佳路线。城市作为顶点,路线作为边。求边的权重。我用线连接地图中的城市并测量它。然后我接受它作为 edge 的权重。但在现实生活中,路线并不直。那么我该如何解决呢? enter image description here
在我的项目中,我必须通过创建软件来解决逻辑问题。谁能告诉我要解决什么问题?
正如您已经发现的那样,问题并不像看起来那么简单。
首先,只连接主要城市是个坏主意,因为它们可能没有直接与高速公路相连(如果不是 U.S。或其他东西)。
这是你目前的想法:
我的建议是尝试以每一种有意义的方式获取每个小城市,并将其作为顶点添加到您的 Dijkstra
:
现在,我们可以看到现实世界中实际存在的方式。从我们的图表来看,我们可能会假设使用底部路径应该更有效。但是,如果我们发现这个怎么办:
现在我们很容易得出结论,上面的路径实际上要好得多,因为你可以达到底部路径的两倍的速度。
是不是很精确的分类?不,这不对。
我们可能想考虑每条路上的流量并动态更改边的权重。但这对于您的基本实施来说可能太多了。
我最后要做的是想一想我几乎可以独自一人或在几乎没有帮助的情况下收集到哪些数据。
所以我绝对可以:
- 以某种方式废弃了一些关于从 A 点到达 B 点的实际方式的数据;好的参考资料是 Google Maps API or Bing Maps API;
- 沿途收集小城市,寻找从 A 点到 B 点的现实世界道路;
- 尝试找出速度限制在哪里(如果有任何数据库的话)
实际上,您可能想要完全进入 Google Maps
或 Bing Maps
,让他们为您提供最佳道路。
他们都有您需要的任何道路的真实数据。
您无法收集到与他们一样多的数据。
如果你觉得这是你能做到的方式,你可以把所有东西都放在盘子里。
如果没有,我会采用混合方式 - 从任何地图 API 获取一些重要数据,然后将其用于我的 Dijkstra
算法,然后使用此数据编写一个简单的测量算法基于可能的修饰符的每条边的实际权重(速度限制,如果 API 提供的流量等等)。
我有一个运输公司的程序,其中由 Dijkstra 计算出最佳路线。城市作为顶点,路线作为边。求边的权重。我用线连接地图中的城市并测量它。然后我接受它作为 edge 的权重。但在现实生活中,路线并不直。那么我该如何解决呢? enter image description here
在我的项目中,我必须通过创建软件来解决逻辑问题。谁能告诉我要解决什么问题?
正如您已经发现的那样,问题并不像看起来那么简单。 首先,只连接主要城市是个坏主意,因为它们可能没有直接与高速公路相连(如果不是 U.S。或其他东西)。
这是你目前的想法:
我的建议是尝试以每一种有意义的方式获取每个小城市,并将其作为顶点添加到您的 Dijkstra
:
现在,我们可以看到现实世界中实际存在的方式。从我们的图表来看,我们可能会假设使用底部路径应该更有效。但是,如果我们发现这个怎么办:
现在我们很容易得出结论,上面的路径实际上要好得多,因为你可以达到底部路径的两倍的速度。 是不是很精确的分类?不,这不对。 我们可能想考虑每条路上的流量并动态更改边的权重。但这对于您的基本实施来说可能太多了。
我最后要做的是想一想我几乎可以独自一人或在几乎没有帮助的情况下收集到哪些数据。 所以我绝对可以:
- 以某种方式废弃了一些关于从 A 点到达 B 点的实际方式的数据;好的参考资料是 Google Maps API or Bing Maps API;
- 沿途收集小城市,寻找从 A 点到 B 点的现实世界道路;
- 尝试找出速度限制在哪里(如果有任何数据库的话)
实际上,您可能想要完全进入 Google Maps
或 Bing Maps
,让他们为您提供最佳道路。
他们都有您需要的任何道路的真实数据。
您无法收集到与他们一样多的数据。
如果你觉得这是你能做到的方式,你可以把所有东西都放在盘子里。
如果没有,我会采用混合方式 - 从任何地图 API 获取一些重要数据,然后将其用于我的 Dijkstra
算法,然后使用此数据编写一个简单的测量算法基于可能的修饰符的每条边的实际权重(速度限制,如果 API 提供的流量等等)。