个人快速交通动态任务分配问题的优化研究

朱辰阳，赵春晓

(1.北京建筑大学 电气与信息工程学院，北京 100044；
2.北京建筑大学 北京未来城市设计高精尖创新中心，北京 100044)

近年来，城市汽车连年暴增，交通拥堵越来越严重，行路难、停车难已经成为阻碍国内城市发展的主要因素[1]。当前交通结构的主要矛盾是私人轿车和开放式道路之间的矛盾，是彻底治堵的切入点。现有的公共交通无法与私人轿车竞争，只有轿车化的公共交通方式才能彻底缓解交通拥堵问题。

轿车化公交车和架空轻轨，构成了一种新型交通系统——个人快速交通(Personal Rapid Transit，PRT)系统，采用离线车站，用轨道轿车实现点到点的快速直达，其最大的价值是可以在未来取代一部分的私人轿车，从而彻底解决交通拥堵。但此系统中乘客的出行模式在空间和时间上不对称导致PRT资源无法被充分利用。因此，如何在考虑乘客行程需求、电池容量约束的情况下，使整个PRT系统的效益最大化，是PRT系统亟待解决的问题。

目前PRT动态任务分配方面的研究相对较少，主要原因是无人驾驶技术、传感器技术等关键技术尚未成熟，同时已运营的PRT系统线路结构较为简单，对PRT动态任务分配的要求不高。近年来，无人驾驶等关键技术以及相关的硬件设备不断完善，随着PRT系统在城市公共交通的广泛推广应用，对PRT动态任务分配的要求会越来越高，因此，深入研究PRT动态任务分配极为重要。

虽然当前任务分配的研究未有直接应用在PRT系统的研究方案，但针对其他不同的应用场景，国内外学者提出了诸多卓有成效的任务分配实现方法。卢骞[2]将改进的模拟退火算法和移动策略相结合；
周晶[3]引入迁移策略和贪心算法对任务分配方案进行局部提升。

在文献[4]中，作者提出了一种基于鱼群的多无人机任务分配算法(FIAM)；
蒋硕[5]在标准粒子群算法中采用阶层分级策略来为不同粒子选择相应的学习模型来解决多无人机协同任务分配问题。

文献[6]提出了一种细菌觅食启发式算法；
曹鹏飞[7]将生物免疫网络的工作机理应用到多机器人动态任务分配算法中；
Fang[8]综合机器人情感因素，提出了一种基于情绪渲染的寻踪任务分配算法(PTA-EC);杨惠珍[9]引入动态蚁群劳动分工中的刺激—响应原理，将任务的状态预测纳入响应阈值;李珣[10]提出了一种基于智能体博弈理论的分布式自主决策框架。

针对多车站、多PRT、乘客随机到达等复杂动态任务分配问题，该文建立了以PRT车辆里程利用率、乘客等待时间为优化目标的PRT车辆动态任务分配模型，并进行了针对此模型优化算法的研究。

1.1 PRT系统

PRT系统可以简单地表示为一个四元组，其中V表示PRT车辆实体，GN是一个导轨网络，E是城市社区，是V和GN所在的环境，f是系统目标函数，是实体状态的非线性函数。

V={v1,v2,…,vm}表示一组PRT车辆实体，代表轨道路网上m个运行的车辆。GN包括节点和链接。节点是一个地理位置，链接连接两个节点，类型有主线、出站、入站、合并、分叉、侧线(站)等。GN可以被建模为一个完整的有向图GN=(N,L)的子图，其中N={1,2,…,n}代表n个节点，L={(i,j)|i,j∈N,i≠j}代表n(n-1)条从节点i到j的有向链接。E是用来规划PRT系统的城市社区。f是系统目标函数。在四元组中，给定一个轨道网GN和车队V，选择能实现里程利用率和乘客等待时间之间最佳权衡的调度策略作为系统目标函数f。

Voronoi图是将一定的区域范围按照最近邻原则划分为n个凸边形子区域，其中n是区域范围中包含的点数量。在PRT系统中，以乘客需求点集{p1,p2,…,pn}中的点为中心，以相同的速率向外扩张，直到覆盖整个区域范围，由此形成PRT车辆的任务范围S。任一点扩张出的多边形Ti内的点满足下列条件：

Ti={x:d(x,pi)

式中，d表示需求点间的欧氏距离，Ti内任意一点到达pi的距离都小于该点到{p1,p2,…,pn}内其他点的距离。

1.2 PRT车辆动态任务分配模型

传统公共交通大多采用静态任务分配，根据线路乘客需求提前确定发车时刻表[11]。但由于各车站的客流是不断波动的，客流在一天内的波动会不断打破原有的车辆供需平衡[12]，这使得PRT系统随之动态变化。为了增加整个运行时段系统的稳定性，减少系统中乘客的等待时间，需要PRT系统在静态任务分配的基础上，根据客流的变化动态调整车辆的运行状态，实现车辆的动态任务分配。

系统优化的目标是制定一个力求为所有行程请求提供服务的任务分配策略，在满足每辆车的电池容量的前提下，找到里程利用率和乘客等待时间之间的最佳权衡。该文仅考虑每个行程请求之间的次序选择，对于具体线路规划暂不予考虑。为此，对该PRT系统做出如下假设:

(1)所有车辆的电池容量和初始电量相同，且电池不会发生损耗。

(2)PRT车辆的行驶速率恒定。

(3)每个行程需求的乘客规模不超过6人，即每个需求由一辆车即可完成。

(4)每个乘客行程请求所需车辆电量不超过车辆的电池容量。

(5)任务的产生是独立且随机的，即任务到达是泊松过程。

对于运营者而言，PRT系统要减少车辆资源的浪费，降低运营成本，提高整个线网的运行效率；
对于乘客而言，PRT系统要提供快捷和有效的交通服务。因此，制定有效的动态任务分配策略来实现这种平衡是PRT系统的重点和难点。PRT动态任务分配模型如图1所示。

针对特定环境下的动态任务分配，根据任务和车辆特点，可得多站点动态任务分配的目标函数和约束条件为：

(1)

(2)

(3)

(4)

uij∈{0,1}

(5)

式中，式(1)、(2)均为目标函数，式(1)表示系统载客里程利用率、式(2)表示乘客总等待时间；
式(3)～式(5)均为约束条件，式(3)表示PRT车辆电池容量约束，式(4)、(5)表示每一个任务点只能由一辆PRT负责。模型中的参数及变量见表1。

表1 模型参数及变量

2.1 PRT与多智能体系统

为了实现PRT系统的高效率，在车辆运行过程中，车辆安全间距较小，车辆与中央调度系统之间通信实时性要求较高，如果采用集中控制的方式，就会导致车辆自主性不高，运行过程当中如遇紧急情况需完全依赖中央调度系统回传指令，往往由于通信时间问题和信息掌握不全导致指令失效，系统的容错性较低。分布式控制方式可以很好地解决PRT系统车辆动态任务分配问题。每一个车辆就是一个简单的个体，具有相对独立性，个体之间可以进行一些简单的信息交互，车辆可以根据感知周围的环境信息进行自主控制。一方面中央调度系统可以对车辆的运行状态进行实时监测和调整，另一方面车辆也具备了一定的自行控制的能力，这降低了中央调度系统控制的难度，同时提高了系统的智能化程度和适应环境的能力。多智能体系统建模使分布式控制实现成为可能。

多智能体系统通过由实际系统总结出的系统中个体的运行机制，构建由这些自治智能体组成的复杂系统，观察个体之间以及个体与环境进行交互后，整个系统的演变趋势[13]。采用多智能体系统对分布式控制方式进行建模，优点是在系统中个体可以自下而上地进行智能决策，而不是中央系统自上而下地调整个体的行为，仿真结果更加贴近实际系统。

2.2 PRT系统多智能体模型

多智能体系统建模技术是对“主体”(Agent)自身以及它们之间的通信交互等行为进行模拟，通过观察系统整体涌现的行为，进而揭示实际系统的运行规律[14]。该文旨在基于多智能体模型从随时间变化的PRT系统中探究PRT个体行为与系统群体行为之间的微观关系。假设所有车辆最初位于停车场，车辆从出发站到目的站的路径最短。PRT系统多智能体模型中，主要有三类智能体形式，即静态主体道路和动态主体PRT车辆以及乘客。不同智能体主要属性及含义如表2所示。

表2 不同智能体主要属性及含义

3.1 粒子群算法

粒子群算法模拟了某一群体中个体通过与其他成员间的交互来共享与获得信息，一群粒子由个体曾到达过的最优点以及群体曾到达过的最优点的引导，在指定的搜索空间内随机移动[15]。在整个粒子群的运动过程中，粒子间相互影响，包含解的最佳局部点和全局点的信息在各个粒子之间传递、更新，每个粒子再根据这些信息调整其速度和方向，并继续在搜索空间内探索最优解的解空间。该文采用基于淘汰机制的粒子群算法求解任务分配问题。给出PSO的标准形式，如公式(6)、(7)所示：

(6)

(7)

3.2 粒子群算法与实际问题映射

应用PSO解决PRT车辆动态任务分配问题时，把实际站点上候车的乘客看作任务点，PRT在顺利完成每次任务后，会在该点产生一定数量的粒子，其能够随虚拟区域的环境变化做出选择、决策。由于新的乘客不断以一定的到达率随机出现，车辆事先无法得知乘客所在的位置，只能通过不断搜寻迭代，才能找到适应度函数较优的乘客位置。

3.3 适应度函数的改进

在PSO中，适应度函数的确定决定了一个问题能否找到一个更优的解。在该文背景下，适应度函数若为单一的距离指标，可以极大地提高里程利用率，但同时忽略了乘客的等待时间，也就意味着此时默认无论等待时间多长，乘客都不会离开，这与实际情况不符。综合考虑区域边界、目标出现位置概率以及整体覆盖率后，最终确定适应度函数如公式(8)所示：

(8)

式中，distij、Wj、m、n含义同表1，a、b分别为距离与等待时间的权重系数。

3.4 改进的粒子群算法

标准粒子群算法中，在某一区域范围内任何一点都可能是局部最优值或者全局最优值，但在针对PRT车辆动态任务分配模型中，只有特定的车站站点处才可能成为局部最优值或者全局最优值。在改进后的适应度函数评价标准下，粒子群从PRT所在位置产生后，总体的趋势是不断向外的，此时适应度函数的第一项不断变大，因此不断向外搜寻到的乘客需求点的适应度函数随之变大的概率很高，除非在此过程之中搜寻到了等待时间较长的乘客需求点，这导致很大概率上搜寻的时间越长，算法搜寻的结果越差。在文中模型背景下，乘客需求点是未知的、不断产生的，且任务分配方案评价指标之一是乘客的等待时间，因此对于整个系统分配方案的解的要求并不苛刻，且很难搜寻到最优解，所以更倾向于在较短的时间内得到较为满意的解而不是最优的解，标准粒子群算法很难适应文中针对的模型。为了提高算法的效率，首先将Voronoi图融合进PSO的初期搜索过程中，每当车辆完成运输任务后，粒子群会从车辆所在点产生，一旦粒子群超出了Voronoi图形成的车辆所在的任务区域之后，随即调整适应度函数中距离的权重系数a。然后为了应对在搜索后期结果变差的问题，该文引入了遗传算法的选择淘汰策略，提出了一种基于淘汰机制的粒子群算法(Elimination-Based Particle Swarm Optimization，EBPSO)，并将新的EBPSO算法与Voronoi图结合。当PSO优化进行到一定时间后，从当前的全局最优值处重新产生一定数量的粒子来替换掉那些原本适应度值较差的粒子继续进行优化。EBPSO调度算法的伪代码设计如下：

算法1：EBPSO调度算法

ask PRT所在点产生population-size个粒子

while searching-time != 0

ifelse 处于搜寻的初始阶段

if not Voronoi图划定的子区域范围

动态调整适应度函数中距离的权重系数a

end if

ask 一部分适应度差的粒子die

ask 全局最优值所在点产生相应数量的粒子

end if

if 搜寻到的当前点有乘客 and not 通信列表中其他PRT已确定的目标乘客

计算其适应度

if适应度优于粒子局部最优值

更新personal-best-x、personal-best-y

end if

ask粒子群中适应度最优的粒子

if适应度优于全局最优值

更新global-best-x、global-best-y

end if

ask每个粒子

按公式(6)更新粒子速度

按公式(7)更新粒子位置

end if

end while

ask 所有粒子 die

基于上述的多智能体模型，在NetLogo中实现了PRT系统模拟器，这是一个多智能体可编程建模环境。模拟器支持PRT系统任务分配求解，仿真内容包括PRT初始运行阶段对线网上已聚集的乘客的静态任务分配以及对整个运行阶段不断到达的乘客的动态任务分配。仿真环境的中心为坐标系原点(0,0)，通过设定121*59个点构成的坐标系来模拟一个4 km*2 km的区域范围。

4.1 静态任务分配

PRT系统刚开始运行时，线网中聚集了一定数量的乘客需求点，这要求首先进行目标位置已知的静态任务分配。对于静态任务分配问题，该文以基本的K-means聚类算法为基础，综合考虑已知需求点间的距离以及PRT车库与需求点的距离，同时根据PRT车辆数量限定形成聚类需求点的数量以及单个车辆集群的覆盖范围。模型中，共有4个PRT车库，分别为(-56，29)、(-22，29)、(24，-29)、(57，-29)，在仿真区域范围内随机生成20个初始乘客需求点，需求点位置分布如图2所示。采用K-means聚类算法求解得到20个初始乘客需求点的聚类结果如图3所示。

根据车库数量，20个初始需求点聚类生成的集群数量为4个，各集群中心分别为 (-49，8)、(-8，4)、(18，-12)、(48，9)。综上，采用K-means聚类算法得到PRT车辆初始静态任务分配的方案。

4.2 动态任务分配

在实际PRT系统中，任务目标状态和车辆状态会随客流发生变化，因此采用该文提出的基于淘汰机制的粒子群算法解决PRT车辆动态任务分配问题。对于求解模型的参数和优化算法的参数，主要是参考实验测试情况选取优化能力较好的设置，主要参数设置如表3所示。

表3 模型主要参数、参考值及取值范围

仿真环境的时间直接采用NetLogo内建的时钟计数ticks，为方便结果统计，实验均运行3 000 ticks。随机选取T=1 000 ticks和T=2 000 ticks时的关于乘客需求点的Voronoi图如图4和图5所示。值得注意的是，NetLogo平台拓扑允许回绕，即智能体可以从边界出现在另一边。因此从图上可以看出，回绕距离更短时，Voronoi图采用的是回绕距离。

仿真实验分别用标准粒子群算法、改进适应度函数后的粒子群算法和EBPSO算法进行求解，每个算法分别独立运行20次。随机选取其中的20个站点，以公式(1)所示的PRT里程利用率和公式(2)所示的乘客等待时间作为性能评价依据，车辆速度默认为60 km/h，实验结果如表4、图6和图7所示。

表4 里程利用率

经过多次实验得出结果，标准粒子群算法的平均等待时间为294.33 s，最长平均等待时间为501.19 s，平均里程利用率为54.71%；
对适应度函数改进后，平均等待时间为172.47 s，最长平均等待时间为345.45 s，平均里程利用率为54.14%；
采用EBPSO算法后，平均等待时间为153.21 s，最长平均等待时间为294.16 s，平均里程利用率为54.46%。可以看出，在解决PRT车辆动态任务分配的问题上，EBPSO算法在不损失里程利用率的前提下，相比标准粒子群算法使平均等待时间和最长平均等待时间分别降低了47.95%和41.31%；
相比仅改进适应度函数的粒子群算法使平均等待时间和最长平均等待时间分别降低了11.17%和14.85%，且通过对算法结果的标准差分析可知，EBPSO算法的实验数据波动更小，在运行上更加稳定。仿真实验结果表明，EBPSO算法在解决PRT车辆动态任务分配问题上比标准粒子群算法以及仅改进适应度函数的粒子群算法都更具优势。

PRT是一种新型公共交通方式，有潜力与当前主流交通方式竞争，以实现从本质上缓解交通拥堵问题。该研究的目的是为PRT系统中的动态任务分配问题提出一个有效的调度策略，实现里程利用率和乘客等待时间的最佳权衡。

首先基于NetLogo平台建立了PRT系统多智能体模型，然后对于系统中多站点动态任务分配问题，建立了以里程利用率和等待时间为优化目标的PRT车辆动态任务分配模型，最后针对PRT系统的主要特征以及模型中动态目标的特点，提出了对标准粒子群算法的适应度函数的改进方案，并将Voronoi图和淘汰选择策略与粒子群算法进行有效融合。通过多次对比实验，所提算法在不损失里程利用率的前提下，相比标准粒子群算法使平均等待时间和最长平均等待时间分别降低了47.95%和41.31%；
相比仅改进适应度函数的粒子群算法使平均等待时间和最长平均等待时间分别降低了11.17%和14.85%。实验结果证实了所提算法在解决PRT车辆动态任务分配问题上具有优越性。