基于节点备选集的城市轨道线网规划模型与算法

郭建民，李虎，门燕青，潘春雨

济南轨道交通集团有限公司，山东 济南 250014

0 引言

城市轨道交通对缓解城市交通拥堵、提升城市品质与竞争力、推动城市的可持续发展具有重要作用。特别是随着国家新型城镇化战略的推进，轨道交通对实现交通、产业与空间的协调发展发挥积极引领与推动作用，作为指导轨道交通建设的线网规划成为国内外研究的热点问题。

城市轨道交通线网规划是城市总体规划的强制性内容，也是城市轨道交通建设的前提和依据。做好轨道交通线网规划，对引领城市发展、优化城市空间结构、实现交通与用地的协调发展具有重要意义。同时，合理的线网规划方案也能有效缓解城市交通拥堵，提升城市交通发展的承载力，研究城市轨道交通线网规划问题具有重要的理论和现实意义。Bruno等[1]提出了轨道交通单线路布设模型和基于非劣解集的K-最短路算法，Montis等[2]、Rocha[3]、Roth等[4]将复杂网络理论用于铁路网、航空网络等规划，Gendreau等[5]提出线网规划布局的移动网格法模型，刘灿齐等[6]提出轨道交通虚拟线网模型，郭孜政等[7]等建立了基于客流场强、以覆盖最大相关性客流为目标的线网规划模型，高世廉[8]、王忠强等[9]、金键等[10]提出了基于客流分析的线网规划集散点法、主出行路径法及出行向量法等，黄超等[11]提出了基于网络演化方法的城际铁路网规划模型，杜胜品等[12]、李文博[13]提出基于绿色交通以及定性分析为主的轨道交通线网规划方法；方恒堃[14]研究了多元数据在北京轨道交通线网规划中的应用；冷海洋等[15]、马小毅[16]从功能定位、服务范围、规模、布局思路等探讨了Ⅰ型大城市的城市轨道交通线网规划思路及目标；吕颖[17]、张云娇[18]分析了基于出行时间最小的规划布局方法及城市轨道交通层次划分；李岩辉[19]提出未来线网优化思路并给出某城市轨道交通线网规划优化方案；王周扬[20]对轨道交通线网规划的设计原则、思路、方法以及空间结构等进行分析；姚智胜等[21]研究了轨道交通发展战略规划、线网功能层次与组织、中心地区既有线网提升、区域快线规划、副中心线网规划5个线网规划所面临的关键问题；袁江[22]、蒋文[23]对城市域轨道交通线网基本构架进行评价分析。

既有研究在线网规划阶段未考虑单条线路运营效率的影响，若线路单向运营时间超过1 h，运营效率将大大降低；既有研究未考虑轨道交通的建设成本因素，若轨道交通网络规模过大，将给所在城市带来较大的经济负担，难以实现轨道交通的可持续发展；既有研究对既定的点线关系考虑较少，致使本应规划在同一条线路中的客流集散点分散在不同的线路中，需换乘才能实现相互之间的连通。

本文在分析轨道交通线网规划影响因素的前提下，考虑客流、经济、产业及政治因素，提取特质因子，构建节点备选集合信息，以直达客流量最大为目标，构建轨道交通线网规划模型，并根据模型特点求解，为轨道交通线网规划阶段方案的制定寻求定量化支撑。

1 线网规划影响因素

影响轨道交通线网布局的因素很多，宏观方面，轨道交通线网服从于城市总体规划和城市综合交通规划等宏观规划；微观方面，轨道交通线网布局受交通需求、工程水文地质、土地利用、产业发展、建设成本等因素影响。在满足水文地质等工程条件下，对线网布局产生重要影响的因素为直达客流、线路数量、线路长度和建设成本，将其称为轨道交通线网规划布局的特质因子。

1)直达客流 客流是影响轨道交通线网布局的决定性因素之一，客流预测是确定线网规模、运输能力、车站规模以及运营组织等的重要依据。直达客流是评价线网规划的重要指标，所占比例越高，换乘量越小，线网运行效率越高。

2)线路数量 线路数量是决定建设成本的重要因素，也是考验城市经济实力的重要指标。线路数量既包括轨道交通线路总条数，也包括通过某一节点的线路总数量。

3)线路长度 线路长度包括线网总规模和单条线路的长度，既与城市规模和形态有关，又深刻影响着轨道交通运营方式和运营效率。

4)建设成本 轨道交通投资巨大，控制好轨道交通的建设成本对实现轨道交通的可持续发展具有重要作用。

2 线网规划模型

基于3个基本假设建立模型：1)城市中重要客流集散点的位置已经确定；2)轨道交通每条线路建设的固定成本均相同；3)已知轨道交通建设预算成本。

2.1 参数定义

2.1.1 参数

N为网络中节点的集合；i、j分别为网络中的任意节点，满足i、j∈N；qij为节点i、j的客流量，人/h；lij为节点i、j的距离，km；cij为节点i、j的单位建设成本，亿元/km；K为轨道交通线路的集合；k为轨道交通线路集合中的一条线路，k∈K；fk为线路k的固定建设成本，亿元；L为单条轨道线路的最大长度，km；πmax为通过节点的最大线路数；γmax为城市中轨道交通最大线路数，γmax由城市的客流量、城市空间布局综合确定；M为一充分大的正数。

2.1.2 决策变量

yk为0-1变量，表示轨道交通线网中是否包含线路k，如果包含线路k,则yk=1，否则yk=0。

2.2 规划模型函数

轨道交通线路的规划与设计，应充分考虑客流与城市空间布局因素，结合城市的发展战略及城市产业的发展，综合确定城市轨道交通线网的架构。同时，轨道交通作为大运量的公共交通，应串联主要的客流集散点，为交通方式结构转型提供强有力支撑。依托于主要客流集散点，以轨道交通线网直达客流量最大为优化目标，构建轨道交通线网规划模型的目标函数，表示轨道交通网络的直达客流量最大化

(1)

约束函数分别为：

(2)

(3)

(4)

(5)

(6)

(7)

(8)

式(2)为节点的线路数量约束，每个节点i至少有1条轨道交通线路；式(3)为决策变量的连锁关系约束，即当节点j在轨道交通线路k上时，则轨道交通线网中包含线路k；式(4)为轨道交通总费用约束，即轨道交通线网的建设成本小于预算Tc；式(5)为轨道交通线路总数量约束；式(6)为轨道交通线路的长度约束；式(7)为通过节点的最大线路约束；式(8)为决策变量的逻辑约束。

2.3 节点备选集合构建

综合考虑客流、经济、产业及政治等因素，并与现实情况充分衔接，同时有效降低模型的求解规模，采用节点备选集合方法，解决部分节点与线路的匹配关系。重点针对大型客流集散节点构建节点备选集合，例如对外交通枢纽、景区出入口、公共服务设施出入口等。

节点备选集合的构建有2种方式：一是根据2点间的直达客流量确定节点的备选集合，选取网络中的部分节点，分析该节点与网络中其他节点的上行、下行直达客流量，将直达客流量位居前两位的直接纳入该节点的备选集合；二是根据特殊因素确定的节点备选集合。基于产业、经济与政治等特殊因素，选取网络中的部分节点如商务中心、政务中心等，纳入节点备选集合，在线网规划中，该节点必须与备选集合中的节点位于同一条线路中。

3 求解算法

图1 抗体结构图

本文构建的轨道交通线网规划模型为决策变量为0-1的整数问题，综合考虑各种智能优化算法的特点及模型求解时间等多种因素，采用免疫克隆算法进行求解。

3.1 抗体结构

模型的决策变量为0-1变量，抗体采用0-1编码。由于决策变量间存在相互关联、相互影响的关系，在此采用的抗体结构如图1所示。

3.2 变异策略

变异是免疫克隆算法的核心步骤，变异策略直接影响算法的求解效率，此处采用多变异策略。

变异策略一：交换策略。随机生成2组不相同的随机数r1，r2∈[0，N]，交换此随机数的相关基因，增加抗体的多样性，具体操作如图2所示。

图2 基因交换策略

变异策略二：随机变异策略。随机生成随机数r1∈[0，γmax]，且满足yr1=1，随机生成随机数r2∈[0，N]，将对应的r1行、r2列的基因进行随机变异操作，具体操作如图3所示。

图3 随机变异操作

3.3 计算步骤

抗体及变异策略定义完成后，采用免疫克隆算法分5步进行计算。

1)设置免疫克隆算法的最大迭代数Nmax和抗体数n，定义变异概率β，考虑模型的相关约束，采用随机生成策略生成n个抗体。该抗体集合主要有记忆细胞S和剩余细胞Pr组成。

2)将式(1)作为抗体的亲和度函数，并按照抗体亲和度由大至小的顺序进行排序，将前n个抗体亲和度高的抗体放入S中，同时对n个抗体进行克隆复制，采用的规则为：

ni=round (βn/i)，

式中：ni为第i个抗体的克隆个数，round(·)为向下取整函数。

3)将克隆后的na个抗体采用多变异策略进行变异操作，随机数var Value ∈[0,1]，若var Value≤0.6，采用交换策略，否则采用随机变异策略。

4)计算变异后na个抗体的亲和度并排序，如果抗体亲和度优于S中的所有抗体，则将该抗体放入S细胞，同时将Pr亲和度较低的抗体替换为na个抗体中亲和度较高的抗体。

5)判断是否达到Nmax，如果达到Nmax则算法终止，从S中选择最优抗体作为输出；否则转至步骤2)。

图4 算例测试网络

4 算例分析

为验证模型及算法的有效性，以某城市的主要客流集散点为例，对网络进行模型及算法的测试，如图4所示。

部分节点之间直达客流量较低，只给出部分客流量较大的数据，具体参数如表1所示。

表1 部分节点间的直达客流量

根据备选集合的构建策略，选取网络中位置相对重要的3个节点a、i和d，构建其节点备选集合。根据客流量及特殊因素的考虑，确定a、i、d的备选集合分别为{b，h}、{j，b}、{h，a，f}。

图5 轨道交通线网布局

假设每条线路的固定建设费用为20亿元，根据预测的城市总客流量确定该城市最多建设4条轨道，轨道交通的造价为5.5亿元/km，预算总造价为80亿元。已知轨道交通单程最长运营时间约为1 h，按照轨道交通平均运营速度为35 km/h，单条轨道线的最大长度为35 km，设置节点的πmax=3，M=10 000，利用免疫克隆算法计算，设置种群N=30，β=0.3，计算得到最优目标为58 900 人/h。轨道交通线网布局如图5所示。

通过轨道交通网络架构分析可知，该线网是由勺型环线和放射线路构成的“环形+放射”式轨道交通网络架构，有利于疏解城市边缘区的高强度客流，减少对城市中心的过度干扰，同时环形线路有利于加强轨道线路间的联系，有效提升乘客换乘的便利性。

5 结语

本研究运用轨道交通线网规划理论和思想，综合考虑直达客流、线路数量、建设成本、线路长度等特质因子的影响，以直达客流最优为目标，设计了城市轨道交通线网规划模型与算法，探讨轨道交通线网规划布局，案例分析得到了合理的规划方案，说明该模型与算法具有一定的科学性和适用性，能够为现实中城市轨道交通线网规划编制提供较好的参考价值。模型没有考虑道路规划、工程地质、文物保护等因素的影响，也是下一步需要继续深入研究之处。