计算在美国进行公路旅行的最优路线

 Python库依赖:

如果你没有Python,请安装Python。本代码基于 googlemaps 和 pandas 库,你可以用 pip 安装:

如果你使用 Mac,Linux/Unix 系统,你也许需要在命令前加sudo。收集公路旅行停留点

首先你要决定公路旅行的经过地点或景点。

你列出的地点必须符合Google地图中的地址,确保可以用Google地图找到。

注意:由于我们用 google 地图的API 获取两地之间的最短公路距离,但是免费的API查询上限为70个地点,要想查询更多就要付费了。

列出如下格式的地点:

Google地图API

在你的google console中打开 Google Maps Distance Matrix API,google 在这里解释了怎么做。

把API密钥粘贴到代码中。

现在你就可以查询所有地点的最短路径了。如果你在查询时得到了错误码,最有可能的原因是因为你的地点不在Google地图中。还有可能是因为两点间不能开车直达,像夏威夷和阿拉斯加。

收集所有地点的最短旅行距离:

把路径距离保存起来,以后就不用在麻烦google了:

下面用遗传算法求最优路径:遗传算法从一个随机解开始,然后试图找到和当前解不同的解,保留最优解,直到不能找到更好的解为止。

下面代码用到上面的距离文件my-waypoints-dist-dur.tsv。

用遗传算法计算最优路径:

结果:

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注