01

花了3亿没解决的问题

前文《出错，如何获取火车中转换乘的最优方案？》说到app存在2个问题：

1.1搜出的中转方案不是最快的

从赣州西站去保定东站，用搜索出的中转方案如下图所示：

这些中转方案是按总耗时排的序，可以看出，搜出的最快方案为11:44出发、23:00到，用时为11小时16分钟，明显不是真正的最快方案。

1.2只支持中转1次

无论是中转，还是定制中转，都只支持中转1次，比如我搜索：赣州西站——石河子站，怎么搜都显示无法到达。

02

我是怎么解决问题的？

我针对以上2个问题向客服邮箱（kyfw

.cn）提出建议，请求TA们升级功能，使app支持多次中转、并确保搜出的方案是真的前K最快方案。

然而一直没有回应，这咋办？

如果每次旅途能省下1个人的1小时，14亿人就是14亿个小时，14亿小时/24小时/天/80年=2千万人，时间就是生命，相当于每次能省下2千万条人命。

节省全国人民坐火车的时间功德无量，于是，我决定不等了，生死看淡，不服就干，从年9月1日开始开发“野猫版”。

我是电气博士，以前开发的都是电网仿真与分析软件，因此，对超大型网络分析是有研究基础的，火车网跟电网差不多，也是最复杂的人造网络之一。

下图是我绘制的全国火车网络图，一键布局、自动绘制，图太大，只能截图展示部分。

注：本文所有图片皆高清，点击可放大查看

我的开发步骤如下：

1）开发网络爬虫爬取全国列车时刻表，形成火车网字典；/9/1完成

2）网络爬虫爬取全国各车站所属省份，形成车站-分区字典；/9/5完成

3）将火车网字典转换为电网数据，对车站进行分区管理；/9/10完成

4）建立全国火车网图，支持双向、多回路、多标签，方便未来的功能扩展；/9/11完成

5）将车站按时刻不同划分为多个子站，添加子站之间的空线路，以乘车时长作为线路权重，搜索两两之间的最短路径；/9/13完成

6）对搜出的路径进行精简、整合、形成路径描述字符串及时长，对路径字典按时长排序，输出前K条最短路径。/9/15完成

7）允许时间筛选、站名扩展，支持指定多个中转站。/9/18完成

8）提高程序运行速度和准确率，让用户使用更傻瓜、更友好。正在完成中，软件有任何问题，欢迎大家批评指正，提出改善建议。

9月的课余时间多数都投入在开发这软件上了，代码量约2千行，当前发布的算是1.0版本，绿色运行文件夹如下图所示：

注：本文所有图片皆高清，点击可放大查看

03

野猫版的功能和用法

首先申明，本次开发和测试用的是个人电脑，内存和CPU性能有限，不敢开多线程，因此图论搜索用时较长，如果换成之类的大公司的服务器，开多线程、运行速度不是问题。

野猫版共有以下5大功能：

3.1更强大的单次中转方案搜索

启动程序之后界面如下图所示，在关键词框中输入火车站名，比如“赣”，点击筛选，会筛选出赣州站和赣州西站等所有名字带“赣”的。

双击列表中筛选出的“赣州西”，即完成出发站的设置，同理设置目的站。

你如果记得火车站的全名，可以不筛选、直接在出发站文本框中输入火车站全名。

软件的每个按钮都提供了悬停提示，哪里不会就把鼠标悬停在哪。

搜出的最快方案为11:44出发、23:00到，用时为11小时16分钟。

从上图可以看出，野猫版搜出的前11个最快方案，最慢的都比的快，最快的只需要9小时26分钟。搜索用时1秒。

将K值改为20，搜索前20个最快方案，发现的最快方案，实际就是野猫版的第18快方案。

3.2二次中转方案搜索

将中转次数由1次改为2次，再次搜索前9个最快方案（超过9个1张截图显示不全），结果如下图所示：

从上图可以看出，中转次数从1次到2次会量变引起质变，程序无法短时通过简单搜索获取最优方案，而需要生成火车网络图，利用图论搜索。

最终生成了1张包含5.7万个节点、46.6万条支路的全国火车网络图，搜索用时达到秒。

可以看到，赣州西到保定东用搜索中转1次最快要11小时16分，用野猫版中转1次最快要9小时26分、中转2次最快要8小时34分。

(8*60+34)/(11*60+16)=76.04%，由此可见野猫版可以节省旅途约1/4的用时，赣州西到保定东的用时少了近3小时。

3.3不限次中转方案搜索

将中转次数由2次改为不限，再次搜索前9个最快方案（K值超过9个时1张截图显示不全，K值想取多大就可以取多大，几乎不影响运行速度），结果如下图所示：

可以看出，不限中转次数的搜索是真的全局搜索，生成了1张包含6.3万个节点、.2万条支路的全国火车网络图，搜索用时达到秒。

它搜出的方案是真的全网最快，赣州西到保定东只用了8个半小时。上图还可以看出，并非中转次数越多就越快，一般2次以内就可以取得最快方案。

3.4时间过滤

软件支持对出行方案进行时间过滤，限制最早和最晚的出发时间、最早和最晚的到达时间。

如果搜索之前未限制，也可以事后对搜出的结果进行时间过滤。

从赣州西到乌鲁木齐，搜索最少要用44小时45分，用野猫版只需要33小时53分钟。（缩时搜索，上图方案并非全局最优）。

车型为GDCT时，形成的火车网络图有12.7万节点、.7万支路；车型为GDCZ时，形成的火车网络图有12.8万节点、.1万支路。

网络越大，搜索用时也越长，因此，建议只输入需要的车型。

上图是我真花时间搜的，用了秒，已经是GDCZ车型下的全国最快方案。赣州西去乌鲁木齐最快要31小时36分钟，比的省了13个多小时。

如果还要考虑T和K字头的火车，则将车型改为GDCZTK，有可能会有更快方案，但搜索用时会更长，我就不演示了。

3.5指定中转站

指定中转站之后，程序搜索最短路径的难度大为下降，只需要简单搜索即可，不必图论搜索，因此搜索速度会更快。

指定1个中转站如下图所示，搜索用时为0.秒。

指定2个中转站如下图所示，用时为0.秒。

指定中转站的优先级高于中转次数，也就是如果用户输入了2个中转站、但限制了中转次数为1，程序会优先满足那2个中转站、中转2次。

指定3个中转站如下图所示，用时为6.秒。

指定4个中转站如下图所示，用时为58.秒。

总结：只支持1次中转，且搜出的最快方案，并非1次中转方案中最快的。野猫版很好的解决了这2个问题，能确保搜出的1次中转方案是最优的，并支持多次中转和时间过滤。

04

野猫版的获取与更新

人生三不朽，立德、立功、立言。本人是大学老师，开发此软件为的是广积善缘。

大家可以回复“火车”免费获取本软件的绿色版，下载之后解压，解压之后不用安装、直接双击“野猫版.exe”即可运行。

软件文件夹中有个“列车时刻表.txt”文件，是用“野猫网络.exe”从携程

转载请注明:http://www.aideyishus.com/lktp/6528.html