旅客列车线路选择的蚁群算法求解

1.西华大学 汽车测控与安全四川省重点实验室，交通与汽车工程学院，成都 610039

2.西南交通大学 综合运输四川省重点实验室，交通运输与物流学院，成都 610031

1.西华大学 汽车测控与安全四川省重点实验室，交通与汽车工程学院，成都 610039

2.西南交通大学 综合运输四川省重点实验室，交通运输与物流学院，成都 610031

1 引言

随着高速铁路的建设及投入运营，特别是在高速铁路与普通铁路共同形成一个四通八达的铁路网后，旅客列车的开行方案制定将更加复杂。在线路组成要素和功能确定的前提下，有必要对旅客列车的线路选择方案进一步优化，即研究旅客列车是选择既有铁路还是高速铁路运行。目前，国内外许多学者对于线路选择问题进行了大量的研究[1-8]，在交通运输方面的成果主要包括：

（1）公交线路选择。主要的研究集中在保证换乘次数较小的情况下，合理选择公交走行线路和停靠站点，采用的方法主要是运筹学中的最短路径算法，如纺锤算法、Dijkstra算法、Floyd算法等。

（2）公路运输线路选择。主要集中在运送特殊货物（如大件货物）时需要对运行走向和经由站点进行选择，采取的方法主要是综合几个线路方案，采用层次分析、模糊综合评价等方法进行方案比选。

（3）铁路列车运行线路选择。主要是对铁路运输通道内两条并行的线路进行分工，然后选择合理线路，采用的方法主要是一些启发式算法，如遗传算法、粒子群算法等。

本文在前人研究成果的基础上，以运输成本最少为优化目标，利用蚁群算法对旅客列车的线路选择方案进行了优化，并根据旅客列车的线路选择决策问题与蚁群活动的相似性，对该问题进行了蚁群算法（ACO）设计，给出了相应的求解策略。

2 旅客列车线路选择的特殊性及与蚂蚁寻优的相似性描述

2.1 旅客列车线路选择的特殊性

由于铁路运输与公路、航空、水运等运输方式有很大的不同，铁路运输的机车、车辆、轨道、站场，及其他一切营运设施专供铁路使用。正是由于铁路对轨道的独享性，以致铁路列车运行线路的选择，相比公路运输或城市道路运输而言缺乏一定的机动性。通常情况下，铁路部门每隔一段时间（一般为一年或半年）会根据铁路网的更新情况重新编制旅客列车运行图。计划运行图一旦制定，将不得进行修改。计划运行图的编制一般是根据编制人员的经验和常用的普通方法进行，本文的研究目的是为编制正式的高速铁路旅客列车运行图提供一种新的方法，即该问题的应用场景是在编制正式列车运行图之前进行的一种可行性研究和分析，下面的描述和分析也是基于此应用背景进行的。

2.2 旅客列车线路选择与蚂蚁寻优的相似性

蚁群算法是受自然界中蚂蚁群体合作行为的启发而产生的，它是由意大利学者Dorigo M在20世纪90年代提出的一种分布式智能模拟算法。蚂蚁在寻找食物或寻找回巢路径的过程中，会在它经过的地方留下一些化学物质，即“信息素”。后面经过的蚂蚁能够感知这种物质，并且倾向于朝着该物质浓度高的方向移动，以致最后寻找到最优路径。蚁群算法是一种随机的通用试探法，具有正反馈、较强的鲁棒性、分布式的特点，并且具有一定的系统学特征[9-11]。

旅客列车线路选择决策问题主要考虑的是运输成本，通常情况下运输成本要受旅行速度、运行调整、综合能力以及旅客服务供给的约束，因此旅客列车线路选择的决策优化需要在上述约束条件下，保证完成运输任务，并使得运输成本最少。从物种对己最优选择策略出发，列车选择最优开行方案与蚂蚁寻找最优路径具有很大的相似性，由此可以借鉴蚂蚁寻优的过程，将蚁群算法应用于线路选择方案的优化问题。首先将路网上的始发列车设定为要寻找最优线路方案的蚂蚁，列车总数为蚂蚁数量，而它们面临选择的方案为既有线或高速铁路，并且在任何一个能够转线的车站（K类节点）都将面临再选择。如果线路上的某个车站没有可转线节点（J类节点），则不进行选择，继续执行上一个选择的方案；如此可以将旅行速度、运行调整、综合能力以及旅客服务供给等约束条件转化为蚂蚁在线路上残留的信息素，蚂蚁可根据线路上的信息素量进行选择。由于铁路运输通道是一个封闭的网络，也就是说只要给代表列车的蚂蚁确定一个起讫点，蚂蚁在路网上最终总能找到一个满意的方案。

3 求解旅客列车线路选择问题的ACO设计

3.1 旅客列车线路选择的转移概率

旅客列车 p(p=1，2，…，m)在选择出行线路的过程中，根据高速铁路和既有线上的信息量来决定其选择结果。这里采用禁忌表tabp(p=1，2，…，m)来记录旅客列车选择经过的车站和区间，集合随着tabp进化过程作动态调整。在搜索过程中，旅客列车根据各条径路上运输线路的信息量及路径的启发信息来计算状态转移的概率，在t时刻第 p列旅客列车在铁路运输通道内从车站i到 j时选择第k（k=1表示高速铁路；k=0表示既有线）种线路方式的状态转移概率为：

式中，α为信息素启发式因子，表示轨迹的相对重要度，反映了旅客列车在选择经由线路的过程中所累积信息在旅客列车选择时所起的作用，值越大表示旅客之间的协作性越强，一般取值在[1，5]；β为期望启发式因子，表示能见度的响度重要性，反映了旅客在选择经由线路过程中启发信息在旅客选择运输线路时的受重视的程度，值越大则该状态转移概率越接近于贪心规则，一般取值在[1，5]；ηij(t)为启发函数，其表达式如下：=，其中表示车站i到 j的第k种线路方式的距离，该函数表示旅客从车站i到 j时选择第k种线路方式的期望程度。

3.2 信息量的描述

由式（1）可知，线路选择问题的信息素表示为各条线路上旅行速度、运行调整、综合能力以及旅客服务供给。将车站以及车站之间运输方式的线路构成一个有向网络图，各边上的信息量用旅客列车选择线路方式的重要影响因素（包括旅客广义出行费用、服务评价）加以描述。在线路选择问题上，信息量可以看作是第k种线路方式对旅客列车的吸引强度，为此需要将出行费用以及服务评价统一量纲，或者加以合理化处理才方便进行描述。如果仅将列车选择某种线路所需花费的费用作为线路上的信息量，可以采用先确定一个相对最优的可行满意线路选择方案，再对该方案进行服务水平的后评价，即在根据蚂蚁觅食的思路确定线路选择方案后仅对此种线路选择方案条件下的旅客服务进行评价，只要评价结果在合理范围内则认为该种方案是可行的。

此处引入列车出行时间价值的概念[12-13]，将旅客列车经由线路所需花费换算为单位时间费用，即元/h，则信息量可表示为：

3.3 信息量的更新

由于列车在线路上经过之后，线路上的信息量要发生变化，因此需要对列车经过线路上的信息量进行更新，信息量的更新方程如下：

式中，(1-ρ)表示信息素的残留因子，ρ∈[0，1]。

根据旅客列车的等级、速度的不同进行分类，在每一列车由始发站开始对高速铁路还是既有线做出选择时给列车赋予一定的初始信息量值。等级越高的列车，赋予高速铁路的信息量值也越高；反之对于等级越低的列车赋予高速铁路的值越低。由于高速铁路上运行的列车速度有一定要求，不能太低，否则将影响高速铁路能力的发挥，根据式（1）可知，等级高的列车相对等级低的列车选择高速铁路的概率要大。

4 旅客列车线路选择问题的ACO求解策略

根据上述关于线路选择方案与蚁群算法的共性、信息量及更新公式的描述，可以根据线路选择方案的基本原则对旅客列车进行分类。假设某运输通道铁路网上旅客列车分类如表1所示，旅客列车线路选择方案的寻优过程就是使得Ant（1）～Ant（5）五个蚁群中的蚂蚁各自均选择得到最优的路径。

表1 列车线路选择的蚁群算法描述分类

由于五个蚁群的技术速度、参数以及两种线路对不同蚁群的吸引程度均不相同，因此可采用1～9的标度方法来标定高速铁路或既有线对旅客列车的吸引程度。由于单独蚂蚁群体的寻优策略是在整体的约束条件下进行的，蚁群群体间的相互关联程度与整体的寻优线路方案并不矛盾，因而采取对每个蚁群的蚂蚁进行单独计算（即对每个蚁群单独寻优）也是可行的。

4.1 Ant（1）的寻优策略

蚁群Ant（1）的特点是列车速度高达350 km/h以上，且高速铁路对其的吸引程度为0.9，远远高于既有线。相对而言，此类蚂蚁的线路选择比较单一，基本上在满足条件的情况下均是在高速铁路上运行，只有当出现天窗时间的时候会下线到既有线上运行。

步骤1参数初始化。令t=0，且循环次数Nc=0，设置最大循环次数Ncmax；将m1只蚂蚁置于n个铁路运输通道路网的车站上，可转线节点为K类节点，不可转线节点为J类节点。

步骤2循环次数，Nc←Nc+1。

步骤3蚁群Ant（1）的禁忌表索引号k=1。

步骤4蚂蚁总数k←k+1。

步骤5蚂蚁根据此类蚁群的特点选择车站i到 j的高速铁路方式运行；当列车满足不满足高速铁路运行的条件但符合既有线条件时则下既有线运行。

步骤6修改禁忌表，将选择好的蚂蚁移动到新的车站，并把该车站移动到该蚂蚁的个体禁忌表中。

步骤7蚂蚁到达 j站后i←j，且令与 j紧相连的前进方向的车站个数为x；若x＝1则继续选择由步骤5选择的第k种线路方式前进，若x∈{K类节点}且正好是天窗维修时间则跳至步骤5重新进行选择。

步骤8若x＝0且k＜m，则跳转至步骤4，否则执行步骤5。

步骤9若满足结束条件，则退出并输出结果，否则清空禁忌表并返回步骤2。

4.2 Ant（2）、Ant（3）、An（4）的寻优策略

蚁群 Ant（2）、Ant（3）、Ant（4）的特点是列车速度为100～160 km/h、160～250 km/h和 250～350 km/h，且高速铁路对其的吸引程度分别为0.7、0.5、0.3。由于这三类蚂蚁的线路方式选择比较复杂，且有可能因线路吸引程度及线路上残留信息素的不同而产生很大的变化，因此需要对线路残余信息量的设计和更新进行综合考虑，其蚁群选择策略如下：

步骤1参数初始化。令t=0，且循环次数Nc=0，设置最大循环次数Ncmax；将m2+m3+m4只蚂蚁置于n个铁路运输通道路网的车站上，并设置各车站间有向图上各运输线路的初始信息量为常数，=con，其中 con=0，且=0；可转线节点为K类节点，不可转线节点为J类节点。

步骤2循环次数，Nc←Nc+1。

步骤3旅客列车的禁忌表索引号k=1。

步骤4旅客列车总数k←k+1。

步骤5旅客列车根据状态转移方程公式计算的概率选择车站i到 j的第k种线路方式运行，j∈{C-tabp}。

步骤6修改禁忌表，con←con+1。

步骤7列车到达 j站后i←j，且令与 j紧相连的前进方向的车站个数为x；若x＝1，则继续选择由步骤5选择的第k种线路方式前进，若x＝2，则跳至步骤5重新进行选择。

步骤8根据式（3）、（4）更新每条经路上高速铁路与既有线各自线路区间的信息量。

步骤9若 x＝0且k＜m，则跳转至步骤4，否则执行步骤5。

步骤10若循环次数Nc≥Ncmax，则退出并输出结果，否则清空禁忌表并返回步骤2。

4.3 Ant（5）的寻优策略

蚁群Ant（5）的特点是列车速度高100 km/h以下，且高速铁路对其的吸引程度为0.1，远远低于既有线。相对而言，此类蚂蚁的线路选择也比较单一，基本上均在既有线上运行，只有在极少数特殊情况下才有可能上高速铁路运行，但原则上暂不允许低速旅客列车上高速线运行，其蚁群选择策略如下：

步骤1参数初始化。令t=0，且循环次数Nc=0，设置最大循环次数Ncmax；将m5只蚂蚁置于n个铁路运输通道路网的车站上，可转线节点为K类节点，不可转线节点为J类节点。

步骤2循环次数，Nc←Nc+1。

步骤3蚁群Ant（5）的禁忌表索引号k=1。

步骤4蚂蚁总数k←k+1。

步骤5蚂蚁根据此类蚁群的特点选择车站i到 j的既有线方式运行；若满足极少数特殊情况则允许上高速铁路，但当特殊情况解除之后则应立即返回既有线运行。

步骤6修改禁忌表，将选择好的蚂蚁移动到新的车站，并把该车站移动到该蚂蚁的个体禁忌表中。

步骤7蚂蚁到达 j站后i←j，且令与 j紧相连的前进方向的车站个数为x；若x=1，则继续选择由步骤5选择的第k种线路方式前进，若x∈{K类节点}且满足特殊情况（诸如发生事故或灾害）则跳至步骤5重新进行选择。

步骤8若x=0且k＜m，则跳转至步骤4，否则执行步骤5。

步骤9若满足结束条件，则退出并输出结果，否则清空禁忌表并返回步骤2。

4.4 求解实例分析

应用上述求解旅客列车线路选择问题的ACO策略，对京广高速铁路武广段的旅客列车线路选择方案进行求解：

步骤1根据式（2）确定每种蚁群相对高速铁路与既有线上的蚁群信息量，旅客列车选择某线路的单位时间价值[13]如下：

运输距离小于等于200 km时取20.21元/h；运输距离为200～300 km时取14.44元/h；运输距离为300～500 km时取13.25元/h；运输距离为500～700 km时取13.50元/h；运输距离为700～1 100 km时取13.50元/h；运输距离大于1 100 km时取17.04元/h。

步骤2确定旅客列车选择第k种线路方式出行的单位距离出行费用。根据文献[13]的计算，确定旅客列车选择高速铁路的单位费用为0.25元/km，选择既有铁路的单位费用为0.15元/km。

步骤3计算线路上的信息量，按照式（2）进行计算。

步骤4根据状态转移方程（1）计算列车选择线路方式的结果，随后根据对蚁群的分类按照寻优策略分别求解Ant（1）、Ant（2）、Ant（3）、Ant（4）、Ant（5）五类蚁群的最优分工方案。其求解结果如表2所示。

总的来看，由ACO算法求解出的武广通道内高速铁路和既有线的线路选择方案，主要体现在选择的路径是高速铁路还是既有线，以及在可转线节点是否转线（由于转线的计算表格比较大，此处略）。经过ACO算法优化的方案与实际采用方案相比，在以下两个方面有明显优势：

（1）通过对高速铁路与既有线的线路选择，实现了二者的合理分工，改善了既有线旅客列车的运行状况，优化方案较之实际方案既提高了既有线旅客列车的速度，又提高了高速铁路的利用率。

（2）优化方案兼顾了高速铁路与既有线的能力综合利用，较之实际方案能使两条线路的能力负荷得到较好的匹配。

5 结论

随着高速铁路的快速发展，高速铁路与原有铁路既有线逐步交错成网，旅客列车的开行方案需要考虑列车的线路选择问题。通过对旅客列车线路选择方案问题与蚁群活动的相似性描述，根据蚁群算法对该问题进行了设计，建立了旅客列车线路选择的状态概率函数，并在信息量的描述中引入了列车出行时间价值的概念。在旅客列车线路选择问题的ACO求解策略中，采用1～9的标度方法来标定高速铁路（既有线）对旅客列车的吸引度，并对每个蚁群单独寻优。通过对京广高速铁路武广段的旅客列车线路选择方案进行实际分析，结果表明采用蚁群算法能够快速求解出满意的旅客列车线路选择方案，达到了线路选择方案优化的目的，为今后基于路网的旅客列车线路选择方案的编制提供了一种参考方法。

[1]徐勇，李杰，张军芳，等.新型公交网络模型与最优线路选择算法[J].系统工程理论与实践，2011，31（11）：2234-2240.

[2]Abdelkader T，Naik K，Nayak A.Choosing the objective of optimalrouting protocols in delay tolerantnetworks[C]// ICENCO 2010，2010：16-21.

[3]Arturas P，Ramunas P.Evaluation criteria and a route selection system for transportating oversize and heavyweight cargoes[J]. Transport，2012，27（3）：327-334.

[4]乔国会，张东杰，聂钦中，等.大件货物公路运输线路选择方法研究[J].物流技术，2006，214（4）：55-57.

[5]彭其渊，殷勇，闫海峰.客运专线建成后铁路运输通道合理分工模型[J].西南交通大学学报，2005，40（6）：788-792.

[6]张怡.铁路客运专线与既有线对跨线旅客列车的分工[J].铁道运输与经济，2006，28（7）：58-59.

[7]罗建，薛锋.基于改进蚁群优化算法的客运专线旅客出行方式选择[J].系统工程，2008，26（1）：82-85.

[8]胡秀婷.不同阶段高速铁路与既有线分工方案[D].成都：西南交通大学，2012：42-45.

[9]李士勇，陈永强，李研.蚁群算法及其应用[M].哈尔滨：哈尔滨工业大学出版社，2004.

[10]吴宗彦，王景华，张建军，等.基于蚁群算法的智能运输调度问题的研究[J].计算机工程与应用，2006，42（35）：11-14.

[11]杜艳平，尹晓峰，刘春煌.采用蚁群算法求解铁路空车调整问题[J].中国铁道科学，2006，27（4）：119-122.

[12]朱从坤，王洁，冯焕焕.区域运输通道内客运方式分担率模型[J].交通运输工程学报，2005，5（4）：111-115.

[13]南敬林.京沪通道旅客行为时间价值研究[J].铁道经济研究，2002（3）：36-38.

旅客列车线路选择的蚁群算法求解

罗 建1，2，薛 锋2

LUO Jian1，2,XUE Feng2

1.Vehicle Measurement,Control and Safety Key Laboratory of Sichuan Province,School of Transportation and Automotive Engineering,Xihua University,Chengdu 610039,China
2.Sichuan Province Key Laboratory of Comprehensive Transportation,School of Transportation and Logistics,Southwest Jiaotong University,Chengdu 610031,China

After the completion of the high-speed railway line elements within the passenger corridor and line functions will be changed greatly,schedule of passenger trains in the passenger corridor also needs to be further optimized.Ant Colony Optimization algorithm（ACO）is adopted in passenger train route selection and optimization,and the updating methods of transition probability and information are provided.The corresponding solution tactics have been made by optimization for every ant colony. The example proves that better result is received.Based on the route selection and decision optimization,it provides a new reference method of the passenger train route selection and decision optimization under the conditions of the railway network.

passenger train;route selection;ant colony optimization algorithm;decision optimization;solution

高速铁路建成后客运通道内的线路组成要素及线路功能将发生较大变化，旅客列车在通道内的线路选择方案也需要进一步优化。采用蚁群算法（ACO）对旅客列车的线路选择进行了设计，给出了转移概率及信息量更新方法，并采用对每个蚁群单独寻优的思路，制定了相应的求解策略。经过实例验证，取得了较好的结果，为今后基于路网条件下的旅客列车线路选择方案决策优化提供了一种新的参考方法。

旅客列车；线路选择；蚁群算法；决策优化；求解

A

U293

10.3778/j.issn.1002-8331.1211-0305

LUO Jian,XUE Feng.Solution for passenger train route selection based on ant colony optimization algorithm.Computer Engineering and Applications,2013,49（11）：11-14.

国家自然科学基金（No.61203175）；汽车测控与安全四川省重点实验室（西华大学）开放研究基金资助项目（No.Szjj2012-009）；综合运输四川省重点实验室开放基金项目（No.B01B1201）；西华大学2010年校重点基金项目（No.Z1020308）。

罗建（1982—），女，工学博士，讲师，主要研究方向：交通运输规划与管理、运输组织优化；薛锋（1981—），男，工学博士，副教授，主要研究方向：运输组织理论与系统优化、交通运输集成智能化。E-mail：luo06_jian2000@126.com

2012-11-26

2013-02-21

1002-8331（2013）11-0011-04

CNKI出版日期：2013-03-15 http://www.cnki.net/kcms/detail/11.2127.TP.20130315.1146.003.html