基于出行效率提升的公共交通线网优化研究*

揭远朋 冯雪松 解振全 刘 异 朱晓静

(北京交通大学城市交通复杂系统理论与技术教育部重点实验室1) 北京 100044)(北京交通大学交通运输学院2) 北京 100044)(中铁第四勘察设计院集团有限公司线路站场设计研究处3) 武汉 430063)

0 引 言

城市公共交通的网络布局会影响居民出行对公共交通的选择，也制约着城市公共交通系统功能的发挥和城市经济的发展.

国外学者近些年以提升乘客公共交通出行的整体效率为目标，在优化公共交通线网的过程中尽可能减少乘客公共交通出行的总时耗和换乘次数.Fan等[1]以减少乘客公共交通出行时间和换乘次数为目标，并提出使用爬山法和模拟退火这两种元启发式算法优化公共交通线网.Nikolich等[2]进一步完善数学模型，他们在研究中考虑了不能满足运载的公共交通出行，并给这些不能满足运载的公共交通出行一个较大的惩罚时间.Nayeem等[3]也使用了和相同的数学模型，不同的是该研究提出了基于精英保留策略的遗产算法对模型进行求解.结果表明，该研究使用的算法相比以往的算法能得到更好的优化效果，并节约了计算时间.Zhao等[4]提出的优化模型不仅考虑了公交换乘和不能满足运载的公交出行，还考虑乘客的等待时间.该研究的优化结果不仅确定了各条公交线路的走向，同时还确定了各条公交线路上公交车辆的发车频率.国内学者主要通过不同的目标对公共交通线网的优化设计进行研究.于滨等[5]提出了上层模型以直达客流密度最大为目标的公交线网双层优化模型.该优化模型考虑公交线网的变化对乘客出行行为的影响，并在下层模型中对公交客流进行再分配.周媛等[6]从乘客利益、企业效益及社会环境的角度出发，以公共交通效率最大化为总目标，建立公交线网优化模型，并提出基于遗传禁忌算法的公交线网优化算法.俞礼军等[7]设计的最优模型解决现有公交线网优化求解算法中存在的很少考虑相邻线路的换乘和求解出的不同线路有大量站点重复等问题.

现有研究成果在优化设计城市公共交通线网的过程中一般先将公共交通系统抽象成为一个数学模型，然后运用相应的算法对问题进行求解[8-10].本文也采用相同的研究思路，从乘客出行的角度出发，以乘客出行对公共交通的需求为依据,以减少乘客出行的总时耗为目标，构造城市公共交通线网的优化模型，并对研究区域的现状公交线网进行优化调整，以提高研究区域内乘客公共交通出行的整体效率.

1 建立模型

1.1 基本假设

本文构建城市公共交通线网优化模型的基本假设如下：①公共交通线网上任意两个站点间的乘客出行需求不变；②公共交通线网各线路上运力供给可满足相应的出行需求；③公共交通线网上任意相邻可连接的两个站点间的在车旅行时间不变；④公共交通线网上任意两个站点间的乘客在考虑换乘时间的情况下，都选择两个站点之间耗时最少的出行路径；⑤优化前后公共交通线网上站点数量和线路条数不变[11-17].

设公共交通线网为G={N,L}.式中：N为公共交通线网中站点的集合；L为连接两个相邻可连接站点的路段；R为公共交通线网上初始线路集合；qod为站点o与站点q之间的公共交通出行量，站点o为乘客公共交通出行的起点，站点q为乘客公共交通出行的终点，乘客在站点o与站点q之间的出行路径为pathod，则

(1)

(2)

(3)

1.2 公共交通出行的换乘时间

将站点o与站点d之间时耗最少的出行路径记为Dpathod，站点o与站点d之间乘客选择Dpathod出行过程中乘坐线路的条数记为σod.若σod=0，表示站点o与站点d之间没有出行路径，即公共交通线网上站点o与站点d不可连通，σod的计算见式(4).根据乘客出行过程中乘坐线路的条数σod，可计算站点o与站点d之间乘客选择时耗最少的路径Dpathod出行的换乘次数δod，δod的计算见式(5).

(4)

δod=σod-1

(5)

在目标函数中计算乘客出行总时耗时，本文只统计换乘次数不超过两次的公共交通出行的在车旅行时间和换乘时间，则若δod≤2，记Δod=1；若δod>2，记Δod=0，见式(6).如果两个站点之间时耗最少的出行路径的换乘次数超过两次，本文会给在这两个站点之间的公共交通出行一个较大的惩罚时间ω1.根据以往的研究，取ω1为100.00 min加上公共交通线网上所有乘客以最短路径直达出行的平均时耗.则若δod>2，记▽od=1；若δod≤2，记▽od=0，见式(7).

(6)

(7)

公共交通出行中途换乘时，乘客需要下车步行到换乘站点并等待公共交通车辆，因此本文将乘客公共交通出行一次换乘的平均时间考虑为由一次换乘平均走行时间和一次换乘平均等待时间构成.公共交通线网上所有不超过两次换乘的公共交通出行的总换乘时间记为TTR1，TTR1的计算见式(8).公共交通线网上所有超过两次换乘的公共交通出行的总惩罚时间记为TTR2，TTR2的计算见式(9).

TTR1=(tw+tc)∑o,d∈NqodδodΔod∀o,d∈N

(8)

TTR2=ω1∑o,d∈Nqodod∀o,d∈N

(9)

式中：tw为公共交通线网上公共交通出行一次换乘的平均走行时间，min；tc为公共交通线网上公共交通出行一次换乘的平均等车时间，min.

1.3 公共交通出行的在车旅行时间

站点o与站点d之间的乘客选择时耗最少的路径Dpathod出行的在车旅行时间记为tod，为

(10)

式中：tij为相邻可连接站点i与站点j之间的在车旅行时间，min.

公共交通线网上所有不超过两次换乘的公共交通出行的总在车旅行时间记为TIV，为

TIV=∑o,d∈NqodtodΔod∀o,d∈N

(11)

1.4 目标函数

本文以公共交通线网上所有乘客出行的总时耗最小为目标构造城市公共交通线网优化模型的目标函数，为

minT=TIV+TTR1+TTR2

(12)

(13)

(14)

式中：T为公共交通线网上所有乘客的出行总时耗，分钟；Q为公共交通线网上公共交通出行总量，人次.

式(12)为优化模型的目标函数，表示公共交通线网上乘客出行的总时耗最少；式(13)为公共交通线网上任意两个站点间可有路径出行，即公共交通线网在优化后各个站点可连通；式(14)为公共交通线网上所有站点间的出行需求量之和为公共交通线网上的出行总量.

2 算法设计

2.1 遗传算法操作方式

1) 编码 根据城市公共交通线网优化问题的特征，本文采用实数编码的形式，先将公共交通线网上所有初始线路的站点数字编号串在一起，相异线路的数字编号组用0隔开.每条线路的数字编号组可以当作一个基因片段，将所有的线路组在一起可以构成一个个体，一个个体代表一个公共交通线网方案.假设个体的基因序号为12 9 4 15 8 5 0 13 6 8 14 0 1 10 3 5 14 0 4 11 2 7 10 1，则表示该公共交通线网有4条线路，第一条线路途径站点的数字编号为12 9 4 15 8 5，第二条线路途径站点的数字编号为13 6 8 14，第三条线路途径站点的数字编号为1 10 3 5 14，第四条线路途径站点的数字编号为4 11 2 7 10 1.

2) 初始种群生成 本文先将研究区域现状的公共交通线路进行编码，然后构成一个初始个体.如果种群的个体规模为N，将初始个体复制N次，这N个相同的个体构成本文遗传算法所需的初始种群.

3) 选择 选择是从旧群体中以一定概率选择优良个体组成新种群，新种群通过繁殖得到下一代个体，本文使用轮赌盘法进行选择操作.轮赌盘法是一种放回式随机采样方法，每个个体被选择进入下一代的概率等于该个体的适应度值占整个种群中个体适应度值和的比例，个体的适应度值越高，该个体被选择的概率就越大，进入下一代的概率就越大.假设在M个体中第m个个体的适应度值为Fm，则个体被选择概率pm为

(15)

式中：Fi为种群中第i个体的适应度值，i=1、2…M.

本文以优化模型目标函数值的倒数作为适应度函数来计算种群中个体的适应度值，假设种群中第m个个体的适应度值为Fm，则Fm表示在第m个个体所代表的公共交通线网上所有乘客出行总时耗的倒数.

4) 交叉 将种群中选出的个体进行两两交叉，第一个个体与第二个个体进行交叉，第三个个体与第四个个体进行交叉，依此类推.如果选择出来的个体数量为奇数，则最后一个个体不进行交叉运算.为了使交叉后公共交通线网上每条线路的各站点间可连通，父个体和母个体在交叉过程会交换整条线路，不进行线路中单个站点的交叉.

交叉的原则是首先确实一个交叉概率Pc，然后遍历父个体或者母个体每个基因片段，并给每个基因片段一个在[0，1]区间均匀分布的随机数Rc.若Rc≤Pc，则父个体和母个体该位置的基因片段进行交叉运算；若Rc>Pc，则父个体和母个体该位置的基因片段不进行交叉运算.为了尽可能实现单点交叉，即父个体和母个体在交叉运算过程中只交换一个基因片段，本文取交叉概率Pc=1/R，R为个体中基因片段的个数.

5) 变异 由于初始种群的所有个体都相同，遗传算法在第一次迭代变异之前所执行的交叉运算并不能改变种群中各个体的基因序号，只有第一次迭代中的变异过程才能使种群中的个体发生改变.本文以个体中基因片段代表的线路所途径站点中两两站点间OD(origin destination)交通量之和的倒数为适应度值，根据基因片段适应度值的大小，以轮赌盘法选择出一个基因片段所代表的线路进行变异操作.首先确定变异概率值Pm，并遍历从种群中选出的每个个体，并给定每个个体一个[0 1]区间内均匀分布的随机数Rm.若Rm≤Pm，则该个体进行线路变异；若Rm>Pm，则该个体进行站点变异.

①线路变异方式 首先确定一个概率分界值Pl，然后给定所选出的基因片段一个[0，1]区间内均匀分布的随机数Rl.若Rl≤Pl，则进行线路整体变化；若Rl>Pl，则进行线路部分变化.

线路整体变化 在{0,1}集合中随机选择一个元素k，若k=0，则保留线路首站；若k=1，则保留线路末站.然后将保留下的站点作为一个端点，根据该端点与公共交通线网上其他站点之间的最短路径所途径站点中两两站点间的OD交通量之和的大小，以轮赌盘法选择出另一个端点，并以两个端点间的最短路径作为变化后的线路.

线路部分变化 除该基因片段所代表的线路首末站外，将线路中其他站点的编号形成一个站点集合，并在站点集合中随机选出两个站点编号，然后这两个站点之间的最短路径替换线路该两个站点之间现有的路径.

②站点变异方式 首先确定一个概率分界值Pt，然后给定选出的基因片段一个[0，1]区间内均匀分布的随机数Rt.若Rt≤Pt，则在线路上增加或删除站点；若Rt>Pt，则在线路上替换中间站点.

增加或删除站点 在{0,1}集合中随机选择一个元素k，若k=0，则选择线路的首站；若k=1，则选择线路的末站.然后确定一个概率分界值Pd，并给定选出的基因片段一个[0 1]区间内均匀分布的随机数Rd.若Rd≤Pd，则删除所选择的站点；若Rd>Pd，则在所选择的站点外延伸一个站点，延伸的这个站点要能与选择的该线路的首站或者末站相邻可连接.

替换中间站点 以基因片段所代表的线路的中间站点到该线路其他站点OD交通量之和的倒数为适应度值，根据基因片段适应度值的大小，以轮赌盘法选择一个中间站点进行替换.替换的新站点必须与线路该位置前后两个站点相邻可连接.

2.2 流程设计

本文基于遗传算法设计求解城市公共交通线网优化模型的算法，算法的流程见图1.

图1 公共交通线网优化的算法流程

3 案例分析

本文以我国某新兴城市化区域X为研究范围，以X境内的现状公交线网为研究对象.X境内的现状公交线网有39条公交线路，该39条公交线路共途径344个不同的公交站点和458个不同的路段.本文以2016年3月21日X境内的公交出行OD交通量为研究数据，运用所设计的城市公共交通线网优化模型和求解算法对X境内的现状公交线网进行优化调整.为了比较通过本文设计的优化模型优化后的公交线网相比初始公交线网是否更能方便乘客出行，是否提高了乘客的整体出行效率，本文设定了5个指标对公交线网进行评价.该五个指标分别为直达公交出行比例、1次换乘公交出行比例、两次换乘公交出行比例、2次以上换乘公交出行比例和一次公交出行平均时间.本文使用C++语言编写模型和算法的程序然后进行优化求解，其中求解算法中各参数值的选取见表1.

表1 遗传算法中各参数的值

根据2016年3月21日X境内乘客公交出行IC(Intelligent Card)卡刷卡记录数据统计，X境内公交线网上所有乘客1次公交换乘花费的平均走行时间与平均等车时间之和取约为10.00 min.据此，X境内公交线网优化前后5个评价指标的计算结果对比见表2.

表2 公交线网换乘时间为变量的优化结果 %

由表2可知，相比于X境内的初始公交线交线网，优化后公交线网的直达的公交出行比例虽减少了约4.01%，但仅需一次换乘的公交出行比例增加了两倍有余；与此同时，需两次换乘的公交出行比例减少了约88.18%，且需要两次以上换乘的公交出行完全消失.优化后的公交线网减少了换乘次数过多的公交出行和时间过长的公交换乘.X境内一日公交出行交通量总数约为7.57万人次，他们在优化后的公交线网上一次公交出行的平均时间减少了约3.40%，整个公交线网上所有乘客的总出行时耗节省超过5.00×104min.通过综合比较分析可以得知，本文以换乘时间为变量的公共交通线网优化模型对X境内的公交线网进行优化调整，可以减少须多次换乘的公交出行比例，减少公交线网所有乘客的出行总时耗，提高乘客的整体出行效率.

4 结 论

1) 本文提出的城市公共交通线网优化模型将公共交通出行的换乘时间设为变量，该变量取值则须根据所研究区域的公共交通线网换乘时耗具体情况的调查统计确定，这样处理能更好贴近现实的优化城市公共交通线网.

2) 使用遗传算法对所构建的城市公共交通线网的优化模型进行求解，并设计了站点变异和线路变异两个变异方法，能在迭代优化过程中更好对城市公共交通线路进行变动和调整，并能更快地寻找到公共交通线网的最优方案.

3) 通过实例分析，本文提出的城市公共交通优化模型和设计的求解算法可以有效减少换乘次数过多的公共交通出行和时间过长的公共交通出行换乘，减少乘客一次公共交通出行的平均时间，进而提高公共交通线网上所有乘客的整体出行效率.

[1] FAN W, MACHEMEHL R B. Using a simulated annealing algorithm to solve the transit route network design problem[J]. Journal of Transportation Engineering,2006,132(2):122-132.

[2] NIKOLIC M, TEODOROVIC D. Transit network design by bee colony optimization[J]. Expert Systems with Applications,2013,41(16):7200-7209.

[3] NAYEEM A M, RAHMAN M K, RAHMAN M S. Transit network design by genetic algorithm with elitism[J]. Transportation Research Part C: Emerging Technologies, 2014,46:30-45.

[4] ZHAO H, XU W T, JIANG R. The Memetic algorithm for the optimization of urban transit network[J]. Expert Systems with Applications,2015,42:3760-3773.

[5] 于滨,刘鸿婷,闫博,等.公交线网优化的双层模型及其解法[J].吉林大学学报(工学版),2010,40(2):402-405.

[6] 周媛,邓卫,胡启洲.基于遗传禁忌算法的城市公交线网优化研究[J].武汉理工大学学报(交通科学与工程版),2011, 35(1):42-45.

[7] 俞礼军,梁明萍.基于整数非线性规划的城市常规公交线网优化设计[J].中国公路学报,2016,29(2):108-115.

[8] KECHAGIOPOULOS P N, BELIGIANNIS G N. Solving the urban transit routing problem using a particle swarm optimization based algorithm[J]. Applied Soft Computing,2014,21(3):654-676.

[9] 李双,郭海洋,张琦.基于TransCAD的城市公共交通线路优化研究[J].科技视界,2014(33):144-145.

[10] 魏素豪,宗刚.基于线路“异质性”假设的轴辐式公共交通网络优化研究[J].运筹与管理,2017(10):42-48.

[11] 杜文举,张建刚,俞建宁.复杂公交社团网络模型的稳定性研究[J].计算机工程与应用,2017(23):39-46.

[12] 史路.城市公共交通线路模拟优化[J].公路交通技术,2014(2):111-114,118.

[13] 潘福全,马雨秋,张丽霞,等.基于限时免费换乘的公交线网优化模型与求解算法[J].科学技术与工程,2016(2):239-243.

[14] 王宇宁.基于公共服务需求导向的轨道线网规划优化研究[J].都市快轨交通,2016(2):13-17.

[15] 李育君.浅谈城市轨道交通提高乘客自助出行效率的可行性措施[J].低碳世界,2017，35(1):288-289.

[16] 朱宇婷.考虑乘客出行效率的城市轨道交通列车开行方案优化研究[D].北京：北京交通大学,2016.

[17] 郭露露,苏国锋,路堃,等.基于复杂网络理论的北京地铁网络脆弱性评估[J].工业安全与环保,2017(11):30-34.