铁路旅客旅行换乘方案优选算法

《铁路旅客旅行换乘方案优选算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、维普资讯http://www.cqvip.com第28卷，第6期中国铁道科学Vo1．28Na62007年l1月CHINARAILⅥYSCIENCENovember，2007文章编号：1001—4632(2007)06—0122—06铁路旅客旅行换乘方案优选算法崔炳谋，马钧培。，陈光伟，王明才(1．铁道科学研究院电子计算技术研究所，北京100081；2．兰州交通大学交通运输学院，甘肃兰州730070~3．铁道部信息化办公室，北京1008444．铁道部信息技术中心，北京1008445．沈阳铁路局，辽宁大连116001)摘要：为给铁路旅客选择

2、合理的旅行方案提供参考，以旅行目标值与换乘目标值之和最小作为目标函数值，考虑旅客从起点站出发、最终到达终到站、在中转站进出平衡的约束条件，建立旅客旅行换乘方案选择问题的数学模型。分别给出旅行时间、换乘次数、票价、距离、到发时刻和综合指数6种目标权值的确定方法，提出最短路法和列车匹配法2种求解方法。最短路法是通过构造并简化旅客运输网络，求出网络上若干条次短路，再根据各条次短路上列车的接续，构造列车换乘方案网络图，根据该网络的目标权值确定最短路，得到最优换乘方案。列车匹配法是根据列车运行图信息直接搜索发、到站的接续列车集合，求其两列车对应的

3、重合停车站，根据重合停车站集合的情况选择迭代步数，剔除显然不利方案，构成换乘方案，根据方案的权值进行比选，得到最优换乘方案。对2种算法均用C#编程实现，并用现有的全路客票数据进行检算。计算结果表明：2种算法均能得到最优换乘方案；列车匹配法所用计算时间比最短路法少160ms。关键词：旅行路径；换乘方案；方案比选；最短路；列车匹配；优选算法中图分类号：U293．32文献标识码：A随着铁路客运专线的建设和运营，铁路路网密为Z列车在i站的开车时问；t为Z列车在站的度增加，旅客换乘方案_1]数量剧增，为了提高铁路到达时间。客运服务的质量，铁路应建

4、立辅助旅客选择旅行路以旅行目标值与换乘目标值之和最小作为目标径的支持系统，为旅客选择合理的旅行方案(路函数值，考虑旅客从起点口站出发、到b站终到、径、中转地点、中转次数等)提供参考。本文根据在中转站进出平衡的约束条件，建立以下旅客旅行路网结构、列车等级、经由、停靠站等信息，建立路径及换乘选择问题的数学模型。旅客换乘方案优化数学模型，提出用最短路法和列rainr∑∑∑锄叫+iEJUaJEJU6z∈to车匹配法2种计算方法进行求解，计算得到优化的∑∑∑∑∑(xi#xlpz')叫，)旅行方案。iEJUaJEJPEJUblELi，∈LiP(1)

5、1模型建立S．t．∑∑z一1(2)设z州为0，1变量，当旅客从i站到站乘坐jEJUbz∈toz列车时为1，否则为0；，为0，1变量，当旅客∑∑z捌一1(3)iEJUaz∈∥从站到P站乘坐Z列车时为1，否则为0；叫为∑∑一∑∑z，gjEJ(4)旅客从i站到站乘坐z列车时的旅行目标值；iEJUa}∈PEJUbF∈U叫埘，为旅客在站从Z列车换乘Z列车时的换乘目z一{0，1}ViEJU口，∈JUb，Z∈标值；J为中转站集合；口，b分别为旅客旅行的始L(5)发站、终到站；L为经过i站到站列车集合；t式(1)中和叫，针对不同的目标，其取值如收稿日期

6、：2006—09—05；修订日期：2007—09—17作者简介：崔炳谋(1961一)，男，陕西武功人，教授，博士研究生。维普资讯http://www.cqvip.com第6期铁路旅客旅行换乘方案优选算法123一F。顶点、边和边上的权。并根据用途对其简化，以减(1)旅行时间：包括列车的运行时间和在换乘少计算量。站的换乘时间。运行时间取旅客乘坐的列车从上车第2步：求该网络图G，从n点到b点的若干条站到下车站间的到开时间差。换乘时间取换乘的2最短路(即1条最短路和若干条次短路)，并排序列车在换乘站的到开时间差，若差值小于1个紧接形成队列。续标

7、准(一般取一20min)，则时差应加1440第3步：从队列的开头取每一条最短路，用匹rain。即伽一t一t，伽ill'一mod{tj，一t一+配列车的方法构造1个可行换乘方案网络图G一1440，1440}。(，E，w)，其中，E，w分别为换乘方案网络图(2)换乘次数。列车在运行途中，若不换乘，G的顶点、边和边上的权。则取伽一O，若换乘1次，则取伽ill'一1。第4步：求该换乘网络图G从起点到终点的1(3)票价：即为列车票价。即，Wij一户，条满足一定权值的最短路(如旅行时间、票价等权叫，一O，其中户为列车z从i站到J站的票价。值目标最小

8、)，即得到最终的最佳旅客换乘方案。(4)距离：即为列车运行距离。即，伽一2．1．2构造旅客运营网络图d，伽∥一O，其中d。为i站到J站的里程。以客运营业站为顶点，以相邻两客运营业(5)到发时刻。列车的始发、