城市轨道交通网络布局的双层优化模型

陈  群¹，史  峰¹，龙科军²

(1. 中南大学 交通运输工程学院，湖南 长沙，410075；

2. 长沙理工大学 交通运输工程学院，湖南 长沙，410076)

摘  要：为了有效布设轨道交通网络，考虑可达性约束与轨道线网合理规模约束，建立了城市轨道交通网络布局优化的双层模型。该模型上层为一个多目标函数，其使得总出行时间最少，轨道交通线网总长度最少及总换乘次数最少；下层通过容量限制分配方法将客流在轨道交通线网上进行分配。算例结果表明，运用该双层模型可对所有可能的轨道交通线路进行筛选，并得到最优的线路网络布设方案。该模型可用于城市轨道交通规划中，对线路网络进行优化布局。

关键词：轨道交通；布局；双层模型；容量限制交通分配

中图分类号：U491         文献标识码：A         文章编号：1672-7207(2008)03-0623-06

Bi-level programming model for urban rail transit network’s layout

CHEN Qun1, SHI Feng1, LONG Ke-jun²

(1. School of Transport Engineering, Central South University, Changsha 410075, China;

2. School of Transport Engineering, Changsha University of Science & Technology, Changsha 410076, China)

Abstract: For effective arrangement of urban rail transit lines, considering traffic zones being divided, the accessibility constraint and the constraint of the rail transit network’s size, the bi-level programming model for urban rail transit network’s layout was set up. The upper level of this model is a multi-objective function which is to minimize the total travel time and the total rail transit lines’ length and the total transfer times, and the lower level of the model is a capacity-constrained traffic assignment model that describes passenger flow assignment on the rail transit network. The results of an illustration show that the reasonable rail transit lines can be selected from all possible lines and the optimal scheme of the rail transit network’s layout can be obtained using this bi-level programming model. This model can be used in urban rail transit’s planning for optimizing the rail transit network’s layout.

Key words: rail transit; layout; bi-level programming model; capacity-constrained traffic assignment

轨道交通是城市交通的骨干组成部分，城市轨道交通网络规划是交通规划的重中之重，是充分发挥轨道交通效率的重要技术环节^[1]。从20世纪60年代末以来，我国有20多个城市进行了轨道交通项目(预)可行性研究，上海、北京、广州、天津等城市进行了轨道交通建设实践，取得了一定成果。目前轨道交通的网络规划一般以定性为主，但为了在定性分析的同时结合定量计算，使得规划结果更加科学合理，一些研究者对轨道交通网络规划的模型与方法进行了研究。王忠强等^[2-3]应用系统分析和网络图论的方法对轨道交通路网规划的关键环节如路网合理规模、路网形态、初级路网规划方法及软件数据流图进行了探讨，采用图论和网络流理论并结合轨道交通特点，从各种不同角度对轨道网基本图式进行了研究；顾金山等^[4]提出了“枢纽锚定全网”的轨道交通网络优化理论；孙有望等^[5]对城市轨道交通网络规模、规划与城市发展的关系、规划与土地使用的相关性等提出了一些定性与定量分析方法；何宁^[6]建立了轨道线网规模与城市规模及城市结构的函数关系；王玮^[7]建立了“宏观定性控制、微观定量分析、综合评价决策”轨道线网规划布局思路。但目前人们对快速轨道交通路网规划方面的研究较少，在此，本文作者通过分析轨道交通网络的目标及客流分布规律，构建双层优化模型对轨道交通线路的布局进行优化。

1  轨道交通网络布局优化双层模型

1.1  基本假设

在规划轨道交通网络时，一方面规划者提出各种可能方案，一方面针对每个方案进行客流预测以评价方案的优劣，因此，轨道交通网络的规划可以看成是一个双层规划问题，可以建立双层规划模型。规划城市轨道交通网络时，应综合考虑城市人口和用地规模、城市现状及发展、城市形态以及地形、地质条件等，为此，要对客流量进行调查并对其需求进行分析预测。为了建立模型，先进行如下基本假定：

a. 首先按城市行政区域划分、土地性质及地形等合理划分交通区域，选择需以轨道交通线路连接的主要交通区域，并预测各主要交通区域之间的现状与未来客流分布。

b. 不考虑具体的轨道交通站点，假设轨道线路和每个交通区域相交的交线中间位置为计算点(如两交通区域之间轨道线路距离计算等)。

c. 不具体考虑乘客从出发地到轨道站点或从轨道站点到目的地的步行、公交接驳、小汽车接驳或自行车接驳等的时间。

d. 轨道交通线路之间的平均换乘时间可在调查、预测及换乘设计一般要求的基础上事先假定1个或几个平均值。

e. 事先经分析讨论并结合可实施条件等初步拟定若干条备选线路，通过优化模型在此备选线路集中选择最合理的线路组合成轨道交通线路网络。这种思路也符合规划设计的一般思路：先定性再定量，定性与定量相结合的规划理念与方法。

1.2  双层模型的上层目标及约束分析

1.2.1  目  标

目标Ⅰ：使总的轨道交通出行时间最少，即

目标Ⅱ：使总的轨道交通线路长度最小以便尽可能获得最大的效益，即

目标Ⅲ：总的换乘次数最少，即

多目标规划模型求解方法很多，包括约束法、分层序列法、功效系数法、评价函数法等^[8-9]。假设采用线性加权方法，则3个目标可表示成

1.2.2  约  束

考虑轨道交通线路合理规模约束、可达性约束(可达性指通过轨道交通任意2个主要交通区域之间的可达性)。

Ⅰ. 轨道交通线路合理规模约束：

Ⅱ. 任意两主要交通区域之间可达性约束：

1.3  双层模型的下层问题分析

下层表示客流在轨道交通网络上的分配(对于线路之间的换乘考虑换乘时间惩罚)。参照常规公交出行路径搜索优先级别^{[7, 10]}，可假设轨道交通出行路径搜索的优先级别也为：直达→1次换乘→…→n次换乘。对与轨道交通方式出行，可以明确2点：

a. 轨道交通线路一般运行时间较稳定，因此，对于出行者(特别是对于通勤出行)，通过轨道交通的各种出行路径的出行时间在出行前基本能事先预知；

b. 出行时间一般仅与轨道交通发车频率相关，而与乘坐轨道交通的乘客数基本没有关系，因此，在不考虑乘客乘坐舒适性的前提下，轨道交通阻抗可取比较稳定的值(与线路乘客数量关系不大)。

可见，对于某一优先级别下出行路径的选择，出行者的出行选择可认为是：首选以最快捷的路径(或综合考虑时间、费用等交通阻抗值最小的线路)出行，称为最短路因素。同时，在实际运营中，由于轨道交通线路的运力有限会使乘客无法选择那些直达但异常拥挤的线路，而不得不选择次优线路或选择换乘线路。

综合上面分析，可选用容量限制分配方法，并可认为轨道交通出行者出行路径选择如下：首先的选择直达→1次换乘→2 次换乘(假设最多2次换乘)；然后在同一优先级别下首选最短路；只有在某一线路容量达到饱和时才考虑次优线路。采用容量限制分配模型分配轨道交通出行量时，需将轨道出行 OD总表分解为k 个 OD分表分 k 次增量加载分配。图1所示为容量限制分配法逻辑框图。

图1  容量限制分配法逻辑框图

Fig.1  Logic flow diagram of capacity-constrained traffic assignment

1.4  轨道交通出行路径确定方法

模型求解的一个关键问题是轨道交通出行路径的确定。

1.4.1  直达路径的确定

① 取起点所在交通区域i所连接的轨道交通线路L₁。

② 线路L₁是否经过出行终点所在交通区域j，若不过，则依次返回步骤①；若经过，则转入下一步。

③ 计算线路L₁上i的顺序号X_i；计算线路L₁上j的顺序号X_j。

④ 计算S=L(X_i, X_j)，并记录路径。

⑤ 若交通区域i还有连接线路，则转入步骤①；否则，结束。

1.4.2  一次换乘轨道交通出行路径的确定

① 取起点所在交通区域i所连接的轨道交通线路L₁。

② 取与线路L₁所相交(或可换乘)的轨道交通线路L₂。

③ 线路L₂是否经过出行终点所在交通区域j，若不过，则依次返回步骤②和①；若过，则转入下一步。

④ 计算线路L₁上i的顺序号X_i；计算线路L₂上j的顺序号X_j。

⑤ 计算L₁与L₂的交点B_D(即换乘点)；计算线路距离L(X_i，B_D)，L(B_D，X_j)。

⑥ 计算S=L(X_i，B_D)+L(B_D，X_j)，并记录路径。

⑦ 若还有交点未算完，则转入步骤⑤；若还有L₁的相交线路，则转入步骤②；若交通区域i还有连接线路，则转入步骤①；否则，结束。

1.4.3  2次换乘轨道交通出行路径的确定

① 取出行起点所在交通区域i所连接的一轨道交通线路L₁。

② 取与线路L₁所相交(或可换乘)的轨道交通线路L₂。

③ 取与出行终点所在交通区域j连接的轨道交通线路L₃。

④ 搜寻线路L₃与线路L₂是否有连接(可换乘)，若没有，依次返回步骤③，②和①；若有，则转入下一步。

⑤ 计算出线路L₁上i的顺序号X_i；计算线路L₃上j的顺序号X_j。

⑥ 依次选取线路L₁与L₂的一交点B_D1，线路L₂与L₃的一交点B_D2，计算S= L_DL(X_i，B_D1)+L_DL(B_D1，B_D2)+L_DL(B_D2，X_j)；则B_D1和B_D2为2个换乘点，并记录路径。

⑦ 若还有交点未算完，则转入步骤⑥；若还有交通区域j的连接线路，则转入步骤③；若L₁还有相交线路，则转入步骤②；若交通区域i还有连接线路，则转入步骤①；否则，结束。

确定轨道交通出行路径之后，又已知其一般行驶速度和换乘次数与地点，故能求得旅行时间。

2  模型的求解算法

上层模型是有约束的0-1规划模型，遗传算法采用0-1编码时可求解此类问题^[11-12]。

2.1  变量编码

采用0-1编码，假设备选轨道线路有n条，代码依次为1，2，…，n，则染色体长度为n：

[0，1，1，0，…，0，0，1]。

n

其中：“1”表示选择该线路，“0”表示该轨道线路不在选择之列。

2.2  适应度函数

为了对式(4)进行最小优化，可取F(i)=C_max-O(i)。其中，F(i)为第i个个体的适应度，C_max为估计的目标函数最大值；O(i)为第i个个体的目标函数值。

2.3  约束处理

    约束处理的目的是要让可行解获得1个理想的适应值，从而被选择进入下一代群体的可能性大。因此，可直接指定合理的选择策略，从中选取合乎要求的个体，这样就代替了罚函数的作用。从群体中随机挑选2个个体，首先判断个体是否为可行解，若是可行解，则计算其适应值；若不是，则计算其超出约束的程度，然后按下面规则进行比较：

a. 可行解之间适应值大的个体以更大概率进入下一代；

b. 可行解与不可行解比较时，可行解以更大概率进入下一代；

c. 不可行解之间比较时，超出约束程度小的以更大概率进入下一代。

对于式(4)中约束Ⅰ(式(5))超出程度比较明确；但对于约束Ⅱ(式(6))超出程度则可以2次换乘以内(包括直达、1次换乘、2次换乘)未完成的总的OD量为根据，未完成的越多超出程度越大。

2.4  遗传操作

2.4.1  选  择

采用基于排名的轮盘式选择算子。对所有待选个体，首先将可行解按适应值由高到低排在前面，不可行解按超出约束程度由小到大继续往后排。第i个个体的生存概率C(i)为

2.4.2  交  叉

设定交叉概率P_c，实行单点交叉操作产生新个体。

2.4.3  变  异

按变异概率选取染色体的某个位置实行变异，该位置是0的变成1，是1的变成0。

2.5  算法流程

运用遗传算法进行模型优化求解，其算法流程  如下。

步骤1  初始化。设定种群数目M、染色体长度l、迭代总代数g_{en max}、交叉概率P_c、变异概率P_m。

步骤2  采用0-1编码，随机产生初始种群，置迭代次数g_en=1。

步骤3  将上层种群中各染色体对应的解代入下层规划求解，可利用容量限制分配方法得到每组OD对应的出行路径选择，然后，返回上层，计算每个个体的适应度及超出约束的程度(若是可行解个体，则其超出约束程度为0)。若迭代次数g_en=g_{en max}，则输出最佳个体，否则，转步骤4。

步骤4  采用基于排名的轮盘式选择算子，复制选择下一代种群。

步骤 5  根据交叉概率P_c，执行交叉操作。

步骤6  根据变异概率P_m，执行变异操作，令g_en=g_en+1，从而得到新种群，并转步骤3。

3  示  例

某城市拟规划建设轨道交通网络，经分析论证，以轨道交通连接6个主要交通区域。图2中，三角形符号表示为交通区域，线段上数值表示轨道交通连接时行车时间。假设仅考虑轨道交通行车时间及换乘时间(假设1次换乘时间均为2 min)，且仅对目标Ⅰ(总的轨道交通出行时间最少)进行考虑。

已知各边长度：

A₁—A₄：4 km；A₄—A₅：6 km；A₅—A₆：6 km；A₆—A₂：6 km；A₁—A₂：6 km；A₁—A₃：6 km；A₂—A₃：4 km；A₃—A₆：4 km；A₃—A₄：4 km；A₃—A₅：4 km。

图2  交通区域分布

Fig.2  Distribution of traffic zones

假设有备选轨道线路为：

a. A₁—A₃—A₆；

b. A₁—A₄—A₃—A₆；

c. A₄—A₅—A₆—A₂；

d. A₁—A₄—A₅—A₆；

e. A₂—A₃—A₅。

假设根据城市规模等条件论证得到：规划轨道交通线路总长度不宜超过28 km，且每条轨道线路单方向容量均为2万人/h；假设各交通区域间客流出行OD分布见表1。

表1  各交通区域之间出行OD对流量分布

Table 1  Traffic volume of OD pairs between traffic zones

运用所提出的模型及求解方法，编码采用0-1编码，染色体长度为5(即备选轨道线路条数)，种群数取150，交叉率取0.7，变异率取0.05，通过MATLAB编程，运行15代可得到最优轨道线路：A₁—A₄—    A₃—A₆；A₂—A₃—A₅。

由于表1中OD分布为对称分布，所以，线路断面流量2个方向相等，单方向断面流量如表2所示。

表2  轨道线路断面流量

Table 2  Results of routes’ section passenger flow vo

4  结  论

a. 以总的出行时间最少、轨道交通线网总长度最小及总的换乘次数最少为优化目标，并考虑可达性约束与轨道线网合理规模约束条件，建立了城市轨道交通网络布局优化的优化模型。该优化模型呈双层形式：上层为多目标优化函数，下层为容量限制分配法模型。该模型描述了客流在轨道交通线网上的分布规律。

b. 运用所建双层模型可对现实中所有可能的轨道交通线路进行筛选，以得到合理的线路网络布设方案。所建模型为轨道交通网络的规划提供了理论依据。

参考文献：

[1] 吴小萍, 陈秀方. 城市轨道交通网络规划理论方法研究进展[J]. 中国铁道科学, 2003, 24(6): 111-117.
WU Xiao-ping, CHEN Xiu-fang. Progress of study on urban mass transit network planning theory and methodology[J]. China Railway Science, 2003, 24(6): 111-117.

[2] 王忠强, 高世廉, 陈金琦. 轨道交通路网规划若干问题探讨[J]. 西南交通大学学报, 1999, 34(3): 369-373.
WANG Zhong-qiang, GAO Shi-lian, CHEN Jin-qi. Discussions on network planning of urban rail transit[J]. Journal of Southwest Jiaotong University, 1999, 34(3): 369-373.

[3] 王忠强, 黎青松, 陆旭梅. 轨道交通路网基本图式研究[J]. 西南交通大学学报, 2000, 35(3): 288-292.
WANG Zhong-qiang, LI Qing-song, LU Xu-mei. Research on fundamental pattern of urban rail transit network[J]. Journal of Southwest Jiaotong University, 2000, 35(3): 288-292.

[4] 顾金山, 顾宝根, 王家玮. 上海市轨道交通网络优化方案说明报告[R]. 上海: 上海市建委轨道交通网络优化课题组, 2000.
GU Jin-shan, GU Bao-geng, WANG Jia-wei. Report of Shanghai’s rail transit network optimization scheme[R]. Shanghai: Rail Transit Network Optimization Project Group of Shanghai Construction Commission, 2000.

[5] 孙有望, 李云清, 王 祥. 城市轨道交通网络规划的优化[J]. 上海交通大学学报, 2000, 34(增): 52-55.
SUN You-wang, LI Yun-qing, WANG Xiang. Planning and building of urban rail traffic network[J]. Journal of Shanghai Jiaotong University, 2000, 34(Suppl): 52-55.

[6] 何 宁. 城市快速轨道交通规划系统分析[D]. 上海: 同济大学城市轨道与铁道工程系, 1996.

HE Ning. Systemic analysis of urban rail transit planning[D]. Shanghai: Urban Rail Transit and Railway Engineering Department, Tongji University, 1996.

[7] 王 炜. 城市公共交通系统规划方法与管理技术[M]. 北京: 科学出版社, 2002.
WANG Wei. Planning method and management technique for urban public transportation system[M]. Beijing: Science Press, 2002.

[8] 毛保华. 城市轨道交通[M]. 北京: 科学出版社, 2001.
MAO Bao-hua. Urban rail transit[M]. Beijing: Science Press, 2001.

[9] 钱颂迪. 运筹学(修订版)[M]. 北京: 清华大学出版社, 1990.
QIAN Song-di. Operation research[M]. Beijing: Tsinghua University Press, 1990.

[10] 冯树民, 陈洪仁, 邹成伟. 公共交通客流分配方法研究[J]. 哈尔滨建筑大学学报, 2002, 35(5): 127-130.
FENG Shu-min, CHEN Hong-ren, ZOU Cheng-wei. Assignment of public transportation passenger flows[J]. Journal of Harbin University of Civil Engineering and Architecture, 2002, 35(5): 127-130.

[11] 晏克非, 陈 群. 基于遗传算法的停车诱导系统中信息显示设施定位研究[J]. 土木工程学报, 2006, 39(7): 104-108.
YAN Ke-fei, CHEN Qun. Location of sign boards in a parking guidance information based on genetic algorithm[J]. China Civil Engineering Journal, 2006, 39(7): 104-108.

[12] 王小平, 曹立明. 遗传算法——理论、应用与软件实现[M]. 西安: 西安交通大学出版社, 2002.
WANG Xiao-ping, CAO Li-ming. Heredity algorithm: Theory, application and software implementation[M]. Xi’an: Xi’an Jiaotong University Press, 2002.

收稿日期：2007-06-29；修回日期：2007-09-08

基金项目：国家自然科学基金资助项目(50608010)；教育部高等学校博士学科点专项科研基金资助项目(20070533111)；中南大学博士后科学基金资助项目(2007年)

通信作者：陈  群(1977-)，男，江西九江人，博士后，讲师，从事城市交通规划工作；电话：13548679364；E-mail: chenqun631@163.com