首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
爱意满满的作品展示区。
V2EX  ›  分享创造

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

  •  
  •   jasonlee · 2016-08-03 18:55:56 +08:00 · 3968 次点击
    这是一个创建于 1196 天前的主题,其中的信息可能已经有所发展或是发生改变。

    最近需要频繁出差,于是用 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

    47 回复  |  直到 2016-08-17 20:19:30 +08:00
        1
    niboy   2016-08-03 19:37:29 +08:00
    提个问题吧,比如在上海的金海路到世纪大道,其实有 2 种路线,实际搜出来的只有一种
        2
    SourceMan   2016-08-03 19:39:00 +08:00 via iPhone
    最优路径的算法思路大概怎么样的?
        3
    moult   2016-08-03 19:51:14 +08:00
    杭州的,江陵路到客运中心,虽然 1 号线直达,但是换成一下 4 号线,就算加上换成时间,也比直达的快。
        4
    jasonlee   2016-08-03 19:56:19 +08:00 via Android
    @niboy 有哪两种?提点一下
        5
    jasonlee   2016-08-03 20:16:58 +08:00
    @SourceMan Floyd 算法。冷启动的时候生成距离矩阵,之后直接查矩阵。
        6
    jasonlee   2016-08-03 20:17:36 +08:00
    @moult 这和时间计算方法有关。我设定的换乘的时间是 5 分钟。实际时间可能会短一些。
        7
    niboy   2016-08-03 21:12:49 +08:00
    @jasonlee
    1. 12 号线金海路--》到大连路换 4 号线 --》世纪大道,起点站,胜在一路有座
    2. 12 号线金海路--》到巨峰路换 6 号线--》世纪大道,比路线 1 少一站,但站内换乘走路时间长,而且不一定有座

    可以和百度地图、腾讯地图等的路线对比一下
        8
    jasonlee   2016-08-03 21:33:41 +08:00
    @niboy 我看了一下。估计是因为大连路那里需要过黄浦江,列车运行时间长一些。 Floyd 算法的主要缺点就是你找不到第二长的线路。我看看广度优先搜索能不能找到。谢了啊。
        9
    jasonlee   2016-08-03 21:37:01 +08:00
    @moult 我新增了一个“换乘多”的模式,将换乘时间缩短为 2 分钟。主要是我不知道各个地方的列车间隔。如果列车衔接妥当,那么换乘所花的时间就短。
        10
    niboy   2016-08-03 22:49:10 +08:00
    我下载了 Android 客户端,看起来就是网站,请问 lz 是用什么封装成 APK 的?难道就是一个 webview 加载了 bootstrap 的网站?
        11
    jasonlee   2016-08-03 23:23:49 +08:00
    @niboy 正解。我写了一个 webView 。专门为 Android 写客户端的原因是因为一部分 Android 浏览器获取的地理位置不正确,所以无奈之下封装了。如果你是用 Chrome 等可以添加到桌面的浏览器,那我觉得不用下客户端也没事。
        12
    wdlth   2016-08-03 23:31:26 +08:00
    我认为如果只有一个结果的话就不要写换乘多了……
        13
    jasonlee   2016-08-03 23:36:50 +08:00 via Android
    @wdlth 好主意。我在想这一块应该怎么展示。有什么建议吗?
        14
    franklinyu   2016-08-04 01:10:39 +08:00
    @jasonlee 弗洛伊德算法是不是可以一次性找到所有「站點對」的最短路徑?而不用在收到請求的時候實時計算?
        15
    jasonlee   2016-08-04 08:01:49 +08:00 via Android
    @franklinyu 是的,這就是原因。但 Floyd 這個演算法不能找到第二長的路徑,十分頭疼。
        16
    kenshin   2016-08-04 10:54:59 +08:00
    挺棒的想法,前阵子去上海正好有这样的需求,当时的想法是自己有时间撸一个,没想到已经有成品了。

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

    所以,能否再加入一些人工干预,比如:
    - 各个换乘站步行时间
    - 每趟车的间隔时间
    - 从出发点到地铁站的时间
        17
    lgh   2016-08-04 12:23:32 +08:00
        18
    jasonlee   2016-08-04 12:35:05 +08:00 via Android
    @kenshin 不显示换乘时间的考虑就是这个。这个程序的好处就是简单。如果要显示这么细的话,就变成地图了(笑)。列车间隔也很难搞,因为不同时候的间隔不同。不过多个首站确实值得考虑,我设计一下流程来。
        19
    jasonlee   2016-08-04 12:45:06 +08:00 via Android
    @lgh 所以说是造了轮子嘛。
        20
    jasonlee   2016-08-04 12:46:57 +08:00 via Android
    @kenshin 我用我的查了一下,小南门出发确实多换一次。
        21
    zhen14   2016-08-04 17:25:55 +08:00
    没有 iOS ?
        22
    jasonlee   2016-08-04 17:30:33 +08:00 via Android
    @zhen14 iOS 我觉得直接浏览器放到桌面比较方便。
        23
    sobigfish   2016-08-04 23:34:28 +08:00
    json 里没有发现里程 2 站间距离很重要吧(大概)-。-
        24
    jasonlee   2016-08-05 07:56:45 +08:00 via Android
    @sobigfish 不是用里程,而是用时间。因为不知道换乘需要多少里程。而且快车哪怕多走一点,时间也比慢车短。不过里程对算票价很有用。
        25
    jasonlee   2016-08-05 10:04:35 +08:00 via Android
    话说有什么新的城市需要添加么?比如北美和欧洲
        26
    zjqzxc   2016-08-05 11:42:18 +08:00
    查北京地铁的时候经常只出现一种路径,例如西直门到东直门只出现了二号线方案;五路居到五道口只出现了换成 10 号线方案;
    北京地铁换成很多幺蛾子, 4/9 换成有同站台换成, 2->1 下了楼梯就是,但 1->2 要绕一大圈。。

    不过话说这种公共交通工具查询这些地图软件已经很成熟了。。
        27
    jasonlee   2016-08-05 20:13:02 +08:00 via Android
    @zjqzxc 西直门到东直门…莫非 13 号?其实这就是选路问题。
    同站台和人流管制确实很麻烦,但我也没有精力去一个个收集这种细节。
    这东西就是自己给自己开发的轮子,就图一个简单快捷而已。很多应用都做得更好。
        28
    franklinyu   2016-08-08 02:45:31 +08:00
    @jasonlee {{15L}}:我感覺你其實可以給每個「站點對」保存前 K 的路徑( K 是你自己決定的常數),然後專門分出一個後臺進程計算。畢竟每個「站點對」只需要計算一次,工作量對於服務器來說應該不算大。當用戶請求到還沒計算好的站點對的時候,將這個「站點對」從計算序列中提取出來,放到序列的前面,同時給用戶返回一個「計算中……」的回覆。
        29
    franklinyu   2016-08-08 02:52:47 +08:00
    @jasonlee {{15L}}:或者可以看一下這個 StackOverflow 問題: http://stackoverflow.com/q/4971850
        30
    jasonlee   2016-08-08 09:04:24 +08:00 via Android
    @franklinyu 一般来讲找多条路径用的是 BFS 。但 BFS 的复杂度很高。我正在考虑的思路是一路存储,就是在 BFS 的时候顺手存储所有沿路的站点。 Dijkstra 是单点出发所有点,也是一种可行的思路。
        31
    franklinyu   2016-08-08 10:25:27 +08:00
    @jasonlee {{30L}}:如何用 BFS 來找多條路徑?
        32
    jasonlee   2016-08-08 12:17:10 +08:00
    @franklinyu BFS 的演算法是這樣的,從起點出發往終點遍曆,只要能到終點的都算一條路徑,如果是死路則返回。最困難的地方在於,有的時候由於圖過分複雜,很難及時返回。(我個人測試,廣州、深圳和香港可以用 BFS ,上海、北京就無法及時返回結果)。這裡有一篇文章,可供聊作參考。 http://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/
        33
    franklinyu   2016-08-08 13:25:45 +08:00
    @jasonlee {{32L}}:所以你的圖裡沒有權重的?如果有權重的話廣度優先搜索並不能保證最短路徑先返回誒。
        34
    jasonlee   2016-08-08 14:38:38 +08:00
    @franklinyu 有權重。可以退化為無權重算,然後逐一計算路徑所需的時間,在瀏覽器用 JavaScript 解決。我看了一下 BFS 失敗的原因是內存溢出,畢竟這是 BFS 的老問題。
        35
    jasonlee   2016-08-08 15:17:33 +08:00 via Android
    @franklinyu 這個排序的問題實際上是個大問題。比起客戶端運算排序,用一個直接尋找最短路徑的算法會更快一些,也更節約服務器內存。
        36
    franklinyu   2016-08-09 00:57:47 +08:00
    @jasonlee 內存溢出?一個城市也就幾十個站,而且地鐵圖是稀疏圖,怎麼會這麼耗內存?是 JavaScript 垃圾回收太遲?
        37
    franklinyu   2016-08-09 01:14:19 +08:00
    我在 CS.StackExchange 裡面幫你問了一下,好像最好的方法也只是逐對計算了: http://cs.stackexchange.com/q/62383
        38
    jasonlee   2016-08-09 07:39:11 +08:00 via Android
    @franklinyu 北京上海東京個個都是數百個站。如果帶權重就不是稀疏圖了(因為不為 0)。這是個極為頭疼的問題。我一開始廣州深圳都是可以 BFS ,在做上海的時候發現的這個問題才轉向 Floyd 。 BFS 應對大規模圖的方法主要是剪枝,但怎麼剪是個問題。
        39
    jasonlee   2016-08-09 07:41:36 +08:00 via Android
    @franklinyu 事實上幾個更坑的問題是有一部分單向運行的(北京機場線),此時馬上變成有向圖。為了壓縮矩陣我毅然廢了這個功能。
        40
    akaayy   2016-08-10 21:58:53 +08:00 via Android
    百度地图。
        41
    jasonlee   2016-08-11 06:09:19 +08:00 via Android
    @akaayy 这是个轮子。另外百度地图目前无法提示出站换乘和转乘。这方面做得比较好的其实是日本人。
        42
    wshcdr   2016-08-11 14:57:24 +08:00
    以前写过类似的,这东西其实不容易写的...
        43
    jojobobo   2016-08-11 21:01:52 +08:00
    非常帮,,哈哈 为什么你这么棒
        44
    jasonlee   2016-08-12 11:21:03 +08:00 via Android
    @wshcdr 是的。很多容易掉进去的陷阱。也祝您编程之路愉快
        45
    jasonlee   2016-08-12 11:21:19 +08:00 via Android
    @jojobobo 多谢夸奖。编程之路愉快。
        46
    kyzylsy   2016-08-17 17:48:35 +08:00
    web 版点击寻找线路根本没有反应。。。差评
        47
    jasonlee   2016-08-17 20:19:30 +08:00
    @kyzylsy 是不是网络问题?一般多点几次会有结果。
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   4102 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 26ms · UTC 08:19 · PVG 16:19 · LAX 00:19 · JFK 03:19
    ♥ Do have faith in what you're doing.