基于模拟退火算法的公共自行车调度优化问题

岳晓鹏 全启圳 何月华

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

1 问题背景

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

目前，针对公共自行车调度方面的研究较少。蒋塬锐[1]等针对共享单车供需失衡、共享率低等困难，提出了目标为最小成本的共享单车静态调度模型，并利用单亲遗传算法求解。李明明[2]对公共自行车的运营和调度进行研究，基于大数据的数据归纳，研究公共自行车的时间特性和周转特性，并选用改进蚁群算解决调度模型。冯炳超、吴璟莉[3]提出基于单亲遗传算法的求解方法，利用大量的模拟数据和真实数据，求解自行车共享系统静态再平衡问题的有效方法。卢琰[4]结合不同时段共享单车的分布特点，构建混合轴辐式共享单车网络结构，提出有调度任务时间范围和无调度任务时间范围的调度优化模型，并利用遗传算法对模型验证进行求解。本文在分析完公共自行车调度问题及调度影响因素后，将公共自行车的调度问题类比为旅行商问题，设计了基于旅行商问题的0-1 规划数学模型。并运用模拟退火进行模型的求解。

2 模拟退火算法的基本原理

模拟退火算法（Simulated Annealing，SA）是1953 年由N.Metropolis 等人提出的，后来经Kirkpatrick 等人推广后得以广泛应用[5]。SA 模拟物理固体退火的冷却降温过程，从某一很高的温度出发，随着温度的下降，按照Metropolis 准则，结合概率突跳特性在解空间中随机寻找全局最优解，即局部最优解可以概率性地跳出并趋于全局最优解。

模拟退火算法的求解流程：

Step1：随机产生出初始解X0，使Xbest=X0，并计算目标函数值E（Xbest）；

Step2：给定初始温度T0及各参数包括降温系数kr 终止温度Tend 每个温度的迭代次数Iter，且T=T0，i=1；

Step3：基于当前最优解Xbest邻域函数产生新解Xnew，计算新解的目标函数值E（Xnew），并且计算目标函数值的增量，∆E=E（Xnew）-E（Xbest）

Step4：如果∆E＜0，则Xbest=Xnew，即接受新解为当前最优解；

Step5：如果∆E＞0，则接受概率为p（∆E）=exp（-∆E/T），然后以rand 产生[0，1]区间上随机数，若rand＜p（∆E），则Xbest=Xnew，即接受新解为当前最优解，否则放弃此新解，之前的Xbest仍然为最优解；令i=i+1；

Step6：判断i≤Iter，如果满足此条件，则重复进行步骤Step3～Step5，否则继续进行下一步；

Step7：冷却降温T=kr·T，i=1；

Step8：判断终止条件T≤Tend，如果满足该条件，则停止计算，输出最优解Xbest否则返回步骤Step3 继续计算。

3 模型的建立和求解

3.1 公共自行车的调度选取

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

表1 部分驻放点编号

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

3.2 模型假设

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

（1）在研究对象范围内，仅设立了一个车场和一个调度车；

（2）调度车必须经过每一个停靠点，并且每一个停靠点仅能经过一次；

（3）调度车没有时间和速度限制，正常行驶；

（4）调度车调度过程中，公共自行车辆始终保持充足且不超过最大载重。

3.3 模型的建立

针对旅行商问题，目前的学术界的普遍观点是：旅行商问题是一个NP 难题，除非当P=NP 时，否则求解旅行商问题并不存在一种行之有效的精确算法. 因而我们只能找到一些在某些方面接近最优解的解决方案[7-8]。

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

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

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

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

3.4.1 模拟退火算法的求解

由于当地居民的对于公共自行车的需求，为了更好、更快的使得公共自行车系统能够较好的承受每日的需求，现确定20、40 和60 个驻放点依次进行仿真实验完成调度问题。

这里设置算法参数，初始温度T0=1000℃，终止温度Tend=0.001℃，降温系数kr=0.97，迭代次数Iter=454。由于该方法得到的一般为近似解，因此每种情况执行5 次并统计该情况下的最短总距离及求解时长，如表3 所示。

表3 不同数量驻放点下的模拟退火5 次求解

通过上表可以得到，在模拟退火算法下，20、40 和60 的这3种情况下的最短距离依次为8.49、19.06 和22.04km。

3.4.2 模拟退火算法的应用

在实际情况下，由于时间限制，一辆调度车负责的驻放点不会太多，这里以30 个驻放点为例进行模拟求解，结果如图1 和图2 所示。

由图1 可以看出，迭代次数在50 以内，下降速度快，而在50～140 时，状态保持平稳，当150～275 时，再次下降且比前期幅度大，直至320 以后处于平稳状态。

图1 每次迭代最短路径图

从图2 可以得到，该模型求解的最优调度运输路线为：

图2 最优调度路线

1→4→5→6→7→17→8→9→10→11→12→25→24→23→18→21→20→22→29→30→28→27→26→19→15→16→14→13→3→2→1

因此，从调度车停车场出发到最后回到起点，依次经过4，5，6，…，3，2，其优化总距离为13.08km，计算求解耗时38.99s，求解速度较快。

4 灵敏度分析

针对模拟退火算法的参数设置，初始温度越高，调度路径的变化程度就越大，容易导致出现较差的解，而终止温度则作为算法停止的平衡条件，一般温度较低。当初始温度相对较高时不利于算法的收敛，过低时不利于计算效率导致迭代的过高。降温系数控制着温度变化的快慢，数值越小，降温越快，过早的结束算法不利于最优解的寻优。这里继续选用30 个驻放点来对初始温度、终止温度及降温系数进行研究对比分析，结果如表4 所示。

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

通过上表数据可以看出，当提高初始温度时，求解时间变长，但所得最优距离相对略大。对于终止温度，随着设置温度的上升，求解速度越快，但其最终结果并没有0.001 时好，最优距离变远。针对降温系数，系数的上升并没有得到更好的解，反而延长了求解的时间。最终得到当初始温度1000℃，终止温度0.001℃，降温系数0.97 时，最短路径距离13.08km。

5 主要结论

本文主要是研究公共自行车的调度问题，通过将公共自行车的调度问题类比转化为旅行商问题，从而构建出了调度车的调度路径的优化模型，再利用模拟退火法算法求解该模型并加以分析，得出以下结论：

对于大多数的智能算法都容易陷入局部最优，本文利用模拟退火算法有效的避免陷入局部最优解，因此模拟退火算法能有效地解决本文提出的调度路径优化模型。又因模拟退火算法受各种参数的影响过大，所以对初始温度，终止温度和降温系数进行灵敏度分析，做参数设置的相关研究，最终确定了本次模拟退火算法所用的参数大小，从而得到了较为满意的运算结果。