【项目】TSP旅行路线规划

GitHub 项目地址:tsp-route

对于在欧洲的小伙伴们,复活节假在这一周就正式开始啦。大家都是怎么计划旅行的呢?

我的习惯是在出发前最后一晚,花上半小时,搜索目的地景点 (Point of interest, POI), 然后在Google Maps上为它们点上小星星,以免和它们擦肩而过。我的地图经过一番操作,就成了下面这副模样。

攒满了小星星

此时此刻,望着这些密集的星星,我不禁自问:如何才能走最少的路,遍历所有景点呢?

搜索了谷歌和百度,都没找到我要路径规划功能。最接近需求的是谷歌地图的"Add destination"功能。然而这个功能只是依次连接你点选的地点。并不能由一组地点,确定连接它们的一条全局最短路径。

没有现成应用怎么办,我打算自己动手写一个。

下图是Google Add destination功能。

Add destination 功能

适用模型:TSP 模型

用一句话概括需求就是:我们需要一条从某地方出发,遍历所有地点,最终回到起点的最短路径。

这个需求其实就是运筹学的一个经典问题,旅行商问题(TSP)。旅行商问题的确切描述是这样的:一个商人在各个城市之间旅行,要求遍历所有城市并返回到出发点,要如何规划路线,才能使总路径最短。(打开维基百科了解更多)

解决思路

  • 用googlemaps包获取纬度和经度信息
  • 用OR-Tools包求解TSP问题
  • 最后用gmaps可视化结果

在敲代码的过程中,最难的地方莫过于看文档查API, 搞清楚输入输出和调用结构。不过敲完这一顿之后我还是不禁感慨,GoogleI太为开发者着想了。一旦学会调用API,实现一个简单应用的代码量还是很小的 orz

食用指南

项目地址 –> 传送门

在运行代码之前,你需要以下配置:

  1. 一个Jupyter Notebook.
  2. 你需要安装这些包:googleplaces, googlemaps, gmaps, ortools.
  3. 你需要一个Google Maps API key, 从这里获取API.

完成配置等于成功的一半。在Jupyter notebook打开TSPSolver.ipynb,将第二个代码块的所有变量,改成自己的,比如自己的目的地自己的区域和自己的API密码……最后从头到尾运行所有代码块,你就可以得到自己的定制路线辣~

my route

配置代码如下。

# input the places of interest (POI)
places = 'YHA London Central Hostel', 'Coca-Cola London Eye', 'St. Paul\'s Cathedral', 'Leadenhall Market', 'The National Gallery' \
          'Big Ben', 'Buckingham Palace', 'Waterloo Station'

# the region
Location='London'

# choose a mode
Mode = "walking"  # "driving", "walking", "bicycling", "transit"

# get Google API key from following website: 
# https://developers.google.com/maps/documentation/distance-matrix/start#get-a-key
password = "YOUR_GOOGLE_API_KEY_HERE"

欢迎Star, Pull, Pr.