关于铁路换乘算法的一些思考

前不久看到了一个视频《我国有哪些距离很近且不在同一线路上的火车站？》，很好奇在这些地理位置相近的车站间进行转移，若只能采用铁路换乘的形式，在理论上的最优路径是什么？尝试了下12306的换乘查询，但不出所料给出的几乎都是包含同城换乘的方案。其它工具更是倾向于都是综合来看最优的方案，但并不符合我这个要求。于是我在 NAS 上挂了个任务，爬取了全国铁路列车的时刻表。

如果目标函数是总行程时长，这是一个非累加性的目标函数。单源最短路算法的正确性依赖于边的权值可以累加并且满足最优子结构。但目前这种情况一条路径的总成本无法通过其子路径的成本简单推导得出。

很显然，不能简单地在以物理车站为节点的图上跑最短路。于是我们可以定义以当前路径的到达时间，整个旅程的初始出发时间和当前所在的车站为一个状态，然后按照状态的经由时间维护优先队列跑 Dijkstra ，问题就解决了。

但是似乎这样效率并不高，想了下如果目标只是求最优的一个解，可以直接舍弃掉那些到达晚于已有状态且出发早于已有状态的状态。不过问题是这样并无法求出前 K 个最优路径，但作为寻找可行的解是足够了。于是就有了CRTransfer这个项目。

如果目标函数是换乘次数的话，简单 BFS 即可。跑出来目前全国任意两站之间最大的最小化换乘次数是 6 次。举个例子：

香坊 换乘 (2小时 38分钟)
K5171/K5174: 香坊 11:42 → 哈尔滨 11:52 (7公里)
哈尔滨 换乘 (21小时 5分钟)
K1525/K1528: 哈尔滨 08:57 → 长春 11:55 (246公里)
长春 换乘 (21小时 53分钟)
Z325/Z328: 长春 09:48 → 贵阳 03:11 (3563公里)
贵阳 换乘 (7小时 31分钟)
昭通 换乘 (15小时 21分钟)
K9501/K9504: 贵阳 10:42 → 昭通 18:07 (391公里)
昭通 换乘 (15小时 21分钟)
5636: 昭通 09:28 → 内江 19:25 (367公里)
内江 换乘 (15小时 8分钟)
5611: 内江 10:33 → 迎祥街 11:16 (30公里)

进而，我们思考如果限制只能一次换乘，那么有多少车站能互相通达？这是最大团问题的变种，懒得手写分支限界了转换成补图直接调用 KAMIS 算出来答案是 857 。

包含这些车站

万安县,万州北,万源,三明北,三门县,三门峡,三门峡南,三门峡西,上海,上海南,上海松江,上海虹桥,上海西,上虞,上虞南,上饶,东台,东安东,东海县,东胜西,东莞,东莞东,东莞南,中卫,中山,丰城,丰城东,丰都,临平南,临汾,临汾西,临沂北,临泉,临海,临淄北,临清,临潼,丹徒,丹江口,丹阳,丹阳北,丽水,义乌,义马,乌兰察布,乌鲁木齐,乐山,乐平北,乐昌东,乐清,乐清东,九华山,九江,乾县,云阳,亳州,亳州南,介休东,仙居,仙桃西,仙游,仲恺,任丘,余姚,余姚北,余干,佛坪,侯马,侯马西,保定东,保康县,信丰西,信阳,信阳东,修文县,修武西,偃师,光明城,兖州,全州南,全椒,公主岭,公主岭南,六安,六枝南,六盘水,兰州,兰州西,兰考,兰考南,共青城,兴国西,兴城,兴城西,兴山,内江北,内黄,冠豸山南,冷水江东,凤凰古城,凤台南,凯里,凯里南,利川,剑门关,勉县,包头,包头东,北京,北京丰台,北京南,北京西,北戴河,十堰,十堰东,千岛湖,华山,华山北,南京,南京南,南充,南召,南宁,南宁东,南平市,南昌,南昌东,南昌西,南通,南通西,南阳,南阳东,南靖,博罗北,卫辉,即墨北,原平,原平西,厦门北,双流机场,古城东,句容,句容西,台前,台安,台州,台州西,合川,合肥,合肥北城,合肥南,吉安,吉安西,吉首东,吐鲁番北,含山南,吴忠,周口东,呼和浩特,呼和浩特东,和平北,咸宁北,咸阳,咸阳北,咸阳西,哈密,哈尔滨,哈尔滨西,响水县,唐山,商丘,商丘东,商丘南,嘉兴,嘉兴南,嘉善南,嘉峪关,嘉峪关南,四平,四平东,固安,垫江,城固,城固北,城阳,塘沽,夏格庄,大冶北,大同,大同南,大庆西,大港南,大英东,大连北,天台山,天水,天水南,天津,天津南,天津西,天门南,太仓,太仓南,太原,太原南,太和东,太姥山,太湖南,太谷东,奉化,奉节,如皋,如皋南,姜堰,威海,威海北,娄底,娄底南,婺源,孝感东,孝感北,宁县,宁国南,宁强南,宁德,宁波,宁海,宁陵县,安吉,安庆,安庆西,安康,安阳,安阳东,安陆西,安顺,安顺西,定西,定西北,定远,定陶,宜兴,宜宾,宜昌东,宜春,宝丰,宝应,宝鸡,宝鸡南,宣城,宣威,宣汉,宿州,宿州东,宿松东,宿迁,富县东,富源北,富阳西,察素齐,寿县,射阳,将乐,尤溪,山海关,山阴,山阴南,岐山,岚山西,岳阳东,峡江,嵊州新昌,巢湖,巢湖东,巨野北,巩义,巩义南,巫山,巴东,常州,常州北,常德,常熟,平原,平原东,平度,平潭,平遥古城,平阳,平顶山,平顶山西,广元,广安,广州,广州北,广州南,广州白云,广德,广德南,庆城,庆阳,庐山,庐江西,应县,应县西,廊坊,延安,延平,建始,建德,建湖,建瓯西,开原,开封,开封北,引镇,张家口,张家港,张家界西,张掖,张掖西,当涂东,彬州东,彭山北,徐州,徐州东,德兴,德安,德州,德州东,德惠,德清,德清西,德阳,忻州,忻州西,怀仁东,怀化,怀化南,恩施,息烽,惠安,惠州,惠州北,惠阳,成都东,成都西,扬州,扬州东,扶余,扶沟南,抚州,文登东,新乡,新乡东,新乡南,新余,新余北,新化,新化南,新县,新安县,新干东,新沂,新沂南,新郑机场,新都东,方城,旌德,无为,无锡,无锡东,日照,日照西,旬阳,昆山,昆山南,昆明,昆明南,昌图,昌邑,昌黎,明光,明港东,晋中,晋城东,晋江,晏城,普宁,普安县,景州,景德镇北,曲阜东,曲靖,曲靖北,曹县,朔州东,来宾北,杨陵,杨陵南,杭州,杭州东,杭州南,杭州西,枝江北,枣庄,枣庄西,枣阳,枫林,柳州,株洲,株洲西,桂林,桂林北,桃村北,桐乡,桐城东,桐庐,桐庐东,桐梓东,梁平南,楠溪江,榆林,榆社西,樟树,樟树东,横店,歙县北,正定机场,武义,武义北,武乡,武夷山北,武威,武山,武当山西,武昌,武汉,武穴北,武进,武陟,民和南,民权,民权北,水家湖,永修,永城北,永川东,永州,永康南,永福南,汉中,汉口,汉川,汉阴,汕尾,汝州,江宁,江宁西,江山,江油,江都,江阴,池州,汤阴,汨罗东,沈丘北,沈阳,沈阳北,沈阳南,沧州,沧州西,河源,河源东,河源北,泉州,泉州东,泉州南,泊头,泗阳,泰和,泰宁,泰安,泰山,泰州,泸州,泾县,洋县西,洛阳,洛阳龙门,洞口,洪洞西,济南,济南东,济南西,浠水南,浦江,海城,海宁,海宁西,海安,海阳北,涟水,涟源,涪陵,涪陵北,涿州东,淄博,淄博北,淮南,淮南东,淮南南,淮安东,淮阳南,深圳,深圳东,深圳北,深圳坪山,清河城,渑池,渑池南,渠县,温岭,温州,温州北,温州南,渭南,渭南北,湖州,湖州东,湖州南浔,湘乡,湘潭,湘潭北,湛江西,湾沚南,溆浦,溆浦南,源潭,溧水,溧阳,滁州,滁州北,滑浚,滕州,滕州东,滦县,滦河,滨海港,滨海西,漯河,漯河西,漳州,潍坊,潍坊北,潜山,潜江,潢川,潮汕,潼南,濮阳东,灌云,灌南,灵宝,灵宝西,灵石东,烟台,烟台南,焦作,焦作西,牟平,玉屏,玉林,环县,珠海,瑞安,瑞昌,瑞昌西,瑞金,瓦屋山,甘谷,界首南,白沙铺,白河东,白河县,白洋淀,盐城,盐城大丰,盘州,盘锦,盘锦北,盛泽,睢宁,石家庄,石家庄东,石柱县,石泉县,砀山,砀山南,磁窑,磐安,祁东,祁阳,神农架,福安,福州,福州南,福清,福清西,禹城,禹城东,禹州,秦安,秦皇岛,章丘,紫阳,綦江东,红安西,红岛,练塘,绍兴,绍兴东,绍兴北,绥中,绥中北,绥德,绩溪北,绵阳,缙云,缙云西,罗源,耒阳,耒阳西,聊城,聊城西,肥西,胜芳,胶州,胶州北,自贡,芙蓉镇,芜湖,芜湖北,芜湖南,苍南,苏州,苏州北,苏州南,苏州园区,苏州新区,英德,英德西,茂名,荆州,荆门,荣成,荣昌北,莆田,莱西,莱阳,菏泽,菏泽东,萍乡,萍乡北,营口东,萧县北,萨拉齐,葛店南,董家口,葫芦岛,葫芦岛北,蒲城东,蓝村,蔡家坡,蕲春南,藁城南,虎门,虞城县,蚌埠,蚌埠南,衡山西,衡水,衡水北,衡阳,衡阳东,衢州,襄垣东,襄汾,襄阳,襄阳东,西乡,西华,西宁,西安,西安北,西安西,许昌东,许昌北,诏安,诸暨,谷城,谷城北,贵安,贵港,贵阳,贵阳北,资中北,资阳北,赣县北,赣州,赣州西,赣榆,赤壁北,赶水东,辛集,辛集南,辽中,辽阳,达州,达拉特西,运城,运城北,连云港,连江,通渭,遂宁,遵义,邓州东,邢台,邢台东,邯郸,邯郸东,邳州东,邵东,邵阳,邵阳北,邹城,郎溪南,郏县,郑州,郑州东,郑州航空港,郑州西,郴州,郴州西,都昌,鄂尔多斯,鄂州,鄠邑,鄢陵,鄯善北,鄱阳,鄱阳北,醴陵,醴陵东,重庆北,重庆西,野三关,金华,金华南,金坛,金寨,金山北,铁岭,铁岭西,铜仁南,铜陵,铜陵北,银川,锦州,锦州南,镇安,镇江,镇江南,长临河,长乐东,长兴,长兴南,长寿北,长春,长春西,长汀南,长沙,长沙南,长治东,长治南,闻喜,闽清北,阜宁东,阜宁南,阜阳,阜阳西,阳平关,阳新,阳曲西,阳泉北,陆丰,陇西,隆回,隆昌北,随州南,雁荡山,集宁南,霞浦,霸州,青岛,青岛北,青岛机场,青岛西,青州市,青州市北,青田,青白江东,静海,鞍山,鞍山西,韶关,韶关东,韶山南,颍上北,饶平,香港西九龙,马鞍山东,驻马店西,高坪,高密,高密北,高平东,高邑西,高邮,高邮北,鲁山,鲅鱼圈,鲘门,鹤壁,鹤壁东,鹰潭,麻城,麻城北,麻阳西,黄冈东,黄冈西,黄山北,黄梅东,黄河景区,黄石,黄石北,黎塘,黔江,黟县东,齐河,齐齐哈尔,龙山镇,龙岩,龙川,龙川西,龙游