基于精英选择遗传算法的需求响应公交规划

2020-05-15

公路工程 2020年2期

(华南理工大学土木与交通学院，广东广州 510641)

0 引言

传统公交系统通常是基于固定线路固定时刻规划的，无法根据乘客需求做出动态调整。今年来随着“公交优先”口号的提出，定制公交、需求响应公交(Demand Responsive Transit，DRT)等乘客需求导向性新型公交模式被提出并尝试运营。以DRT为例，企业需要根据乘客的响应状态规划合适的车辆停靠站点和行驶路径，在尽可能满足乘客需求的条件下，控制运输成本，实现企业利润最大化。对于DRT的研究，Carlos[1]在1984首次提出DRT的设想，Rodier[2]对DRT中乘客出行收益进行了研究，Bellini等[3]建立了DRT车辆调度模型。Schilde等[4]等研究了不同速度下对DRT服务水平的影响。在国内，潘述亮等[5]等对包含特殊需求的DRT模型进行了研究，卢小林等[6]同时提出一种最小化公交车运营时间为目标的DRT路径优化模型，郑汉等[7]等对混合车型DRT进行了建模，并设计了Dantzig-Wolfe分解算法求解。

对DRT规划可分为站点规划和路径规划两阶段，首先规划公交临时停靠站点，通常通过K-means算法实现[8]。对公交路径规划可看作是一种特殊形式的带有容量约束的车辆路径问题(Capacitated Vehicle Routing Problem，CVRP)，不同的是公交车需要从同一战场出发到达同一目的地，目的地与出发地往往不同。车辆路径规划已被证实为NP(Non-deterministic Polynomial)完全问题，通常设计启发式算法[9-11]求解。遗传算法(Genetic Algorithm，GA)是通过模拟生物在自然环境中的遗传和进化过程而设计，是一种广泛使用的启发式搜索算法，其选择策略通常是基于轮盘赌(Roulette Wheel Selection Genetic Algorithm，RWSGA)的概率选择。为了提高算法收敛速度和搜索结果，本文提出了一种基于精英选择遗传算法[12](Elitist Selection Genetic Algorithm，ESGA)求解DRT中路径规划问题，并通过试验验证。本文首先建立的DRT站点选择和路径规划模型，并通过试验数据求解分析，对DRT规划具有一定的参考意义。

1 DRT规划模型

1.1 问题描述

在某一限定的区域内，已知一定数量乘客的位置、使用DRT意愿和支付意愿，企业根据乘客信息规划若干数量的临时停靠站点响应乘客出行需求，并在已有的车辆数量和车辆容量限制下，根据车辆出发地、目的地和停靠点规划响应公交接送乘客路径，以实现企业利润最大化。

为了方便模型建立和求解，有以下基本假设。

① 只有乘客的支付意愿高于或等于企业最低支付意愿时，乘客需求才会被企业响应；

② 每一局部区域的乘客需要到最近的临时停靠点乘车；

③ 每辆公交车都从固定的站场出发，完成所有乘客的接收后，到达固定的目的地；

④ 每辆公交车只开行一次，每个停靠点只能被公交车访问一次。

为了方便数学模型的建立，定义相关变量含义如下：

K：表示战场公交车总数量(k=1，2，……，K)；

N：表示公交车停靠站点总数量(n=1，2，……，N)；

M：表示公交车停靠站点总数量与出发地和目的地的数量之和(m=0，1，2，……，N，N+1)，m=0表示公交车出发地，m=N+1表示公交车目的地；

L：表示乘客总数量(l=1，2，…，L)；

cf：表示车辆固定成本；

c0：表示车辆可变成本，即单位距离行驶成本；

ua：表示乘客使用DRT的意愿，ua=1表示乘客具有使用意愿，否则ua=0；

pa：表示乘客支付DRT的意愿(元)；

p0：表示企业响应乘客最低支付意愿(元)；

ra：表示企业是否响应乘客需求，ra=1表示企业响应乘客需求，否则ua=0；

yai：yai=1表示第a个乘客在第i个站点乘车(a=1，2，…，L；i=1，2，…，N);

dij：表示点i到点j的行驶距离(i，j=0，1，2，…，N，N+1)；

xijk：xijk=1表示车辆k从站点i行驶到站点j，否则xijk=0，(i，j=0，1，2，…，N，N+1；k=1，2，…，K)；

Qi：表示第i个停靠站点的上车人数；

Qc：表示响应公交的最大载客量。

1.2 建立模型

由上述的问题描述和基本假设，以企业最大化利润为目标，建立DRT路径规划模型。

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

2 DRT规划模型求解

2.1 基于K-means算法的停靠站规划

本文首先基于K-means聚类算法规划了DRT停靠站点。K-means算法根据乘客坐标划分为k个簇，可以并将每个簇中心作为DRT的停靠站点，可以使得每位乘客到其所属簇内的站点的距离最小。K-means算法获得停靠站的流程如图1所示。

图1 K-means算法流程Figure 1 The flow of k-means Algorithm

2.2 基于ESGA的路径规划

本文设计了基于精英选择遗传算法(ESGA)求解模型，其相比于普遍使用的基于轮盘赌选择遗传算法(RWSGA)具有更快的收敛速度。ESGA其基本思想：依据上一代种群的适应度建立精英种群，在新一代的选择的过程中，用精英种群替换种群中适应度低的个体。ESGA流程如图2所示。

图 2 精英选择遗传算法流程Figure 2 The flow of elitist selection genetic algorithm

2.2.1编码

本文采用整数编码方案，用0表示公交车战场，1，2，……，n表示上车站点。如编码方案0-1-3-4-5-0-2-8-0-6-7表示企业需要规划3条响应公交线路，从公交站场0出发，路径分别为1-3-4-5、2-8和6-7，然后再到达目的地。

2.2.2适应度计算

ESGA通过选择算子淘汰劣势个体，保留优势个体，适应度为个体选择依据，适应度计算公式为：

fitness(xi)=Zi

(9)

其中,xi表示第i个个体;Zi表示第i个个体的总利润。对于不满足约束条件的个体，将其适应度设为0，可以通过选择操作将其淘汰。

2.2.3基于精英保留的选择算子

ESGA的选择算子主要包括精英种群的建立和选择操作两部分。通过上一代适应度最高的部分个体建立种群，然后在使用精英种群替换下一代适应度最低的部分个体。

2.2.4交叉算子

交叉算子通过随机选择2个个体的基因片段互换位置。由于受约束公式(3)和(4)的限制，为了保证交叉重组后的个体依然具有实际意义，交叉操作如图3所示。

在个体0-1-3-4-5-0-2-8-0-6-7和0-3-6-2-0-5-7-1-0-8-4中随机选择2个车辆路径0-2-8和0-8-4置于基因首端得到0-8-4-0-1-3-4-5-0-2-8-0-6-7和0-2-8-0-3-6-2-0-5-7-1-0-8-4，剔除重复基因位得到交叉后的2个个体0-8-4-0-1-3-5-0-2-0-6-7和0-2-8-0-3-6-0-5-7-1-0-9-4。

图3 交叉操作Figure 3 Cross operation

2.2.5变异算子

设计变异算子可以提高算法局部搜索能力。由于受约束条件(3)和(4)的限制，可随机选择2个停靠站点交换其位置。如，对于个体0-1-3-4-5-0-2-8-0-6-7，随机选择2个站点4和8，通过变异操作得到0-1-3-8-5-0-2-4-0-6-7。

2.2.6反转算子

反转算子本质上也是一种变异策略，可以提高算法局部搜索能力。例如，对于个体0-1-3-4-5-0-2-8-0-6-7，随机选择一段路径0-1-3-4-5，其通过反转操作得到0-5-4-3-1。

3 实例分析

3.1 实例数据

实例数据为某区域内的100位乘客，其坐标和支付意愿如图4和表 1所示。

3.2 求解结果

首先根据坐标信息使用K-means算法将乘客分为10类确定公交停靠站点，如图5所示；然后根据乘客支付意愿确定每个站点的上车人数，如表2所示。

然后基于ESGA规划公交路径，其中种群规模为200，进化代数为200，精英种群比例为10%，交叉概率为0.9，变异概率为0.1，反转概率为0.1，站场车辆数k为5，每辆车的限载人数Qc为40，表示企业响应乘客最低支付意愿为4元，车辆固定成本cf为5，车辆可变成本c0为0.1。经过20次的独立重复试验，选取最好试验结果作为最终结果，其进化曲线、车辆规划路径和计算结果如图6、图7和表3所示。

图4 乘客坐标Figure 4 Passenger coordinates

表1 乘客支付意愿Table1 Thepayingwillingnessforpassengers站点支付意愿/元0123456789总计1101021221010200111321111133000110400942000320401125200000321086100012201297001131220010800100141311190001331111111011001211209

图5 公交停靠点规划Figure 5 Bus stop planning

表2 公交停靠点信息Table2 Busstopinformation站点坐标响应人数1(343.74,883.97)82(656.42,361.95)93(632.76,812.99)64(313.41,593.06)105(547.09,243.67)66(819.06,601.69)87(814.77,221.22)88(326.92,240.38)109(502.46,477.59)1010(133.39,666.06)7

图6 进化曲线Figure 6 Evolutionary Curve

表3 计算结果Table3 Calculationresults公交车路径行驶里程成本/元乘客数量/人收入/元利润/元0-3-6-7-111137.56118.7622132.0013.240-1-10-4-8-111227.13127.7135218.0090.290-9-2-5-11882.2893.2325152.0058.77合计3246.97339.7082502.00162.30

从上述试验结果可以看出，ESGA经过近50代的进化即搜索到了最大利润方案，该方案共需要安排3辆公交车，共响应了82名乘客的出行需求，响应率达82%，车辆载客率分别为55%、87.5%和62.5%，均达到了50%以上，企业可获得的总利润为162.30元。

图7 行驶路径Figure 7 The routing of driving

为了对比ESGA与RWSGA的优劣，在同一初始种群的条件下，对精英种群为5%、10%、15%和20%的ESGA和RWSGA分别进行了20次独立重复试验。统计每种算法的运行时间和最优值的平均值和标准差如表 4所示。并选取结果最好的试验作进化曲线对比图如图8所示。

表4 算法对比Table4Algorithmcomparison运行时间/s最优值/元RWSGA平均值5.37124.47标准差0.6214.6ESGA(5%)平均值7.09145.37标准差0.2310.42ESGA(10%)平均值6.86148.02标准差0.2011.82ESGA(15%)平均值6.49156.36标准差0.828.02ESGA(20%)平均值7.02154.35标准差0.438.21

图8 进化曲线对比Figure 8 Evolution curve comparison

从上述结果中可以看出，ESGA虽然会少量增加算法的运行时间，但ESGA均在50代以内就可以搜索到最优方案；RWSGA需要50代以上才能收敛，并且还未搜索到最优解。因此，在收敛速度和搜索结果上，ESGA均优于RWSGA，证实了ESGA求解DRT路径规划的有效性，其中精英种群的规模设为15%左右求解结果较好。