在确定了候选线路集合R后,需要进一步构建数学模型从集合R中优选出较优的线路布局方案。
过短或过长的线路均不利于接运公交线路功能的发挥。令Lmax为所允许的最大线路长度,Lmin为所允许的最小线路长度,即
同时,应保证线路平均站间距在合理范围内,令γmax为所允许的最大平均站间距,γmin为所允许的最小平均站间距。
依据4.2.1节中关于地面公交站点分类的情况,可知第Ⅱ类站点是既有站点,第Ⅲ类站点为新增站点,均与轨道交通站点无线路直接连通,是接运公交线路必须提供服务的站点,均应纳入接运公交线路途经站点集合。令S表示接运公交线路途经站点集合,SⅡ表示第Ⅱ类站点集合,SⅢ表示第Ⅲ类站点集合,即
接运公交线路布设需要兼顾企业与乘客双方的利益。乘客期望线路尽可能顺直使其能快速到达轨道交通站点或目的地;公交企业则期望线路以尽可能少的运行成本覆盖尽可能多的区域,吸引更多的客流,获取经济效益。因此,接运公交线路布局方案既要满足线路行程时间最小化要求,也要实现覆盖居住人口和就业岗位数最大化目标。
线路行程时间可按式(4-11)计算:
式中:z1——总行程时间(min);
K——线路数量(条);
Nk——线路k(k=1,2,…,K)上站点数量(个);
——线路k站点间最短行驶时间(min),可根据站点间最短距离除以平均行驶速度估算获得;
——线路k上车辆站点平均停靠时间(min),可根据既有线路历史AVL数据估算其取值。
线路覆盖总人口岗位数可按式(4-12)计算:
式中:z2——总人口岗位数(人);
——线路k上站点300 m服务半径内覆盖的居住人口数(人);
——线路k上站点300 m服务半径内覆盖的就业岗位数(人)。
综合考虑乘客和企业双方利益,目标函数表达为:
式中:z——线路运营效益(元);(www.xing528.com)
C2——单位乘客票价(元/人);
C1——单位时间线路运行成本(元/min);
λ——非负权重系数,表征减少线路行程时间的重要性。
故接运公交线路布局方案生成问题可抽象为由目标函数(4-13)、约束条件(4-8)~(4-12)构成的多目标优化模型。当候选线路集合规模较小时可以采用枚举法求解模型,但当问题规模较大时,宜采用启发式算法如遗传算法进行求解。一条接运公交线路可以表示为途经站点的有序排列,故遗传算法中线路布局方案编码设计如图4-12所示。当线路为环线时,染色体的第一个基因和最后一个基因相同。
图4-12 遗传算法中线路布局方案编码设计示意图
下面具体介绍遗传算法中的交叉运算、变异运算和选择运算。
交叉运算的目的是对两个布局方案内的线路和线路走向进行交换,以获得更好的方案,可分为两类。
第Ⅰ类交叉运算通过从不同的父代方案中抽取线路进行交换形成子代方案,如父代方案1拥有线路1、2、3、4,父代方案2拥有线路A、B、C、D,进行交叉运算后产生子代方案1(1、2、C、D)和子代方案2(A、B、3、4)。需要说明的是,由于各条线路串联的站点数不一定相同,个体的基因串长度存在差异,第Ⅰ类交叉运算需要在具有同名首末站点的两条线路之间进行,即在经过同一对首末站的两条线路之间进行。
第Ⅱ类交叉运算通过对同一个父代方案中两条线路的部分走向进行交换形成子代方案,如图4-13所示。当两条线路被随机选中后且存在共同经过的站点时进行交叉运算,如线路2和4被随机选中,交换部分线路区段产生线路A和B;如无共同经过的站点,则继续随机搜寻其他线路。若两条线路共同经过的站点数大于1,则各站点作为交叉点的概率相等。
图4-13 第Ⅱ类交叉运算示意图
变异运算的目的是对线路走向进行微调,以获得可能丢失的较好的布局方案。变异点(站点)的选择是随机的,变异后的站点应为该站点的邻接站点,且需与下一站点有连通路径。
选择运算是依据父代方案产生子代方案的过程,将较好的方案遗传的同时淘汰较差的方案。为避免遗漏较好的方案,将所有方案的目标函数值进行排序,选择前M个方案作为优选出的方案。
求解接运公交线路生成问题的遗传算法具体步骤如下:
Step1:初代种群。在候选集合中随机生成初代种群,令种群代数i=1。种群规模为G,交叉率为ρc,变异率为ρm,最大迭代次数为imax。
Step 2:第Ⅰ类交叉。对每一个染色体,设一个服从[0,1]均匀分布的随机数α(i)。将α(i)<ρc的染色体进行配对,对选中的每一对染色体,在1至K(线路数量)间取一个整数K',交换代表前K'条线路的基因,即产生两个新的染色体。
Step 3:第Ⅱ类交叉。对经过第Ⅰ类交叉后的每一个染色体,设一个服从[0,1]均匀分布的随机数β(i)。将β(i)<ρc的染色体进行配对,对选中的每一对染色体中相应线路,寻找相同的基因(记其顺序为H),交换前H个基因,即产生两个新的染色体。
Step 4:变异。对所有染色体上的每一个基因(除染色体的第1个和最后1个以及各线路的第1个和最后1个基因外),设一个服从[0,1]均匀分布的随机数η(i)。若η(i)<ρm,则改变该基因的值(其编号变为邻接站点编号),从而产生新的染色体。
Step 5:计算目标函数值。判断各染色体是否满足约束条件,若满足,则计算目标函数值;否则,在增加惩罚参数P后计算目标函数值。
Step 6:选择。将所有染色体的目标函数值进行排序,选择前M个染色体作为优选出的染色体。
Step 7:收敛判断。若i>imax,算法停止并输出优选出的染色体目标函数值以及对应的染色体;否则,令i=i+1,转至Step 2。
免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。