设计一个地铁路线规划小工具

概述

最近在找房子,因为想找一个去几个地方都相对方便的位置,自己去地图上看还挺麻烦的,所以想做个小工具,本文就简单介绍一下实现过程。目前的功能还比较简单,主体方法就是根据一个输入的始发站,列出其他所有站点到这个地方的站数最少路线。

数据获取

从网上找了高德地图的接口数据: http://map.amap.com/service/subway?_1469083453978&srhdata=1100_drw_beijing.json . 对拿到的json串进行解析,其中包含每条地铁线路的信息,并依次列出线路上的每个站点。

通过解析数据,要得到的主要就是各个站点的信息,站点定义的数据结构如下:

1
2
3
4
5
6
private String id;
private String name;
private Set<String> lines = new HashSet<String>(); //所在线路
private String position;
private String pinyin;
private Set<String> nextStations = new HashSet<String>(); //相邻站点

所有站点汇总后可以看做一张图,nextStations字段就是用来表示边的信息。

路线规划

路线规划算法可以参考Dijkstra算法,由于现有的表现形式下,只是一个无向无权重的图,实现起来还要简单一些。

实现过程描述如下:

  1. 新建两个map, knownPath和waitingPath,分别用来表示已经确定了最短路径的站点列表,和待处理的站点列表。初始化时,knownPath中只包含指定的起点,waitingPath中包含其他所有站点,并将距离设置成无穷大(用MAX = 20000表示)
  2. 指定起点为当前节点
  3. 依次处理当前的相邻节点,更新每个节点的最短距离
  4. 从waitingPath中找到距离最短的节点,作为当前节点,重复第3步,并从waitingPath转移到knownPath

整个过程结束之后,会得到每个节点到起点的最短距离以及路线详情,然后可以根据这些数据计算路线详情的换乘情况。

对于换乘,主体判断逻辑是,如果一个站点的上一站和下一站所在路线不重合,就可以确定在这一站进行了换乘,比如灯市口-东四-朝阳门,灯市口在5号线上,朝阳门在2,6号线上,可以断定在东四肯定作了换乘。不过还有一些特殊情况要处理,比如说西直门到平安里,中间那站如果是车公庄(虽然现实中没人会这么干),实际就是作了换乘的,但是按刚才的逻辑就会判断成未换乘。

最终得到的路线信息中包含以下信息:

1
2
3
4
private String stationId;
private int length;
private int transferNum; //换乘数
private List<String> detail = new ArrayList<>(); //详细路径

用途

主体功能在上面已经完成,后边就可以根据需要再去自定义处理了。比如,加入我现在需要找到”距奥林匹克公园站15站以内且距天安门东站7站以内的位置”,就可以分别输入奥林匹克公园和天安门东,然后在结果中作相应的过滤,再取交集。

后续计划

目前做的还比较简单,只是简单考虑站数,但是实际上,不同站点的距离、耗时相差会比较大,再一个不同地方的换乘开销差别也很大。所以后续会试试能不能找到换乘站的详情数据,还有两站之间耗时的数据,并应用到算法中。

再一个是要找一个合适的方法做个界面出来,因为一直做的是纯后台,还没考虑清楚用什么合适。

其他的,还在考虑爬一下房价信息。

代码

https://github.com/lcy362/FoxSubway

欢迎提意见。

原文地址: https://lcy362.github.io/posts/13793

 wechat
订阅公众号