定制公交多目标鲁棒优化模型与算法

陶 浪，马昌喜

(兰州交通大学交通运输学院，甘肃 兰州 730070)

由于采取公交出行的方式能够有效减少道路交通资源的浪费，提高人均交通资源占有率，因此，亟需寻找一种能够被乘客普遍接受的公共交通出行方式。目前，国内市场上公交出行方式主要有市场占有率较大的常规公交和逐渐起步的定制公交。常规公交存在运行速度低、运行质量差、车辆换乘不方便、乘客舒适度低及效率低下等缺点；定制公交安全、快捷、舒适、环保，能够有效弥补常规公交的缺陷。发展定制公交能够缓解人均道路资源占有率低与公共道路交通资源不足之间的矛盾。

国外对定制公交的研究较早，始于20世纪70年代，国内起步较迟。国内外在定制公交的研究上已经取得了一些成果。在国外，Ahmed El Fassi等人指出需要不断地优化定制公交路网布局及增加场站容量来适应逐渐增加的乘客量，提出一种基于离散仿真时间的方法来达到乘客满意度高，并且使用车辆数最小的目的来为决策者提供意见[1]；Alexandre de Lorimier以加拿大蒙特利尔市定制公交为例研究影响车辆使用的决定因素，为路网的扩宽提供指导意见[2]；Rahul Nair建立了平衡网络模型探讨决定定制公交系统的最优配置的因素，运营公司以乘客在距离其最近的上车点上车的前提来确定车辆泊位、车站容量及车辆数量使利益最大化[3]；Michael Duncan指出虽然定制公交在美国获得了大力支持，并且节约了相当一部分的社会资源，但是并没有达到其极限，通过合理恰当的优化方式还能节约其他潜在成本，降低运营费用[4]；T Liu和A Ceder研究定制公交在中国的发展历史，并分析了在中国发展定制公交的利与弊[5]。在国内，张敏捷等通过分析定制公交的服务模式构建了定制公交的线路规划模型，使用蚁群算法求解模型[6]；巫威眺在论文中从“点，线，面”的角度，以一体化干扰的思想，多层次、全方位探讨了如何在不确定环境下提高网络协同调度的鲁棒性[7]；胡列格，安桐等使用K-means聚类分析方法及范围覆盖公式确定了定制公交站点的选址和布局[8]；邱丰等针对可变线路式公交的特殊性，设计了以预约需求为主的第一阶段路径优化模型及以实时需求为服务目标的第二阶段模型的两阶段车辆调度模型，分别使用模拟退火与启发式插入算法进行了求解[9]；林叶倩等考虑公交公司的运营成本和乘客出行费用，从系统成本最优的角度出发，建立了可变线路式公交调度模型，并使用最近插入法获得初始解，依托遗传算法求解模型[10]；梁玉洁从大连交通现状出发，考虑天气因素建立了大连水上公交设计模型，利用pareto优化的启发式遗传算法进行求解[11]；王姣通过对定制公交开行存在的线路中车辆的配置数目、车辆的停靠站点、车辆到达每一个站点的时间等问题进行分析，建立了对应的模型，并利用改进的免疫遗传算法求解模型[12]；涂文苑对定制公交线网进行了研究[13]；王云鹏引入时间成本因素，对城市通勤班车的路线及站点布设进行研究[14]。

综上所述，国内对于定制公交的线路设计、站点布设等方面已经取得了一些成果，不过对于定制公交系统关于乘客等车时间的不确定性及系统的鲁棒性并未展开深入研究。鲁棒性是对系统稳定性的评判依据，研究定制公交系统的鲁棒性有助于确定随着乘客等车时间的波动定制公交该如何调度，能更好地与实际问题联系起来，从而为解决实际问题提供科学依据。

1 问题描述

路网客户需求量大，超过单辆定制公交车核载人数时，必须由多辆公交车协调完成乘客的接送任务。因此，问题描述为：路网上有且仅有一个定制公交发车中心，有多个乘客上下车点，所有公交均由发车中心出发，每辆公交可服务多个乘客上下车点，每个上下车点仅需一辆公交车服务，每辆公交车服务完所负责的乘客上下车点后返回发车中心。

2 模型构建

2.1 模型假设

(1)定制公交车辆的核载人数给定；

(2)路网上需要搭载定制公交的人数足够多；

(3)每个乘客上下车点的人数已知；

(4)发车中心与各个乘客上车点之间，各乘客上、下车点之间的行驶时间；

(5)任意上车点的人数不超过定制公交核载人数；

(6)车辆在线路上的行驶时间设为确定值；

(7)各交通节点乘客等车时间设为不确定值并利用合适的区间值来表示；

(8)乘客出行的单位时间成本确定。

2.2 符号定义

建立模型时运用的符号如下定义：

Zi—— 定制公交的配送中心，Zi={i|i=0}；

Zj——乘客的上、下车点，Zj={j|j=1，2，…n}；

Z——所有的节点集合，Z=Zi∪Zj；

V——定制公交的车辆集合，V={K|k=1，2，…k}；

dij——节点i到节点j的距离；

p1——定制公交载客时的运输费用系数；

p2——定制公交空载时的运输费用系数；

P——车辆的固定使用费用；

M——被派送出发的定制公交的数量，配送中心的车辆足够多；

Qk——定制公交车辆的限载人数；

tjk——在乘客上、下车点j的等车时间标称值，该点由第k辆车服务；

tik——k车在i点的等待发车时间；

tp——每位乘客的平均上车时间；

δjk——乘客上、下车点的乘客等车时间相对于标称等车时间的偏差值，并且此点由k车服务，δjk≥0；

Jk——第k行中所有受可变等车时间tjk的列下标j构成的集合；

Sk——第k行中受可变等车时间的影响而发生改变的等车时间的列下标j构成的集合；

Γk——鲁棒控制参数，控制解的保守程度，Γk∈[0，|Jk|]；

v——定制公交车辆的行驶速度；

Tj——定制公交车辆到达乘客上、下车点的时刻，Tj=Ti+Hi+Tij；

Hi——乘客需求点i的服务时间，包括乘客等车时间和乘客上、下车时间；

PE——当定制公交车辆早于最早时间到达乘客上、下车点的单位时间的惩罚值；

PL——当定制公交车辆晚于最迟时间到达乘客上、下车点的单位时间的惩罚值；

[ETi，LTi]——乘客上、下车点所要求的车辆到达时间窗；

pijk——车辆k从节点i到节点j时，节点i的上、下车人数，k∈V，pijk≥0；

w——运营公司的总收入。

2.3 建立模型

考虑运营公司和乘客两个群体的基本诉求。运营公司追求其利益最大化，也就是说在运营过程中要使投入的资源最少，产生的效益最大；乘客是定制公交的服务对象，在考虑选择以定制公交作为其出行方式并且能够接受相应的出行费用的前提下，乘客追求其出行时间尽可能的少。基于此，本文在乘客等车时间不确定的前提下，以最小化乘客的出行时间，最小化运营公司的经营费用为目标，考虑乘客上、下车点的服务时间窗、车辆的容量限制等约束条件，对不确定时间定制公交路径优化系统的鲁棒性进行分析，建立了定制公交路径优化的鲁棒模型。

2.3.1 目标函数

(1)最大化运营公司的总收入

同等转换：

(2)最小化乘客的出行时间

乘客的出行时间包括四个方面，分别为服务i节点的第k辆车的等待发车时间、车辆从i节点到j节点的行驶时间、乘客的上、下车时间及在乘客上、下车点的等车时间。

考虑到服务时间窗，在定制公交车辆不在规定的时间窗内到达时，需要对运营公司做出相应的惩罚。惩罚之后目标函数一转换为：

2.3.2 约束条件

(1)车辆的容量限制

(2)到达时间限制

定制公交须在乘客上下车点的服务时间窗内到达，若早到或晚到，则在目标函数中加入惩罚函数。

(3)一个乘客上、下车点由一辆车服务

(4)车辆服务完某一节点后返回发车中心

3 设计算法

考虑时间不确定的定制公交鲁棒优化模型为多目标模型，传统的单目标遗传算法不足以解决此问题，应采用更先进的遗传算法。NSGA-Ⅱ算法是在NSGA算法的基础上，通过嵌入快速非支配排序算法、精英保留策略及拥挤距离计算等技术，逐渐成为解决np-hard的多目标问题的一种常用算法。由于本文所建立模型拥有最小化乘客出行时间与最小化经营成本两个目标，属于多目标，所以采用NSGA-Ⅱ算法。在NSGA-Ⅱ算法的基础上通过改进编码方式，使之更符合考虑时间不确定的定制公交鲁棒优化模型的求解。

3.1 设计算法

3.1.1 编码与解码

编码方式采取自然数编码[15]。首先，对有需求的网络节点随机进行自然数编号并按照由大到小的方式排序，放在集合Z中，Z={1，2，3，…，z}，z表示第z个乘客上、下车点。乘客上、下车点的服务顺序为T=(t1t2t3…tz}。设置集合M和集合N，分别表示已经访问的乘客上、下车点与未方位的交通节点，初始化M和N，M={∅}，N={t1，t2，t3，…，tz}。接着按服务顺序访问T的各个节点，并在N中确定该节点在未访问节点中的顺序，并写进集合O中，同时在N中删除该节点，在M中加入该节点。对T的各个节点访问完毕之后，集合O中存放的就是T对应的基因型。假设网络中有9个节点，服务顺序T=(4 3 7 5 2 8 1 9 6)，其编码方式如图1所示。

图1 编码示意图

由上述编码图可知，服务顺序为T=(4 3 7 5 2 8 1 9 6)的基因型O=(435323212)。解码的过程与编码相反，反编码过程进行就能得到基因型O=(4 3 5 3 2 3 2 1 2)的解的个体，其服务顺序为T=(4 3 7 5 2 8 1 9 6)。不同的乘客上、下车点服务顺序，会导致乘客总体出行时间与经营公司的运营成本不一样，遍历所有不同的服务顺序，找到使得系统最优的pareto解。

3.1.2 遗传算子的设计

首先，给模型的任意一个初始解i定义两个参数ni和si，ni表示支配个体i的解的数量，si为个体i支配的解的数量。然后利用ni和si对个体进行非支配前沿排序，具体方法如下：

(1)在所有的解中找到ni=0的解，并将它放在第一非支配前沿F1。

(2)因为第Fk-1层非支配前沿所有的解的ni=0，在第k-1层中逐个访问si集合每个个体j，并计算个体j的nj和sj，将所有nj=0的个体放在第Fk层非支配前沿。

(3)令k=k+1，如果第Fk+1层为空，则停止计算；否则，转到(2)。

群体中某个个体的拥挤距离是指将具有相同非支配前沿的个体，依据其不同的目标函数值，对个体进行排序，并累加与其相邻的两个个体的平均距离值。令i∈I，I代表与i处于同一非支配前沿的解的集合。具体操作如下：

(1)对于每个不同的非支配前沿的个体，初始化其拥挤距离为零，即∀i∈I，I[i]d=0。

(2)计算每个个体的第m个目标函数值并按照第m个目标函数值对不同非支配前沿的个体按照从小到大的顺序进行排序。

(3)对于任意的一非支配前沿，对其不同的目标值进行排序之后，处于两个临界边缘的值规定为无穷大。n为处于相同非支配前沿的个体数目。I1d=Ind=。

①选择算子

依据上述介绍的非支配前沿的确定方法以及拥挤距离的计算流程，可以肯定群体中每个个体拥有两个参数，分别为非支配前沿Fk及拥挤距离id。依据Fk和id对个体进行选择。在群体中随机选择两个个体i和j，如果Fi≤Fj且id>jd，那么个体i优于个体j，记作i>j；否则j>i。重复上述步骤选择过程，直到选出popsize个个体。

②交叉算子

本文采用了自然数编码方式，而采用单点交叉的方式产生一条新的服务顺序，不会产生新的不可行解，且单点交叉简单，容易操作，故而在本文中采用单点交叉就能满足求解需要。

③变异算子

为保证变异之后不产生不可行解，变异后的编码方式对应着一条可实际操作的服务顺序，在本文中采取均匀变异算子。假设变异的概率为Pm，某个体的基因型为O=(1 2 3…m)，其中某基因i(1≤i≤m)发生变异，变异后i的等位基因只能从Oi=(1，2，3，…m-i+1)中选取。

3.2 NSGA-Ⅱ算法步骤与流程图

图2 算法流程图

针对于不同的具体问题，应该制定出不同的算法步骤与流程(见图2)。以下为关于定制公交鲁棒优化模型的NSGA-Ⅱ算法步骤。

step1：随机生成大小为popsize的种群Rt，t=0；

step2：利用快速非支配排序法进行排序，并给每个个体指定与非支配前沿相匹配的适应值大小，计算个体的拥挤距离；

step3：通过变异，选择，重组等操作，产生子代种群Qt，t=0；

step4：合并父代与子代种群，令Rt=Rt∪Qt，并依据非支配前沿与拥挤距离进行排序；

step5：对Rt进行精英选择策略产生新的父代种群Rt+1，重新计算Rt+1种群的拥挤距离；

step6：重复上述操作，若未达到迭代终止条件，则继续；否则，输出模型的最优pareto解。

4 实例研究

本文选取兰州市城关区某区域路网进行实例研究。定制公交空载时费用15 元/km，载客时费用35 元/km，固定使用费用200元，惩罚费用均为20 元/h；车辆行驶速度v=20 km/h。在总计49个节点的路网中选取20个节点，其中12个作为乘客上车点，其他作为乘客下车点。上车点、下车点的编号以及每个需求点的乘客数量如表1、表2所示。每两点之间的距离表示在路网图上(见图3)。

图3 兰州市城关区部分路网图

上车点出发时间窗上车点人数上车点编号出发时间窗上车点人数27:00-7:3013177:00-7:30947:10-7:408257:20-7:401276:40-7:107317:00-7:206106:50-7:2011347:00-7:3012137:00-7:3016426:30-7:008197:10-7:356477:00-7:3010

表2 乘客下车点信息表

运用本文所介绍的算法进行求解，通过分析，设计合适的遗传算子来求解定制公交多目标鲁棒优化模型。遗传算法相关参数设置如下：popsize=50，pc=0.4，pm=0.1，MAXGen=200，定制公交限载人数Qk=40，通过出行人数，可以确定总共需要3辆公交车才能满足路网中乘客的需求。以visual studio 2013为实验平台，多次运行程序，求得定制公交以乘客时间最小以及运营公司盈利最大为目标时的行驶路径。见图4和下页表3。

对公交车的行驶路径进行优化时，不能同时达到乘客出行时间最小及运营公司利益最大，需要以系统整体最优为优化目标。再对模型进行求解其鲁棒解时得出两组不同的pareto解，在控制车辆服务乘客上、下车点相同的情况下，得到的行驶路线不同。在pareto解1中，车辆1的乘客的出行时间比pareto解2的节约5.6%，车辆1运营公司总费用比pareto解2高9.9元；车辆2的乘客的出行时间比pareto解2的高6.5%，车辆2运营公司总费用比pareto解2低5.2元；车辆3的乘客的出行时间比pareto解2的高9.7%，车辆3运营公司总费用比pareto解2高10元。通过对pareto解的分析可知，系统解的鲁棒性逐渐增加，会对解的最优性产生影响，甚至是牺牲解的最优性。纵观上述例子，采用定制公交出行方式，能够节约出行时间，降低经营成本，增加公司收益。

图4 定制公交的运行路线图

注:图中三角形代表乘客下车点；正方形代表乘客上车点；圆圈代表某线路上的节点。粗虚线代表pareto解1、3中车辆1的行驶路线；细虚线代表pareto解2中车辆1的行驶路线，部分与1、3重叠；粗点画线代表pareto解1中车辆2的行驶路线；细点画线代表pareto解2、3中车辆2的行驶路线，部分与2、3重叠；粗实线代表pareto解1中车辆3的行驶路径；中实线代表pareto解2中车辆3的行驶路径；细实线代表pareto解3中车辆3的行驶路径

表3 模型的pareto解集表

5 结语

(1)本文综合考虑车辆的容量限制、乘客的上下车时间窗、乘客的等车时间不确定、一个交通需求点仅且只由一辆车服务、车辆服务完一条线路返回发车中心等因素，以最小化运营公司的经营费用、最小化乘客的出行时间为优化目标，建立了定制公交多目标鲁棒优化模型，并设计了解决定制公交多目标鲁棒模型的多目标遗传算法，通过遗传算法获得模型的pareto解。得出考虑乘客在上车点等车时间的不确定性的情况下，合理规划定制公交的出行路线能够节约乘客的出行时间，并且能够为运营公司带来效益。

(2)本文将定制公交在路网中的行驶速度假定为一固定值，未考虑路网中交通阻抗的变化对定制公交车辆运行速度的影响，对于仿真的结果存在一定影响。下一步将会对非固定行驶速度下定制公交系统的鲁棒性进行研究。

[1]Ahmed El Fassi，Anjali Awasthi，Marco Viviani.Evalua-tion of carsharing network’s growth strategies through discrete event simulation[J].Expert Systems With Applications，2012，39(8)：6692-6705.

[2]Alexandre de，Lorimier Ahmed，M El-Geneidy.Understanding the Factors Affecting Vehicle Usage and Availability in Carsharing Networks：A Case Study of Communauto Carsharing System from Montréal，Canada[J].International Journal of Sustainable Transportation，2013，7(1)：35-51.

[3]R Nair，E Miller-Hooks.Equilibrium network design of shared-vehicle systems[J].European Journal of Operational Research，2014，235(1)：47-61.

[4]M Duncan.The cost saving potential of carsharing in a US context[J].Transportation，2011，38(2)：363-382.

[5]T Liu，A Ceder.Analysis of a new public-transport-service concept：Customized bus in China[J].Transport Policy，2015，39(1)：63-76.

[6]张敏捷，冯 偲，吕晨曦，等.定制公交线路优化模型及求解算法[A].中国智能交通协会.2014第九届中国智能交通年会大会论文集[C].中国智能交通协会，2014，8.

[7]巫威眺.不确定环境下公交网络协同调度的鲁棒性及控制策略[D].广州：华南理工大学，2015.

[8]胡列格，安 桐，王 佳，等.城市定制公交合乘站点的布局研究[J].徐州工程学院学报(自然科学版)，2016(1)：27-32.

[9]邱 丰，李文权，沈金星.可变线路式公交的两阶段车辆调度模型[J].东南大学学报(自然科学版)，2014(5)：1078-1084.

[10]林叶倩，李文权，邱 丰，等.可变线路式公交车辆调度优化模型[J].交通信息与安全，2012(5)：14-18+33.

[11]梁玉洁.大连水上公交线路的设计与鲁棒优化[D].大连：大连海事大学，2014.

[12]王 姣.定制公交行车站点规划与时刻表编制研究[D].北京：北京交通大学，2016.

[13]涂文苑.定制公交的现网规划研究[D].北京：北京交通大学，2016.

[14]王云鹏.企业通勤班车线路优化研究[D].大连：大连海事大学，2013.

[15]关志华.非支配排序遗传算法(NSGA)算子分析[J].管理工程学报，2004(1)：56-60.