面向动态公交的离散分层记忆粒子群优化算法
2024-04-23黄君泽吴文渊李轶石明全王正江
黄君泽,吴文渊,李轶,石明全,王正江
(1.中国科学院重庆绿色智能技术研究院自动推理与认知重庆市重点实验室,重庆 400714;2.中国科学院大学重庆学院人工智能学院,重庆 400714;3.重庆市凤筑科技有限公司,重庆 401120)
0 引言
随着信息技术基础设施在交通领域的不断完善,智慧交通——一种集成了信息技术与数据分析的现代交通系统也正快速发展。在运营端,公交信息基础设施如公交全球定位系统(GPS)、公交智能交互平台正不断完善;在乘客端,移动互联网的发展使得乘客能将自己的需求实时提交给出行服务商。这两点变化的发生使得一种名为动态公交的新型公交运营模式成为可能,并且动态公交已经成为了许多城市公交企业布局智慧交通的重要落脚点。动态公交融合了传统公交和网约车[1]的运营模式,乘客可以像预约网约车拼车模式一样在网上平台下单,告知运营商自己的上车点、下车点和预计的上车时间,并在约定时间和约定地点上车,在无换乘的前提下前往目的地;但与网约车不同的是,前来接上乘客的不是小型轿车,而是相对较大的面包车、大客车等,并且一车可以同时接送多人。
在动态公交的运营机制和所需考虑的运营指标上,已经有了较多研究[2],运营机制方面的改动包括添加换乘点[3]、设置多车场[4]、使用电动车[5]、设置充电站[6]、订单设置软时间窗[7]等;而运营指标方面包括着眼于提升居民出行满意度、减少政府在公共交通领域的开支、缓解城市拥堵现象、降低出行带来的碳排放等。但在对动态公交数学建模、对动态公交问题求解这两方面的研究尚有不足。
动态公交问题从路径规划问题的角度而言,属于电召问题(DARP)的一类子问题。电召问题是一种区别于车辆路径问题(VRP),每个订单有两个或更多个需要依序经过的途径点的路径规划问题,并且在车载客量大于2人时是NP难问题[8]。而动态公交问题在电召问题的基础上,要求订单随机生成(Stochastic)、允许根据新信息更新在途车辆的路径(Dynamic)。需要指出的是,另一种常见的新型公交——定制公交,则是电召问题中确定订单(Deterministic)、不允许更新在途车辆路径(Static)的另一子类型问题,所建立的模型和使用的求解算法与动态公交存在巨大的差异。
需要指出的是,本文提出的动态公交问题具有一定的特殊性:1)动态公交问题的解空间是离散空间,这使得在连续问题上的求解算法不适用,并且动态公交问题的解由两个子问题的解构成,还存在大量相似或相同的子问题;2)动态公交问题的离散状态较多,动态公交问题中车辆数、可访问点数和订单数决定了动态公交问题的解空间的大小,在实际问题中,相较于之前的研究,这三者都较多,因此离散状态较多,许多算法无法很好地进行求解;3)动态公交问题的实时性要求较高。在动态公交问题的实际应用中,以本文后续实验所选定区域为例,高峰期订单数平均可达180个/min,而服务器需要在一定时间内为用户反馈计算结果。
目前,电召问题求解算法可以分为求精确解算法与启发式算法两大类,其中多数算法不能满足上述动态公交问题的具体要求。求精确解算法以分支定界法[3]和约简法[9]及其变种为主,但目前,求精确解算法的计算复杂度都较高,因而可解决问题规模较小,一般仅能解决使用车辆数在10车以内、订单数在100单以内的问题[10],不能满足上述实时性的要求,难以在现实场景中应用。启发式算法包括神经网络[11]、仿生算法[12]、插入算法[13]、模拟退火算法[6,14]、多方逼近算法[15]、禁忌搜索(Tabu Search)算法[3,16]、变邻域搜索(VNS)算法[4]和大邻域搜索(ALNS)算法[5,13]等,当解空间离散且离散状态较多时,大多数启发式算法对初始解高度敏感,并且都会面对探索和利用的平衡问题。
由于现有算法都存在一定的问题,因此有必要探索新的求解算法。在求解优化问题时,粒子群优化(PSO)算法是一种被长期验证有效和使用的算法。PSO算法是一种将问题的解视为粒子,并使多个粒子依一定规则相互作用以探索解空间、寻找最优解的优化算法。国内早在2004年就有基于PSO算法求解多目标问题的研究[17],并一直得到研究者的广泛关注[18-19]。在连续空间下,PSO算法的参数设置和改进方向[20]都较为成熟,但相关的研究无法简单地套用在离散空间PSO算法上[21]。
在路径规划领域,PSO算法也长期得到广泛的研究与应用。国内同样于2004年就有学者研究了PSO算法求解车辆路径问题[22],王飞在带时间窗的车辆调度问题上应用了改进的PSO算法[23],近期的车辆路径问题综述[24]中也对PSO算法近年来的研究进行了总结。在面对多目标问题时,PSO算法也展现出了较好的适用性[19,25]。然而,目前较少有将PSO算法应用到动态公交问题上的研究[21]。
原始的PSO算法不能较好地适用于动态公交问题,有以下原因:1)在粒子群迭代的过程中,多个粒子会重复计算相同或相似订单集的最优路径,造成冗余计算;2)相对于其他启发式算法,PSO算法较为不依赖初始解,但优质的初始解也可以帮助算法快速收敛;3)PSO算法在离散空间存在容易早熟的问题。
针对以上问题,基于相关领域的研究现状,结合动态公交问题的解的形式的特点,本文提出了动态公交问题的模型,并在此基础上对基础的PSO算法做出了以下创新:
1)将PSO算法也针对性地拆分成两层分别进行迭代优化,并提出可复用、可继承的低层粒子结构,避免重复计算的开销,提高算法的实时性。
2)提出基于出行偏好的初始解生成算法,从而利用数据生成在未来时间片更优的初始解,同时帮助算法快速收敛。
3)引入自适应变异机制,在离散空间上重新设计自适应参数和变异概率,避免算法早熟,减少收敛到局部最优的情况。
1 动态公交问题
动态公交问题是一种多车路径规划问题,源于动态公交这一公交运营模式。动态公交区别于传统公交,其由乘客先发起一个包含该乘客的起终点、上下车时间窗等信息的订单,随后公交公司结合订单信息和当前公交车辆状态将该订单指定到一辆公交车,由其完成该乘客的需求,并且公交车可以部分或完全不沿公交线路行驶;动态公交也区别于定制公交,其允许订单实时发起、允许乘客期望上车时间接近发起时间,因此需要能够实现实时计算并分配订单;动态公交还区别于网约车,每辆公交上可以搭载超过5名乘客,这对算法的复杂度提出了一定的挑战。动态公交运营模式示意图如图1所示。
图1 动态公交运营模式示意图Fig.1 Schematic diagram of dynamic public transport operation mode
在动态公交问题中,每个订单都具有两个途径点,并且要求以给定的先后顺序访问这两个途径点,这使得动态公交问题模型区别于传统的路径规划问题。但在其他路径规划问题如旅行商问题(TSP)、车队寻径问题(VRP)中,也存在一些目标函数、变量和限制条件的设置具有一定的参考价值。在过往的动态公交模型的研究中则探索了动态公交的运营机制,包括是否设立实体站点、是否允许换乘[26]等。在现实问题中,设立实体站点、存在多车场[4]、允许订单超时[11]是较为普遍的情况,并且一般不允许换乘。因此,本文所构建模型也包括多车场,并在单目标模型下设置了订单时间窗。
1.1 目标函数建模
针对动态公交所应关注的运营指标,也已有了较多的讨论。动态公交服务有3个主要的相关方:乘客,公交服务运营商,其他社会组织。这三方具有各自不同的关心点:公交服务运营商希望尽可能降低净支出;乘客希望能接受公交服务,并希望最小化自身的总出行时间;其他社会组织则希望通过推广公共交通缓解城市拥堵和降低燃油消耗和碳排放。根据以上三方的实际关系构建目标函数,其中:与乘客相关的指标包括接单率、乘客候车时间和乘客在车时间3项;与运营方相关的指标包括服务订单数、所需司机工时和运营里程3项,其中,服务订单数在订单数不可控的情况下等价于接单率,司机工时与最大可用车数呈正相关;其他社会组织关心的指标包括服务订单数、燃油消耗和碳排放量3项,其中,服务订单数越多,城市道路车辆数就越少,对城市拥堵现象的缓解就越明显,而燃油与碳排放量一般都与运营里程呈正比。因此,最终构建的目标函数旨在实现最大化接单率、最小化平均乘客候车时间、最小化平均乘客在车时间和最小化运营里程,具体公式如下:
(1)
(2)
(3)
(4)
多目标问题的求解方法主要包括引入博弈机制[11]和转化为单目标2种,本文将采用将多目标问题中的目标一部分通过加权和的方式转化为新的单目标,另一部分转化为约束条件的方式将动态公交问题建模为单目标问题进行求解。具体地,本文对上述目标函数进行转化,合并式(1)与式(4),并将式(2)与式(3)转化为约束条件,如下式所示:
(5)
(6)
(7)
本文通过新增每单收入常量、每里程代价常量合并了对接单率和里程的目标;通过新增比例约束和常量约束来限制乘客在车和等车时间。在式(5)中:po表示接受该订单带来的收入;co表示车辆的支出。在式(6)中:Ttravel表示订单可接受的最长在车时间。在式(7)中:Twait表示订单可接受的最长候车时间。这一形式下,式(6)、式(7)即一般意义上的时间窗约束。
1.2 约束条件建模
动态公交具有的订单是动态、随机生成的,因此动态公交的订单分配过程也需要分时间片进行,并且满足订单约束。具体到某一辆公交,其任意时刻的路径都应是满足车辆路径约束的,并且在公交往往具有多车场的现实背景下,公交路径的起终点也应满足一定约束。
1.2.1 订单约束
订单约束包括分配约束与载客量约束。其中,分配约束表示订单在车辆间的分配情况,载客量约束则限制车辆的最大接单数。设b载客量为vb,vo表示订单的人数,Tnow表示算法中的当前时刻,则:
(8)
(9)
(10)
(11)
式(8)表示所有订单都被归入一个分配集,其中分配集0为下一时刻的待分配集;式(9)表示所有分配集间交集为空,即订单不能重复分配;式(10)表示车辆的接受订单集为车辆在当前时刻之前的所有时刻的分配集的并集;式(11)表示车辆的接受集的载客量之和不能大于车辆的额定载客量。
1.2.2 车辆路径起终点约束
在动态公交实际运营过程中,在车辆没有订单时停靠在何处是一个具有实际意义的问题。如果要求公交每次接单后都必须回到集中停放的车场,可能会产生不必要的成本;但公交车辆也不能停放在任意的道路或公交车站边,否则会引起交通堵塞。为此,根据公交运营的实际情况,本文提出可以将部分暂时无订单车辆临时停放在道路边的临时停车位,避免车辆不必要地返回车场。此外,在新能源公交车需要充气、充电时,需要前往指定的停放点进行充气、充电。为对以上情况进行建模,设置车辆路径起终点约束。
车辆路径具有一个起点,是车辆当前所处或出站车辆当前正要前往的站点;车辆路径具有一个终点,是满足约束条件下离车辆的最后一个途径节点最近的可行停放点;车辆终点的约束条件包括是否需要充电、充气、加油,以及是临时停放还是长时间停放。
(12)
(13)
(Eb≤Elimit)=Cb
(14)
(15)
(16)
其中:路径及其后的中括号表示路径中的指定下标位置的元素,下标从0开始标号。式(12)、式(13)表示车辆路径起终点,分别指车辆路径经过的第一个站点与最后一个站点;式(14)表示当车辆能源低于给定值时,车辆需要充能;式(15)表示若车辆需要充能,则车辆路径的终点需要可以为车辆提供对应的能源补充;式(16)表示若车辆需要退出运营,则车辆路径终点需要支持长时间停放车辆。
1.2.3 车辆路径约束
(17)
(18)
(19)
(20)
Lb=distance(rb)
(21)
式(17)、式(18)约束了订单起点在巴士路径中的位置;式(19)、式(20)约束了订单终点在巴士路径中的位置;式(21)表示车辆里程数,即车辆全天路径的长度。
2 离散分层记忆粒子群优化算法
本章分为3个部分:第1个部分介绍离散空间中的动态公交问题的解的结构及基础运算的定义;第2个部分介绍基于出行偏好的初始解生成算法,该算法首先在给定城市道路图上生成名为路网的图结构,随后在该图结构上依一定规则游走产生符合要求的随机路径;第3个部分介绍分层自适应变异记忆PSO算法,该算法基于离散空间中动态公交问题解的编辑距离动态调整粒子收敛速度、控制粒子随机扰动的方法,同时基于对车辆种类的定义给出将粒子群分层、记忆、继承和复用的方法。
本文算法整体流程如图2所示,其中订单层粒子单次迭代流程如下:对每辆车所分配到的订单集,首先在以订单集为键的路径层解字典中检索其对应的粒子群;若检索到,将对应的粒子群进行相对于正常次数而言较少的次数的迭代;若未检索到,则根据2.3.1节所述规则进行求解,并迭代正常次数。此处的迭代次数具体值为超参数,本文所用迭代次数详见3.2节实验参数。完成路径层求解后,通过在路径层解的最后一个订单结束的站点最近的符合约束的停放点加入路径,即可得到一个车辆的路径及其对应的代价,由此订单层的每个粒子可以计算得出其所对应的所有车辆的代价和,从而可以进行粒子位置优劣的比较,并进行速度和位置的更新。
图2 分层自适应变异PSO算法流程Fig.2 Procedure of discrete hierarchical memory PSO algorithm
2.1 动态公交问题解的结构及运算的定义
PSO算法在迭代过程中需要计算两个解间的距离,但在动态公交问题中,解空间为离散空间,因此不能直接使用连续空间中对解的距离的定义[27]。本文采用定义解及对解的操作的方式解决这一问题。动态公交问题的解包括以下两部分:订单在车辆间的分配情况,车辆行驶路径中对节点的访问顺序。设点全集为V,有k个可用车辆,则粒子的解S为一个包含k+1个分量的向量,其中,第一个分量D表示订单的分配状况,包含|O|个有k种取值的变量d;其后的k个分量Rb分别表示其右下角标所指示的车辆经过的点的序,包含l个在点集V中取值的变量v,l的取值范围为0～2|O|。可将动态公交问题的解S表示如下:
S=
D={do∈D}
Rb=
由于动态公交问题中不同的解可以通过使用上述两个算子进行转化,因此可以根据两个不同解间变换所需的基础操作定义解与操作算子的加减法。设V为粒子的速度,μ1、μ2分别为两种操作的操作次数,则有:
S1+μ1Reassign+μ2Insert=S2
S2-S1=μ1Reassign+μ2Insert
将两解间变化所需基础操作的次数定义为两解间的编辑距离ΔS1,S2,则有:
ΔS1,S2=|S2-S1|=μ1+μ2
需要注意的是,由于将解S1变化为解S2所需的操作次数与将解S2变换为解S1所需的操作次数可能不一致,因此ΔS1,S2≢ΔS2,S1。
2.2 基于出行偏好的初始解生成算法
本文提出基于从历史数据中总结的出行偏好的初始解生成算法。初始解的生成关系到算法的收敛速度,并且会在很大程度上影响算法最终的收敛结果。在动态公交问题中,由于订单生成的随机性,当前时间片的最优路径可能不利于后续订单的接收,因此需要一定的设计来使得算法生成的路径能尽可能地满足未发起订单的需求[15]。尽管在动态公交问题中订单的生成是随机的,但在实际场景下,这种随机并非是无规律的。在某一地区,订单的生成一定是遵循某种规律的,这也是智慧交通领域研究的课题之一[28],但这种规律的探索不在本文的研究范围之内,下述初始解生成算法将基于已有的出行偏好。出行偏好的表示形式是一个以公交站点为行索引和列索引的矩阵,矩阵中的元素表示行索引所对应的公交站点出发到列索引所对应的公交站点的出行偏好。
近年来,基于数据的预计算路径集方法逐渐受到研究者的重视[29]。本文提出了将出行数据归约到路网,并通过对路网进行扫描生成备选路径集的路网扫描算法。该算法可以分开利用带权路网上的点信息与边信息,也可以将点信息与边信息进行加权综合利用,得到符合要求的备选路径。其中:点信息是指公交车打卡上车数据、住宅区居民人数、商圈人流量及蜂窝网络网点使用人数等,描述一个在给定问题规模下可被抽象为一点的区域的与动态公交问题中需求数具有直接关系的信息;边信息是指以各种方式统计或计算得到的两服务点间的客流量,或出行轨迹数据集中两服务点相邻的次数。
下面将介绍路网扫描算法的具体流程。路网扫描算法基于深度优先遍历算法,首先选定初始节点,随后从初始节点向其邻居节点延伸路径,若路径各边的访问概率之和大于路径访问次数下限a,则将其加入结果集;若路径长度超过从初始节点到路径末端节点的最短路径距离的b倍,则不继续延伸该路径。具体算法流程见算法1。
算法1路网扫描算法
输入点集V,V上的边集E,E上的边访问次数P,E上的边长度L,路径访问次数下限a,路径绕路上限b
输出预计算路径集R
1)初始化预计算路径集R。
2)从V中取出一个未访问过的点v。
3)初始化栈结构stack,将一条仅含v的路径压入栈。
4)从栈stack中弹出顶元素,记为路径r。
5)检查路径r上各边的访问次数之和,若该和大于路径访问下限a,则将路径r加入预计算路径集R。
6)取r的最后一个访问节点的未访问过的邻居节点u。
7)记在访问完路径r的所有节点后,再访问节点u的路径为路径r′,若路径r′中所有节点间沿路径的距离均不超过其在地图上的距离的b倍,则将r′压入栈stack。
8)若路径r的最后一个访问节点尚有未访问过的邻居节点,回到步骤6)。
9)若栈stack非空,回到步骤4)。
10)若V中还有未访问过的节点,回到步骤2)。
11)算法结束。
在后续的PSO算法中,通过在预计算路径集中检索出全部对当前订单可行的路径,并以每条路径的长度除以全部可行路径的长度之和作为各路径被选中的概率,通俗来说,在路径均有较高概率满足较多需求的情况下,路径越短,被选中概率越高。设预计算路径集为R,则其中一条路径r被选中的概率为:
2.3 分层自适应变异记忆PSO算法
上文引言中提到,在将PSO算法应用在动态公交问题上时存在以下问题:
1)在动态公交问题中,由于车辆数、地图中存在的可访问点以及同时存在的订单数较多,因此问题解空间较大、等价状态较多,基础的PSO算法难以平衡探索与利用的过程。
2)使用不完全随机的初始解算法固然可以提高收敛速度,但可能将粒子解局限在特定区域,使得粒子解缺乏随机性,容易收敛到局部最优。
3)动态公交需要在多个时间片上重复计算具有相似订单的车辆的最优路径,尤其是PSO算法迭代轮次多、计算耗时长,容易在高峰期不能及时求解。
针对以上问题,本文提出根据动态公交问题的解的结构将粒子解进行拆分,并将路径层的结果保存复用,同时使当前时间片中的其他粒子和之后时间片的粒子计算在继承、复用之前计算结果的基础上缩短计算时间;此外,引入连续空间PSO算法所常见的两大PSO算法的改进,即自适应参数和变异机制,将其推广到离散空间,以缓解算法早熟和收敛到局部最优解的问题,从而提出了分层自适应变异记忆PSO算法。
算法2分层自适应变异记忆PSO算法
输出未接订单集O中各订单在车辆集上的分配情况D,车辆集中各车辆b的节点访问顺序rb
1)生成N个订单层粒子。
2)将所有未接订单逐一随机分配得到一个订单层初始解,重复N次即可得到N个O的分配。
5)根据2.3.2节粒子更新规则更新路径层粒子直至迭代轮次达到算法设定次数。
6)根据2.3.2节粒子更新规则更新订单层粒子直至迭代轮次达到算法设定次数,返回订单分配情况和该分配情况下各车辆的路径。
下面,本文将分别介绍动态公交粒子群分层方法、粒子解的更新规则和变异规则。
2.3.1 动态公交粒子群分层方法
上文定义了动态公交问题的解S由两部分构成:订单在车辆间的分配情况D,给定车辆的节点访问顺序Rb。粒子群分层方法的核心,就是将D的求解与Rb的求解过程分离,并对Rb的求解结果进行分类、保存、重用和继承,从而减小问题的解空间和时间复杂度,加快搜索速度,减少计算时间。
在同一时间片的不同粒子解之间,以及在不同时间片下的粒子解之间,都有很高的概率会存在两车所接的订单种类的集合相同或相近。为避免重复计算,考虑根据一定原则对车辆的解Rb进行分类,下面将依次给出订单和车辆的种类的定义。将订单的种类Θo定义为仅由其起点与终点决定的变量,若起点在计算时已经过,则将起点设为空。以
ΘO={Θo,∀o∈O}
将车辆的种类Θb定义为其已接订单集的种类,则有:
设有粒子初始化方法Init,粒子群求解过程为PSO,该过程接受一个初始解和一个新增订单集作为参数。历史订单集为O,新增订单集即分配集为A,所有已发生计算订单集及其对应的路径层粒子群构成字典D,则可将分层PSO算法表示如下:
由此,可以将一个订单种类集合所对应的粒子群及其最优解保存在以订单集为键的字典D中。在计算具有相同类型订单的车辆时,可以调用之前记录的最优解,在其基础上进行计算,大大节省了计算时间。在没有对应解时,再根据2.2节所述方法生成路径层初始解。
2.3.2 粒子解的更新规则
在每个时间片中,算法将当前订单池中订单随机分配生成订单层初始解,再根据2.3.1节所述规则生成路径层解,每个路径层粒子的解代表一辆车在给定订单集下的一条路径,路径的终点是距最后一名乘客下车点最近的可用停放点。在此基础上,根据本小节规则更新路径层粒子群,迭代直至达到迭代停止条件。此时,每个订单层粒子的解的代价是该订单层粒子对应的路径层粒子的解的代价之和,随后订单层粒子再根据本小节规则进行更新。每次更新时如产生已计算的路径层粒子解构成的字典D中不存在的订单情况,则根据2.3.1节规则生成新的车辆路径解Rb并加入字典D。
设v为订单层或路径层粒子的速度,x为订单层或路径层粒子的当前解,x′为订单层或路径层粒子的加速解,x″r为路径层变异解,x″o为订单层变异解,xglobal为订单层或路径层粒子的全局最优解,xhistorical为订单层或路径层粒子的历史最优解,σ0、σ1、σ2为3个0～1的随机数或固定为1,w为惯性系数,α、β为学习率,γ为变异率,则粒子更新公式为:
v=σ0wv0+σ1α(xglobal-x)+σ2β(xhistorical-x)
(22)
x′=x+v
(23)
x″r=x′+γ|Rb|Insert
(24)
x″o=x′+γ|O|Reassign
(25)
其中:式(22)为速度更新步;式(23)为位置更新步;式(24)、式(25)为变异步。
在连续空间的PSO算法中,存在一类被广泛应用的粒子群范式——自适应变异粒子群。其中,自适应指的是速度更新步的参数w、α、β会随着迭代进行一定的变化,变异则是指变异步中γ不恒等于0,会在一定条件下使粒子变异,跳跃至离当前位置较远的解,避免出现多个粒子在一个较小的解空间中探索,而其他解空间区域中则缺乏探索,从而导致PSO算法陷入局部最优的情况。为将自适应变异机制引入离散空间,作出如下定义:
w=0.5-0.003hnow
(26)
(27)
βx=hnow-hhistorical+1
(28)
(29)
式(26)中的hnow表示当前轮次,该式表示惯性系数会随迭代轮次提高而减小;式(27)表示距离最优解越远的解将会越快地向最优解迭代;式(28)中的hhistorical表示该粒子上次刷新最优解的轮次,该式表示离上次取到局部最优解的时间越久,局部最优解对当前解产生的影响越大;式(29)中的count函数接受一个表达式作为输入,返回符合该表达式的粒子个数,该式表示粒子群越密,随机扰动概率就越大,有助于粒子群在收缩至局部最优后跳出。
3 实验结果分析
本文实验分为3个部分:1)在真实日订单集上选取6个连续的时间片,检验本文提出的分层PSO算法对比单层PSO算法在时间上的优势;2)构建小规模订单集,在充分迭代的前提下进行消融实验,对本文针对动态公交问题改造的自适应机制和变异机制对算法的收敛过程及最终结果的影响进行分析和比较;3)在完全仿真环境中,限制计算时间在真实计算时间的要求内即5 s内处理当前时间片的所有订单,至多约200条订单,使用区域真实日订单集对本文算法及PSO算法、贪婪插入(GI)算法、VNS算法、蚁群(AC)算法和固定公交进行比较,并分析本文算法的有效性。
3.1 实验环境设置
本文实验环境基于重庆市北碚区蔡家岗街道的道路搭建,蔡家岗街道人口约16.45万人,面积约45.75 km2,使用蔡家岗街道范围内的80个公交车站作为图结构的节点,构建公交站点间202条有向边,使用公交车站间的最短路径的实时通行时间作为动态道路图结构的边长度,并采用重庆市公交4.38亿条历史GPS数据生成动态道路图、3 940.7万条历史打卡数据生成出行数据集,作为预计算路径集的输入数据。在实验区域,公交运营时间为05:00—23:00,动态公交服务器每10 s响应之前10 s的所有订单,即一个时间片为10 s,全天共6 480个时间片。单时间片实验截取了一个有32个新加入订单的时间片;部分时间片实验截取了6个时间片进行实验;全天仿真实验使用数据集中一天约50 000条真实出行需求作为订单集,该订单集中订单的平均里程为6.4 km,当天固定公交平均行驶速度为20 km/h。采用当地公交公司139辆所有在库公交车作为车辆上限,并设置每车同时接受的订单数至多为公交车的实际座位数31座。本文的实验运行于Inter 12700CPU和Win 11系统,算法采用Python 3.10进行开发,主要调用了numpy包。
3.2 实验参数与指标设置
根据模型的目标函数,动态公交在运营过程中主要关心4个指标,即接单率、乘客候车时间、乘客在车时间和运营里程。在本文的实验结果中也将体现这些运营指标,并设置最大可用车辆数这一参数用于体现所需的司机工时。在本文算法及各对比算法中,为保证最坏乘客体验,设置了每个订单的最长在车时间为1.2倍的直接从订单出发地到目的地的预计时间。对除固定公交以外的算法均设置了订单等待接单时间窗,订单发起后的10 min内若仍无法将订单分配给车辆,则自动拒绝订单。
经使用不同系数测试,将改进PSO算法与原始PSO算法的初始惯性系数设为0.5,静态全局学习系数设为0.4,静态局部学习系数设为0.2。限制本文算法、原始PSO算法、变邻域搜索算法和蚁群算法的迭代轮次最多为100轮。设改进PSO算法的路径层在检索到相同解时的迭代轮次,即图2中的“较少次数”为20轮;无相关解时的迭代轮次,即图2中的“较多次数”为100轮。
3.3 分层粒子群对算法计算时间的影响分析
本文针对原始PSO算法计算耗时较长的问题,结合动态公交问题的解包含两部分的特点,以及动态公交问题在不同时间片之间路径层的解具有可复用、可继承性的特点,提出了分层PSO算法。分层PSO算法在单时间片内能复用车辆种类一致的车辆粒子解的结果、继承车辆种类相近的粒子解、加速新粒子求解过程,并能在不同时间片间复用、继承,从而减小PSO算法的开销。本文截取6个时间片用于对比分层与不分层PSO算法的实验,实验结果如图3所示。实验结果表明,在动态公交问题中将粒子解划分为多层可以有效节约单时间片及跨时间片的计算时间开销,整体上降低了PSO算法的计算开销。
图3 多层与单层PSO算法在多时间片下的计算时间Fig.3 Calculation time of multi-layer PSO algorithm and single-layer PSO algorithm under multiple time slices
3.4 自适应变异机制对算法收敛过程和结果的影响分析
本文通过提出编辑距离的概念将连续空间中的自适应变异机制引入离散空间。为研究自适应变量和随机扰动变异机制的作用,设计了基于单个时间片的消融实验用于测试这两点改进的有效性,结果如图4、图5所示。
图4 自适应变异机制对算法收敛的影响Fig.4 The impact of adaptive mutation mechanism on algorithm convergence
图5 自适应变异机制对算法结果的影响Fig.5 The impact of adaptive mutation mechanism on algorithm results
实验结果显示:在对算法收敛过程的影响上,随机扰动算子能有效扩大算法的搜索范围,而动态参数可以在收敛早期加快收敛速度,随后有效避免算法早熟;在算法结果上,仅使用随机扰动在所选实验参数下,算法反而过快收敛于局部最优,动态参数的使用则能有效提高算法的性能。
3.5 全天时间片实验数据分析
为充分验证本文算法的有效性,在全天时间片真实订单集上进行了实验,并与原始PSO算法、GI算法、VNS算法、AC算法和固定公交进行比较,实验结果见表1。
表1 全天时间片实验结果Table 1 Whole day time slice experiment results
表1结果显示:固定公交在运营里程方面具有优势,但在不允许超载的情况下,大量乘客需要进行超长时间的等待才能上车,或由于运营时间结束也未能上车而被被动拒单;在设置的100轮迭代过程中,原始PSO算法所求得的路径较差,而蚁群算法所求得的路径较优,但满足的订单数相对较少;相较于GI算法、VNS算法,本文算法在高接单率、低运营里程的前提下,在乘客体验方面也仍有较好的表现,具有相当的实用价值。
本文算法、PSO、VNS和AC算法均有迭代过程,因此可能运行时间较长,故限制算法的最大迭代轮次为100轮。在全天时间片上,上述4个需要迭代的算法运行时长统计见表2。
表2 全时间片运行时长对比Table 2 Full time slice runtime comparison 单位:s
表2结果显示,本文算法在运行时长方面相对其他需要迭代的算法具有一定的优势。在最长单时间片计算时间上,PSO、VNS和AC算法均超过了10 s,由于算法运行中单时间片需要响应在该时间片的10 s内的所有订单,单时间片运行时间超过10 s实际上表示该算法无法适用于该片区的动态公交问题,而本文算法能在10 s内完成响应,因此具有实用价值。
4 结束语
本文针对城市公交的新模式——动态公交,具体地分析了它所涉及的限制条件,并构建了模型。随后,本文针对动态公交问题搜索范围大、易陷入局部最优等特点,引入了PSO算法对其进行求解。本文针对动态公交问题的解空间是离散空间的情况,提出了解的编辑距离的概念,并在此基础上设计了新的动态收敛系数和随机扰动系数;针对动态公交解具有两部分的特点,创新性地提出了分层粒子群,并提出路径层粒子的复用和继承方法。最后,本文设计了3类实验,分别测试、对比了算法的计算效率和结果收敛性。5个时间片上的实验结果表明,本文提出的粒子群分层、复用、继承机制能降低算法80%的计算耗时;单个时间片实验结果表明,引入的自适应变异机制能有效优化算法的收敛过程,避免算法早熟现象、避免陷入局部最优;全天时间片实验结果表明,本文算法相较于固定公交能在同等运力限制下,提高22%的乘客接单率并节省39.1%的乘客出行时间,相较于其他算法,本文算法平均缩短85.3%的计算用时,降低20%里程数,并提高超12%的接单率。整体结果表明,本文算法能够满足当前动态公交运营的需要。在未来的研究方向上,可以尝试结合其他启发式算法设计混合算法对动态公交问题进行求解,从而进一步提升求解速度和准确性。
