开放式小区公交微循环站点与线路综合设计问题可以描述为:对给定的已知数量的小区, 根据居民出行需求调查确定需求点的位置与数目, 在已知公交微循环线路数目的条件下, 结合乘客的步行距离约束确定公交站点的位置与数目, 同时根据站距范围约束和线路闭合约束得到最终微循环线路布设结果, 每一条线路均为圈点线路, 以满足居民的出行需求, 并实现企业成本和乘客成本的最小化.

1)所研究的每个小区内部道路均具有公交车通行条件; 2)所研究区域内机动车之间、行人之间无相互影响; 3)所研究问题的总成本与企业成本和乘客出行成本线性相关; 4)所研究区域周边只有1个地铁站.

模型参数符号及含义见表1.

表1

Tab. 1

表1(Tab. 1)

表1 模型参数符号及含义 Tab. 1 Symbols and its definition of model parameters 符号 含义 S 公交备选站点集合, 以i、j为索引, i, j取正整数 D 需求点集合, 以m、n为索引, m, n取正整数 L 公交线路集合, 以k为索引, k取正整数 dij 节点i到节点j的距离 dmi 需求点m与车站备选点i的距离 lmax 每一条线路总长度的上限 lmin 每一条线路总长度的下限 smax 站间距的上限 smin 站间距的下限 M 给定的线路条数 xijk 车站备选点i和车站备选点j是否为线路k上的相邻站点, 若是则为1, 否则为0 yi 车站备选点i是否被选中, 若是则为1, 否则为0 zmi 需求点m是否有车站备选点i提供服务, 若是则为1, 否则为0 α , β 权重值, α , β ∈ [0, 1]

表1 模型参数符号及含义 Tab. 1 Symbols and its definition of model parameters

开放式小区公交微循环站点与线网综合设计模型如下:

minα∑i∈S∑j∈S∑k∈Lxijk·dij+β∑m∈D∑i∈Szmi·dmi(1)

s.t.

∑i∈S∑k∈Lxijk=yi(2)

∑j∈S∑k∈Lxijk=yj(3)

∑k∈L∑i∈S\{0}xijk=∑k∈L∑j∈S\{0}x0jk=M(4)

∑i∈S∑j∈Sxijk≥1(5)

xijk≤yi(6)

zmi≤yi(7)

∑i∈S\{0}zmi·yi=1(8)

lmin≤∑i∈S∑j∈Sxijk·dij≤lmax(9)

xijk·smin≤xijk·dij≤xijk·smax(10)

zmi·dmi≤smax(11)

xijk, yi, zmi∈{0, 1}(12)

应用多段组合染色体编码, 将染色体进行整数编码.一条染色体由表示每条线路的基因段组成, 每条基因段由0及若干自然数组成, 其中基因段开头和末位的“ 0” 为线路起讫点, 其他“ 0” 为空位不表示任何含义, 非0整数表示该线路途经的站点序号.

模型中的式(2)~式(5)及式(7)规定了线路的形状和特性, 该算法编码的目的在于检查所设计的线路是否符合其他约束条件, 若不符合, 则重新编码.

在编码染色体前, 先对各备选站点进行编号, 以4条线路12个备选站点为例, 染色体编码示意见图1.图示中所对应的4条线路分别为:O(地铁站, 公共起点)→ 10→ 12→ O; O→ 7→ 2→ 8→ O; O→ 1→ 3→ 6→ O; O→ 4→ 9→ 5→ 11→ O.

图1

Fig.1

	Figure Option ViewDownloadNew Window
	图1 染色体编码示意Fig.1 Chromosome coding diagram

1)选择.采用最佳个体保存与轮盘赌选择相结合的策略.具体步骤为:首先计算并给每代种群个体的适应度进行排序, 排序后第一条染色体为适应度最高的个体予以保留; 其余根据前代种群个体适应度, 采用轮盘赌选择策略进行运算.

2)交叉.染色体的交叉操作采用单点交叉方式.

3)变异.按照预设变异概率, 随机将染色体的基因变异成为站点序号范围内的任意一点, 变异之后对所得染色体进行检测, 若不符合条件便重新变异, 直到可行为止.若无需调整, 则变异结束.

建立判断函数, 函数值规定为0-1变量, 染色体若符合所有约束条件则函数值返回1, 若不符合任意约束条件则函数值返回0.当判断函数运行结果为0时, 启动编码函数, 将不符合约束条件的染色体重新生成.

该小区现有西门、南门2个出入口.小区内部道路均具备消防通道条件.经过实地考察, 获得了小区居民在高峰时间段出行需求的数据, 结合小区内道路的设置情况和住宅楼的分布情况, 通过在某周三(工作日)进行居民出行调查, 识别在早高峰时间段居民在小区内高频出现的150个位置, 即所考虑的需求点.根据这些需求点的位置作聚类分析, 得到25个车站备选点, 最终期望得到的车站实际位置将从这些备选站点中产生.取站间距下限s_min=200 m, 站间距上限s_max=400 m(不包括实际站点和地铁站的距离), 线路条数M=4.

输入算法参数为:迭代次数MAXGEN=200, 种群规模SIZEPOP=50, 交叉概率P_cross=0.9, 变异概率P_mutation=0.09, 线路条数M=4, α =0.4, β =0.6.在Intel Core i5-2450M CPU @2.50 GHz, 内存8 G, 操作系统 Windows 10 环境下, 使用数学求解器Matlab R2015b求解50次, 每次均可获得对应种群下的最优解, 且每次求解运行时间均少于15 s.从Matlab的运算结果中调取Individuals数据表, 对50次结果进行比对分析, 得到一组最优解.该解的4条线路分别为:

①O(地铁平西府站, 下同)→ 1→ 7→ 11→ 23→ O;

②O→ 8→ 5→ 9→ 14→ 15→ O;

③O→ 12→ 13→ 21→ 25→ O;

④O→ 10→ 17→ 18→ 19→ 20→ O.

得到的公交微循环站点选址和线路设计方案见图2.绘制收敛函数曲线, 见图3.由图3可知, 在100代后算法收敛.

图2

Fig. 2

	Figure Option ViewDownloadNew Window
	图2 公交微循环站点某小区选址和线路设计方案Fig. 2 Site and network layout of the bus microcirculation in a community

图3

Fig.3

	Figure Option ViewDownloadNew Window
	图3 遗传算法收敛函数曲线Fig.3 Convergence function curve of genetic algorithm

通过计算直线距离, 可以得到线路布设前后的居民总步行长度, 对比后可以发现线路布设前居民从所有需求点步行至小区南门、东北门及西门距离共15 342 m, 大于线路布设之后居民步行至最近微循环线路站点的距离共3 219 m, 也证明了微循环线路的设置可以有效减少最后一千米的步行距离.

需要说明的是, 尽管Lingo算法可以给出最优解, 但使用Matlab遗传算法完成求解的时间远远小于Lingo算法.此外, 当线路条数M≤ 2时, Lingo算法可以在有限的时间内给出一个最优解; 当线路条数 M> 2时, 针对每个 M值都分别进行10次运算, 发现使用遗传算法更节省时间, 其得到的最优解与使用Lingo算法得到的最优解的差值在允许范围内, 使用Lingo算法和使用Matlab遗传算法计算结果的比较如表2所示.表2中对比度=(Matlab遗传算法计算结果-Lingo算法计算结果)/Lingo算法计算结果× 100%.

表2

Tab.2

表2(Tab.2)

表2 使用Lingo算法和使用Matlab遗传算法计算结果比较 Tab.2 Results comparison of Lingo algorithm and genetic algorithm in Matlab 线路条数 M 计算组别 Lingo算法 Matlab遗传算法 差值/m 对比度/% 目标函数值/m 求解时间/s 目标函数值/m 求解时间/s 2 1 8 763.03 158 9 601 7.02 838 10 2 9 477 6.93 714 8 3 9 503 6.87 740 9 4 9 339 7.15 576 7 5 9 402 7.07 639 8 6 9 395 6.97 632 7 7 9 557 6.97 794 9 8 9 440 7.10 677 8 9 9 387 7.04 624 7 10 9 530 7.09 767 9 3 1 9 635.84 1 620 10 098 7.24 462 5 2 10 116 7.35 480 5 3 10 708 7.27 1 072 11 4 10 133 7.14 497 5 5 10 716 7.22 1 080 11 6 10 586 7.31 950 10 7 10 452 7.23 816 8 8 10 600 7.37 964 10 9 10 285 7.26 650 7 10 10 775 7.25 1 139 12 4 1 — (1 800 s内无法 计算出结果) — 10 777 7.44 — — 2 10 389 7.40 — — 3 10 472 7.55 — — 4 10 548 7.13 — — 5 10 657 7.08 — — 6 10 701 6.93 — — 7 10 373 7.10 — — 8 10 586 7.33 — — 9 10 359 7.63 — — 10 10 587 7.40 — — 5 1 — (1 800 s内无法 计算出结果) — 11 175 7.70 — — 2 10 857 7.54 — — 3 11 255 7.55 — — 4 11 179 7.95 — — 5 10 868 7.71 — — 6 10 988 8.10 — — 7 11 286 7.85 — — 8 11 222 7.61 — — 9 10 946 8.42 — — 10 11 151 7.76 — —

表2 使用Lingo算法和使用Matlab遗传算法计算结果比较 Tab.2 Results comparison of Lingo algorithm and genetic algorithm in Matlab

为了向决策者提供支持, 以下对公交企业成本权重α 、乘客出行成本权重β 以及线路条数M进行灵敏度分析.

1)对α 和β 进行灵敏度分析.

对α 、β 分别取4组值, 并针对每组权重值对不同线路条数M计算目标函数值(该值为使用遗传算法运算20次的平均值), 不同α 、β 值下的目标函数值见表3.

表3

Tab. 3

表3(Tab. 3)

表3 不同α 和β 值下的目标函数值 Tab. 3 Objective function values under different values of α and β α β 线路条数 M/条 目标函数值/m 0.1 0.9 1 10 220 2 10 378 3 10 814 4 10 907 5 11 374 0.2 0.8 1 9 605 2 10 094 3 10 408 4 10 626 5 11 264 0.3 0.7 1 9 392 2 9 828 3 10 330 4 10 580 5 11 211 0.4 0.6 1 9 030 2 9 734 3 9 967 4 10 121 5 10 794

表3 不同α 和β 值下的目标函数值 Tab. 3 Objective function values under different values of α and β

在以上算例中, 当 α的值不断增大时, 相同线路条数对应的目标函数值不断减小, 表明较大的 α值对应的最优解更有优势, 可以使得公交公司的成本和乘客出行成本的总和达到最优, 因此可以设定 α=0.4, β=0.6.

需要说明的是, 当针对的研究区不同时, 需求点的位置与数量也不同, 在不同的 α与β的取值下得到的结果及其变化趋势可能不同, 最后得到的设计结果也会有不同.因此在实际规划中, 决策者应根据具体要求输入参数 α、β,进而找到使目标函数值最优的权重值组合.

2)对线路条数 M进行灵敏度分析.

乘客利益和运营企业利益不同, 乘客希望省时、便捷; 企业则希望减少线路条数以减少运营成本.当α 、β 取不同值时, 企业运营距离成本和乘客出行距离成本随线路条数M的变化曲线见图4.

图4

Fig.4

	Figure Option ViewDownloadNew Window
	图4 企业运营距离成本与乘客出行距离成本随线路条数变化曲线Fig.4 Changing curves of the enterprise operation cost and passenger travel distance cost with line number

由图4可知, 当α 、β 取值相同时, 乘客出行距离成本随线路条数增加而减少, 企业运营距离成本随线路条数增加而增加.因此, 决策者在选定参数α 、β 值后, 应综合考虑企业与乘客利益, 合理布设线路条数.