造了一个查找地铁换乘的轮子

[jasonlee]

最近需要频繁出差，于是用 Python 和 JavaScript 造了一个寻找最短路径的工具，托管在 https://metro.lihanming.me/。界面看起来像这样：

它具有以下的功能：

1. 站点提示（输入站名、线路名，可以提示一些车站）
2. 根据当前位置寻找最近的车站，并提示怎么走过去（感谢高德地图）
3. 寻找路径（支持按最短时间、换乘较少等模式查询）
4. 提示行车时间（目前京沪穗三个地方支持实际时间，其他城市支持估算时间）

目前支持中国内地所有有地铁的城市、香港（不含轻铁和电车）、台北和东京（两大地铁和 JR 部分线路）。伦敦正在写。线路保存在 JSON 文件中，可以随时扩展。

比较有趣的细节：

1. 支持虚拟换乘。虚拟换乘站会提示，并且会有不需要虚拟换乘的方案提供。（南京西路、上海火车站）
2. 支持不同运营商或票务系统。如果行程需要转乘会提示。（如龙阳路、三元桥、青衣等）

目前几个需要努力的地方：

1. 优化变量名。尽可能做到没有文档也能看懂；
2. 连续多个换乘站的处理（四惠-四惠东、中环-金钟等）；
3. 提升算法性能。目前使用的算法在初始化时需要的时间比较长；
4. 多语言支持。目前都是使用本地文字；
5. 用户界面优化。城市太多了需要想个办法呈现；
6. 几个城市合在一起做一个大的系统，并且包括一些城际线路（珠三角、长三角）
7. 其它（包括你们的意见和建议）；

最后欢迎大家试试，希望它能在你们旅行出差的时候帮到你们，也欢迎你们提出意见和建议。

网址： https://metro.lihanming.me/

源码： https://github.com/DaZui/MetroSearch/

Jason

[niboy]

提个问题吧，比如在上海的金海路到世纪大道，其实有 2 种路线，实际搜出来的只有一种

[SourceMan]

最优路径的算法思路大概怎么样的？

[moult]

杭州的，江陵路到客运中心，虽然 1 号线直达，但是换成一下 4 号线，就算加上换成时间，也比直达的快。

[jasonlee]

@niboy 有哪两种？提点一下

[jasonlee]

@SourceMan Floyd 算法。冷启动的时候生成距离矩阵，之后直接查矩阵。

[jasonlee]

@moult 这和时间计算方法有关。我设定的换乘的时间是 5 分钟。实际时间可能会短一些。

[niboy]

@jasonlee
1. 12 号线金海路--》到大连路换 4 号线 --》世纪大道，起点站，胜在一路有座
2. 12 号线金海路--》到巨峰路换 6 号线--》世纪大道，比路线 1 少一站，但站内换乘走路时间长，而且不一定有座

可以和百度地图、腾讯地图等的路线对比一下

[jasonlee]

@niboy 我看了一下。估计是因为大连路那里需要过黄浦江，列车运行时间长一些。 Floyd 算法的主要缺点就是你找不到第二长的线路。我看看广度优先搜索能不能找到。谢了啊。

[jasonlee]

@moult 我新增了一个“换乘多”的模式，将换乘时间缩短为 2 分钟。主要是我不知道各个地方的列车间隔。如果列车衔接妥当，那么换乘所花的时间就短。

[niboy]

我下载了 Android 客户端，看起来就是网站，请问 lz 是用什么封装成 APK 的？难道就是一个 webview 加载了 bootstrap 的网站？

[jasonlee]

@niboy 正解。我写了一个 webView 。专门为 Android 写客户端的原因是因为一部分 Android 浏览器获取的地理位置不正确，所以无奈之下封装了。如果你是用 Chrome 等可以添加到桌面的浏览器，那我觉得不用下客户端也没事。

[wdlth]

我认为如果只有一个结果的话就不要写换乘多了……

[jasonlee]

@wdlth 好主意。我在想这一块应该怎么展示。有什么建议吗？

[franklinyu]

@jasonlee 弗洛伊德算法是不是可以一次性找到所有「站點對」的最短路徑？而不用在收到請求的時候實時計算？

[jasonlee]

@franklinyu 是的，這就是原因。但 Floyd 這個演算法不能找到第二長的路徑，十分頭疼。

[kenshin]

挺棒的想法，前阵子去上海正好有这样的需求，当时的想法是自己有时间撸一个，没想到已经有成品了。

提个建议：
之前在上海的时候，想去迪士尼，出发地点附近有两个地铁线：老西门站与小南门站；通过地图 APP ，告诉我老西门站距离较慢 /较远，建议小南门站；结果发现，小南门的确时间或许比较少，但是需要换乘 n 站，结果这个 APP 就没有计算出每个换乘站需要走多久，需要等下趟车多久。

所以，能否再加入一些人工干预，比如：
- 各个换乘站步行时间
- 每趟车的间隔时间
- 从出发点到地铁站的时间

[lgh]

zuoche.com

[jasonlee]

@kenshin 不显示换乘时间的考虑就是这个。这个程序的好处就是简单。如果要显示这么细的话，就变成地图了(笑)。列车间隔也很难搞，因为不同时候的间隔不同。不过多个首站确实值得考虑，我设计一下流程来。

[jasonlee]

@lgh 所以说是造了轮子嘛。

[jasonlee]

@kenshin 我用我的查了一下，小南门出发确实多换一次。

[zhen14]

没有 iOS ？

[jasonlee]

@zhen14 iOS 我觉得直接浏览器放到桌面比较方便。

[sobigfish]

json 里没有发现里程 2 站间距离很重要吧（大概）-。-

[jasonlee]

@sobigfish 不是用里程，而是用时间。因为不知道换乘需要多少里程。而且快车哪怕多走一点，时间也比慢车短。不过里程对算票价很有用。

[jasonlee]

话说有什么新的城市需要添加么？比如北美和欧洲

[zjqzxc]

查北京地铁的时候经常只出现一种路径，例如西直门到东直门只出现了二号线方案；五路居到五道口只出现了换成 10 号线方案；
北京地铁换成很多幺蛾子， 4/9 换成有同站台换成， 2->1 下了楼梯就是，但 1->2 要绕一大圈。。

不过话说这种公共交通工具查询这些地图软件已经很成熟了。。

[jasonlee]

@zjqzxc 西直门到东直门…莫非 13 号？其实这就是选路问题。
同站台和人流管制确实很麻烦，但我也没有精力去一个个收集这种细节。
这东西就是自己给自己开发的轮子，就图一个简单快捷而已。很多应用都做得更好。

[franklinyu]

@jasonlee {{15L}}:我感覺你其實可以給每個「站點對」保存前 K 的路徑（ K 是你自己決定的常數），然後專門分出一個後臺進程計算。畢竟每個「站點對」只需要計算一次，工作量對於服務器來說應該不算大。當用戶請求到還沒計算好的站點對的時候，將這個「站點對」從計算序列中提取出來，放到序列的前面，同時給用戶返回一個「計算中……」的回覆。

[franklinyu]

@jasonlee {{15L}}:或者可以看一下這個 StackOverflow 問題： http://stackoverflow.com/q/4971850

[jasonlee]

@franklinyu 一般来讲找多条路径用的是 BFS 。但 BFS 的复杂度很高。我正在考虑的思路是一路存储，就是在 BFS 的时候顺手存储所有沿路的站点。 Dijkstra 是单点出发所有点，也是一种可行的思路。

[franklinyu]

@jasonlee {{30L}}:如何用 BFS 來找多條路徑？

[jasonlee]

@franklinyu BFS 的演算法是這樣的，從起點出發往終點遍曆，只要能到終點的都算一條路徑，如果是死路則返回。最困難的地方在於，有的時候由於圖過分複雜，很難及時返回。（我個人測試，廣州、深圳和香港可以用 BFS ，上海、北京就無法及時返回結果）。這裡有一篇文章，可供聊作參考。 http://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/

[franklinyu]

@jasonlee {{32L}}:所以你的圖裡沒有權重的？如果有權重的話廣度優先搜索並不能保證最短路徑先返回誒。

[jasonlee]

@franklinyu 有權重。可以退化為無權重算，然後逐一計算路徑所需的時間，在瀏覽器用 JavaScript 解決。我看了一下 BFS 失敗的原因是內存溢出，畢竟這是 BFS 的老問題。

[jasonlee]

@franklinyu 這個排序的問題實際上是個大問題。比起客戶端運算排序，用一個直接尋找最短路徑的算法會更快一些，也更節約服務器內存。

[franklinyu]

@jasonlee 內存溢出？一個城市也就幾十個站，而且地鐵圖是稀疏圖，怎麼會這麼耗內存？是 JavaScript 垃圾回收太遲？

[franklinyu]

我在 CS.StackExchange 裡面幫你問了一下，好像最好的方法也只是逐對計算了： http://cs.stackexchange.com/q/62383

[jasonlee]

@franklinyu 北京上海東京個個都是數百個站。如果帶權重就不是稀疏圖了(因為不為 0)。這是個極為頭疼的問題。我一開始廣州深圳都是可以 BFS ，在做上海的時候發現的這個問題才轉向 Floyd 。 BFS 應對大規模圖的方法主要是剪枝，但怎麼剪是個問題。

[jasonlee]

@franklinyu 事實上幾個更坑的問題是有一部分單向運行的(北京機場線)，此時馬上變成有向圖。為了壓縮矩陣我毅然廢了這個功能。

[akaayy]

百度地图。

[jasonlee]

@akaayy 这是个轮子。另外百度地图目前无法提示出站换乘和转乘。这方面做得比较好的其实是日本人。

[wshcdr]

以前写过类似的，这东西其实不容易写的...

[jojobobo]

非常帮,,哈哈 为什么你这么棒

[jasonlee]

@wshcdr 是的。很多容易掉进去的陷阱。也祝您编程之路愉快

[jasonlee]

@jojobobo 多谢夸奖。编程之路愉快。

[kyzylsy]

web 版点击寻找线路根本没有反应。。。差评

[jasonlee]

@kyzylsy 是不是网络问题？一般多点几次会有结果。