基于双目标最短路的轨道交通站点布设优化
摘 要：轨道交通线路站点布设需要考虑的因素较多，其中比较重要的是线路总长度和总的客流吸引量。
为此，文章通过对站点布设原则及方法进行分析，并考虑站间距合理范围，从而建立了站点布设的网络模型。
采用双目标最短路原理并结合k—最短路算法和Dijkstra算法对模型进行了求解。
在实际决策中，决策者可以通过调整目标上限的方法获得有效路径集合，再根据实际情况或者个人偏好进行取舍。
毕业论文网 /2/view—12235208.htm 关键词：城市轨道交通；站点布设；站间距；双目标最短路；k—最短路算法；Dijkstra算法 0 引言 当前，全国各大城市修建城市轨道交通的热浪正在兴起。
但是对轨道交通的线网规划、站点设置的相关研究我国起步较晚，目前还处于探索阶段。
作为乘客集中和疏散的基地――站点，其服务功能首先是通过站点实现的，出行者是否选择轨道交通很大程度上取决于乘客到达站点的方便程度。
也就是说，轨道交通站点的布设方案直接影响到其吸引乘客的范围、服务水平、系统的运营效率甚至城市的形态布局、路网结构等。
对于目前已建成的站点，有些由于在规划设计时融入了设计者的主观意识、经验等因素，从而导致了某些轨道交通站站点分布不合理，成本巨大，并且难以与其他运输方式形成分工合理、优势互补、互相协调的局面，因而从一定程度上阻碍了其功能的全面发挥，影响了其在分担客流中的骨干地位。
文献[1]通过寻找备选点，并生成线路虚拟站点分布，以此建立了轨道交通站点布设的方法，但此方法仅仅从站间距角度考虑布设，没有将其他因素考虑进来；文献[2]仅从列车运行工况得到了站间距的上下限，但列车运行工况是一个复杂的牵引过程，其走行路程不能从简单的物理学公式计算；文献[3]使用分析方法建立了站点选址模型及估算站点数目，利用最小生成树得出了地铁建设费用和运行费用之和最小的方案，但此方法仅仅从工程造价角度考虑站点布设，没有从运输角度进行研究；文献[4]从车站费用效益方面考虑，得出了车站寿命期内总净收益最大的优化模型，此方法虽然能获取工程建设各项费用，但是它的缺陷是很难估计出车站建成后带来的具体效益，因此该方法理论上可行。
文章采用双目标最短路的优化方法对地铁站点布设问题进行优化，目的在于通过此方法为轨道交通站点布设问题提供新的解决思路，以供决策人员参考。
1 轨道交通站点布设的原则与方法 1.1 布设原则 一般来说，轨道交通站点布设应遵循以下原则[1]： 1.站点选择应该与城市土地开发现状、土地利用、道路网建设情况等结合起来，既要满足路网远期规划要求，又要充分考虑城市的可持续发展。
2.以人为本，最大限度满足旅客出行需求，合理选址，方便乘客换乘，提高出行质量，因此站点应尽可能选择在大型客流集散点，如：车站，医院，学校、大型商场等附近。
3.站点选择应经济可行，避开地质不良地段，减少对环境的干扰、破坏。
4.充分发挥列车性能，站点尽量均匀，站间距在允许范围内可适当调整，以满足人们出行需求。
5.站点布设应与其他交通方式协调发展，优势互补，使其各尽其责。
1.2 布设方法 对某一条线路来说，在其规划的最初阶段，就已经确定了其走向。
这里所要研究的是各个点的布设选址，其具体方法如下： 1.对预测的出行OD矩阵进行处理，对线网上主要的客流集散点进行标定。
并将矩阵对角线元素置为0，其目的是消除小区内部出行，然后对矩阵各行各列求和，得到各个交通小区区外的吸引量和发生量。
按照其量的大小进行排序，并按照小区总数量一定的百分比（一般取10%—15%）从大到小选点作为主要客流集散点，也是备选站点。
2.确定起点和终点。
3.确定中间点位。
以起点为圆心，以站间距的下限和上限dmin和dmax为半径分别画圆弧，其形成的圆环区域即为第一个站点的备选区域，其备选站点按照第1点的客流集散点进行选取。
记第一个站点的若干个备选点为A1，A2，A3……An，如图1所示。
再分别以A1，A2，A3……An各个点为圆心，dmin和dmax为半径圆弧，得到各自的第二个站点的备选区域，同样的记第二个站点的若干个备选站点为B1，B2，B3……Bn。
以此类推直到最后的终点为止，将各个点连接起来形成一个网络图，如图2所示。
2 轨道交通站间距上下限确定 以上设置方案中需要解决的是站间距范围问题，实际在地铁设计中，为了最大限度吸引客流，站间距需要视情况而定。
站间距过短会直接导致列车旅行速度降低，能耗增大；另外站间距过短会使得站点数量过多，导致工程投资增加。
站间距过大时，虽然旅行速度提高，但是会使旅客增加换乘的衔接时间。
因此，站间距需要确定合理的上下限值。
一般来说，不应小于公交车站距500米，但考虑到列车行驶技术条件，不应小于列车从启动加速至限制速度后立即减速制动至停车所运行的距离。
根据广州地铁一号线和上海地铁二号线采用的德国车辆技术资料，列车最高运行速度80km/h，其牵引特性曲线如图3所示[5]，列车常规制动的加速度为，假定该制动加速度适用于所有负载，并且为了简化，线路条件为平直空旷地带。
列车基本阻力R的计算公式如下[5]：其中v为列车速度（km/h），区段运行时间（h），区段 运行距离（km），其中为速度间隔内的起点速度，为速 度间隔内的终点速度，为速度间隔内平均速度所对应的单位合力，，（N?KN—1），F为牵引力。
根据上述资料和计算公式，当速度间隔取为10km/h时，列车能实现80km/h的最小站间距为1.012km[6]，因此轨道交通站间距在正常情况下不应小于1km。
对于可根据具体的城市区域，参照国内外城市经验选取，但是不能大于乘客平均乘行距离，根据各城市站间距对比分析，最大没有超过3km[1]。
实际上对于站间距，应分为市区和郊区两部分分别考虑。
对于市区来说，人口比较密集，为了方便乘客出行及换乘，轨道交通站间距应设置小一些，虽然列车可能频繁启动、停车，但是其产生的社会效益远远大于其弊端，如东京地铁日比谷线最小间距只有400m，充分说明了此种站点设置有利于吸引客流；对于郊区，人口比较稀疏，人们的出行距离一般比较长，若设置小站间距将会频繁加速、制动，不但影响列车运行效率，而且耽误人们出行时间，因此郊区的站间距可以适当加大。
3 模型描述及算法分析 3.1 模型描述 对图2的方案图的有向边进行赋权，其中第一个权值代表线路的客流吸引量，第二个权值代表实际距离。
因此，目前的问题是需要求出从起点至终点的一条线路，使这条线路客流吸引量最大，并且经过的各个站点长度之和最短的一条路。
此问题是典型的双目标最短路问题，至于目标中的最大吸引量可以用其中最大的值分别减去各个客流量，转化为求最小来处理。
对于双目标最短路问题，一般的有，对于网络图G=（N，E），N为顶点集合，E为有向边集合，，. 令和分别为从起点至终点路径的目标1和目标2的值。
为了得到时变网络下的双目标模型，需要定义如下变量： 3.2 模型算法分析 双目标最短路问题属于多目标最短路问题中的一种常见情况，文献[7，8]对一般的双目标最短路算法进行了研究，并提出了一种交互式双目标算法。
文章利用k—最短路算法[11]结合有效路径进行求解，运算过程中决策者可以根据需要对目标值的上限进行修改，从而获得有效路径的集合。
在此，先给出以下定义： 定义一： 若和是从起点O到终点D之间两条路径。
如果，，且至少一个为严格不等式，则称在Pareto最优意义下，路径有效于路径。
若不存在任何一条路径有效于p，则称p为模型BOSPM的有效路径。
定义三：若为从起点O到终点D之间目标最短路，为路径的目标的值，为从起点O到终点D之间目标最短路，为路径的目标的值，则称为BOSPM的理想点。
若=，令==，则称为BOSPM的绝对最短路径。
由于实际求解过程中，往往不存在绝对最短路径，通常只需要找到满足决策者要求的有效路径。
这里可以利用Dijkstra算法得到考虑单个目标时的最短路，并获得其最小值和。
根据得到的目标1和目标2的最小值，给出一个可以接受的目标1和目标2的上限值up和up，然后利用k—最短路算法分别得到up和up的解集空间和，取二者交集，因此能够同时满足两个目标限制条件，且具有较小的目标值。
如图4所示，假设A，B分别为目标和的最优解，这样集合的路径就落在矩形CDEF之内。
可能有三种情况：（1），（2），（3）。
对于（1），表示交集为空集，此时需要继续调整目标1和目标2的上限值，直到产生交集；对于（2），此时的路径可能为最优路径，若对此结果不满意可以重新调整目标1和目标2的上限值；对于（3）集合内路径不止1条，决策者可以根据个人偏好或采用模糊多目标格序决策进行进一步选择。
4 算法步骤及复杂度 4.1 算法步骤 经过前面的分析，很容易得到双目标最短路问题的算法步骤： （1）利用Dijkstra算法分别算出网络图G=（N，E）中目标1和目标2的最短路和。
（2）若=，则算法结束，否则转步骤（3） （3）令和为路径和的目标值，并给出目标1和目标2的上限up和up。
（4）利用k—最短路算法分别算出上限up和up的路径集合和 （5）取和的交集 （6）若转步骤（7）；若，决策者认为此方案可行则停止，否则转步骤（7）；若，若决策者认为都可行则停止，否则转步骤（7）， （7）继续调整目标1和目标2的上限值，转步骤（4）。
4.2 算法复杂度 首先利用Dijkstra算法时的复杂度为，然后利用k—最短路算法的复杂度为，考虑到需要对上限进行修改，但其计算复杂度仍可记为[12]。
5 算例 图5给出了一个地铁站点布设方案图，边权分别代表实际距离和该线路客流吸引量，如表1所示。
现需要得出从起点到终点的一条线路，使得吸引客流量之和最大，且线路长度之和最小。
由于是求吸引量最大，不能直接利用上述算法，需要进行处理，可用最大值50分别减去各个吸引量值，如表2所示。
为了表示方便，先利用k—最短路算法求出从起点至终点各个目标的最短路序列，如表3所示。
然，目标1和目标2的最短路并不在同一条线路上，因此交集，此时，需要对两个目标上限进行适当扩大，并利用k—最短路算法求出有效路径的集合，如表4所示。
由此可见，若决策者要求目标1，2的上下限不超过（4，35），那么最优线路只有O—1—5—D，其线路长度为4，客流吸引量为40+39+37=116。
在实际决策中，决策者可以根据实际情况增加决策变量，演变成多目标最短路问题，求解思路类似，从而达到良好的实际效果。
6 结论 文章根据站点布设的原则和方法，并结合列车运行工况对站间距的合理范围进行了分析，建立了站点布设的双目标最短路模型，并利用Dijkstra算法和k—最短路算法对有效路径进行搜索，最终得到满意路径。
此方法可以为实际的轨道交通站点布设提供一种新的思路，起到辅助决策作用。
长安大学硕士学位论文，2006 [2] 李媛媛，市域轨道交通快线的合理站间距研究[D]。
北京交通大学硕士学位论文，2011 [3] 吴红兵，城市轨道交通线路与站点规划理论研究[D]。
重庆大学硕士学位论文，2006 [4] 朱蓓玲，合理确定地铁车站站间距离[J]。
铁道标准设计，1999（3）：19—20。
[5] 李君，叶霞飞，城市轨道交通车站分布方法的研究[J]. 同济大学学报（自然科学版），2004（8）：1009—1014 [6] Current J，Revelle C，Cohon J. An interactive approach to indentify the best compromise solution for two objective shortest path problems[J]. Computer & Ops，Res，1990，17（2）：187—198. [7] Coutinaho—Rodrigues J，Climcao J，Current J. An interactive bi—objective shortest path approach：search for unsupported non—dominated solution[J]，Computer & Ops. Res，1999，26：789—798 [8] 郝光，张殿业，王东梅，双目标最短路有效解的快速算法[J]. 公路交通科技，2007（11）：96—99+104 [9] CHEN Y L，An algorithm for finding the k quickest path in a network[J]，Computer & Ops. Res，1992，20（1）：59—65。