基于粒子群算法的公共自行车调度优化问题

岳晓鹏，全启圳，何月华

（许昌学院 数理学院，河南 许昌 461000）

1 问题背景

近年来，公共自行车作为一种新的交通方式，得到了越来越多人的支持与认可。公共自行车在使用过程中不会对环境形成任何污染，节能环保，与此同时，随着广大市民环保认识的提升，大家逐渐更注重生活品质，更愿意选择健康绿色的交通方式，共享单车这一交通方式的出现在某种程度上满足了人们对于绿色出行的需要。

目前，针对公共自行车调度方面的研究较少。蒋塬锐[1]等针对共享单车供需失衡、共享率低等困难，提出了目标为最小成本的共享单车静态调度模型，并利用单亲遗传算法求解；赵曼[2]对共享单车网络，采用社会网络分析法，提出了特征量和凝聚子群，得到了共享单车的局部最优网络结构，并基于此提出调度路径最优方案；周传钰[3]结合共享单车的特点，考虑了轨道交通站点接驳区域的单车投放规模，提出调度最优模型；卢琰[4]结合不同时段共享单车的分布特点，构建混合轴辐式共享单车网络结构，提出有调度任务时间范围和无调度任务时间范围的调度优化模型，并利用遗传算法对模型验证进行求解。还有一些学者利用粒子群算法在智能机器人路径规划、交通路线设计、物流线路规划等方面开展了应用研究[5-9]。

本文在研究公共自行车调度问题及调度影响因素后，将公共自行车的调度问题类比为旅行商问题，设计了基于旅行商问题的0-1规划数学模型，并运用粒子群算法进行模型的求解。

2 粒子群算法的基本原理

2.1 粒子群优化算法

粒子群优化算法（Particle Swarm Optimization，PSO）在1995年由Kennedy和Eberhart提出。该算法源于对鸟类捕食行为的研究[10]。粒子群算法首先随机地初始化一群均匀分布在给定的寻优空间中的粒子（种群规模一般为30个），然后所有的粒子根据2个极值来更新自身的速度：一个是个体极值P；另一个是群体极值g。设粒子群中粒子的总数为N，粒子的维数为m，算法的终止条件（即最大迭代次数）为M，第i个粒子在t时刻的飞行速度以及位置分别为vi（t）=[vi1（t），vi2（t），...，vim（t）]T和xi（t）=[xi1（t），xi2（t），...，xim（t）]T，而对于粒子在t时刻的个体极值表示为pi（t）=[pi1（t），pi2（t），...，pim（t）]T，同样可以得到群体极值表达gi（t）=[gi1（t），gi2（t），...，gim（t）]T，因此所有的粒子按照如下的更新方式在搜索空间中飞行以找到最优解。

其中：ω为惯性权重系数，c1为个体学习因子，c2为社会学习因子。

2.2 粒子群算法的求解流程

Step1：设置种群规模、变量范围、惯性权重、学习因子等参数，并随机地初始化一群均匀分布在给定的寻优空间中的粒子（包含速度和位置信息）。

Step2：计算群体中各个粒子的适应度值，设置第i个粒子的适应度值为它的当前个体极值pi，所有粒子中的最好粒子设置为群体的全体极值g。

Step3：根据公式（1）、（2）更新每个粒子的速度和位置。

Step4：对所有粒子，将其当前的函数值与它以前找到过的最好位置进行比较，如果当前位置较好，则将个体最优位置pi设置为这个粒子的位置，然后再对群体的全局极值g更新。

Step5：判断给定的终止条件是否满足。若满足终止条件，停止搜索，输出需要的结果；否则，返回Step3继续搜索。

3 模型的建立和求解

3.1 公共自行车的调度选取

本文主要是研究许昌市东城区的公共自行车调度问题，因此搜集30个公共自行车驻放点的地理坐标，并计算出各个驻放点之间的距离，即各个驻放点的地理坐标见表1，其之间的距离见表2（由于驻放点较多，仅展示部分数据）。

表1 部分驻放点编号

表2 各个驻放点间的距离 单位：km

3.2 模型假设

为将该调度模型转化为数学模型，进行模型假设，保证一定的准确性。

（1）在研究对象范围内，仅设立了1个车场和1个调度车。（2）调度车必须经过每一个停靠点，并且每一个停靠点仅能经过1次。（3）为保障能较好地完成调度，行车速度在40 km/h，装或卸载3 min。（4）调度车调度过程中，公共自行车辆始终保持充足且不超过最大载重。

3.3 模型的建立

3.3.1 公共自行车的路程规划

本文将调度问题视为0-1规划问题，建立旅行商问题的数学模型。首先，需要确定停靠点i和停靠点j是否连通，即调度车辆从路线xij上经过记为1，否则记为0。

又有调度车辆最短路径问题，目标函数取最小值，对所有存在调度车经过的路径xij=1的距离dij求和，为此得到以下规划模型：

基于问题的假设和实际的调度情况，本文对目标函数进行了一定的约束，其（4）（5）式表示调度车必须经过每一个停靠点，并且每一个停靠点仅能经过1次；（6）式表示所有的停靠点能且只能作为路线起点和终点各1次。

3.3.2 公共自行车的调度耗时计算

针对运输车在调度的过程中，消耗的时间主要花费在路线耗时和装卸自行车上，因此可以得到运输用时条件：

针对调度用时的计算，运输过程的耗时由（7）式表示，而（8）式则表示装或卸载公共自行车的时间，最后由（9）式得到总的时间。其中e为每个驻放点的装或卸载的平均耗时。

3.4 基于智能算法下的模型求解

由于居民对于公共自行车的需求时刻和数量是随机的，为了更好、更快地进行调度，使得公共自行车系统能够较好地承受需求，先选择15个驻放点依次进行仿真实验完成调度问题。模型中的个体学习因子c1=1，社会学习因子c2=0.1，惯性因子ω=0.2，惯性因子最大值ωmax=1，惯性因子最小值ωmin=0.2，粒子数量N=500，迭代次数M=1 000进行求解，如图1和图2所示。

图1 15个驻放点各代最短距离与平均距离对比图

图2 15个驻放点粒子群算法优化路径图

从图1可以看出，迭代次数在75以内，下降速度快，而在75次以后，状态保持平稳，但对于各个粒子的平均距离，在1 000次迭代内始终处于保持下降趋势与最短距离存在一定的间距。

从图1可以得到，该模型求解的最优调度运输路线为：1→2→3→13→14→15→4→7→8→10→11→12→9→6→5→1。

因此，从调度车停车场出发到最后回到起点，依次经过2，3，4，…，6，5，其优化总距离为6.09 km，所耗费总时间为0.91 h。

4 灵敏度分析

针对粒子群算法的参数设置，个体学习因子c1，根据自身经验来计算粒子飞翔速度的权重；社会学习因子c2，根据自群体经验来计算粒子飞翔速度的权重；粒子数量N，粒子数越多，搜索能力越强；惯性因子，其值较大时，全局寻优能力强，局部寻优能力弱，反之相反。迭代次数，次数过少结束过早不易得到最优解，次数过大增大耗时，因此也不宜过大。本文继续选用15个驻放点来对初始温度、终止温度及降温系数进行研究对比分析，结果见表3。

表3 初始温度、终止温度及降温系数对结果的影响

通过表3数据可以看出，对于个体学习因子和社会学习因子，更多的是需要考虑自主的经验，其次较少考虑群体经验来进行计算；为了保障粒子在搜索的过程具有一定的效果且在一定的迭代效果下能有好的解，其粒子数量设置为500，迭代次数1 000较为合适；最后关于惯性因子的设置，通过表3可以看出，针对这一问题寻优能力的受参数的影响不大，因此依旧选择0.2作为模型初值。最终得到当个人学习因子1，社会学习因子0.1，粒子数量500，惯性因子0.2，迭代次数1 000时，最短路径距离6.01 km。

通过选取15个驻放点的数值模拟可以在适当的参数设置下，模拟效果良好，现使用这套参数进行实际计算，选用30个驻放点进行模拟调度，模拟结果如图3和图4所示，得到总路程为13.30 km，总耗时1.83 h。

图3 30个驻放点各代最短距离与平均距离对比

图4 30个驻放点粒子群算法优化路径

由于每天需要调度的驻放点的位置和数量不同，运输车的运输路线、路程以及所花的时间都有所不同，但完成调度时长一般不会超过2 h，否则，市民在无车可用或者无车位可放车时，都会降低对于公共自行车系统的满意度，因此在任务分配时，可以根据不同的站点位置及数量选择路线来完成任务。

5 结论

本文主要研究公共自行车调度车的路线运输以及工作效率的优化。主要选用旅行商问题中的路线规划模型以及依据车辆的平均速度、装卸速度等参数，利用粒子群算法对该模型进行求解，并进行了算法参数的灵敏度分析。

相比其他智能算法，粒子群算法的参数设置易于理解，且利用参数将粒子速度和位置的合理把握，可以很好地解决这一路径问题。但粒子群法一般要保证研究对象在30个以内才有较好的解，否则效果较差，而实际问题研究对象有时会超过这一标准，这时可以考虑将全部站点划分为多个工作区分别进行调度。