基于模拟退火算法的共享单车城市配送路径规划

康雯轩

（燕山大学经济管理学院，河北 秦皇岛 066000）

自行车共享企业在校园、地铁站、公交站、住宅区等提供服务，其可以有效地解决市民在其出行过程中最后一公里的问题，与其他公共交通组合，共同完成市民出行的整个链条。自行车共享也是一种新型的绿色环保共享经济。

车辆路径优化是DANTZIG 等[1]提出的，其后出现了集合分割的方法，可以将整个路径集合进行分割，创建了最初的VRP 模型[2]，此后李军[3]通过启发式的方法求解了VRP 问题，张海刚等[4]使用PSO 算法求解带软时间窗的VRP 问题。雷洪涛等[5]构建了智慧物流路径优化的模型。王超[6]根据城市配送同时取送货的车辆路径问题、带时间窗的同时取送货的车辆路径问题和配送网点优化的车辆路径问题，给出了智能启发式求解算法。

由于城市内大量共享单车的存在，导致了城市拥堵、道路上共享单车摆放无序等问题，许多学者开始研究如何在共享经济的环境下研究城市合理治理。王婷等[7]提出通过使用奖惩机制和押金的合理规划管理来合理规划共享单车。周建高[8]针对上述城市治理问题提出对于公共场所的共享单车存放点实行缩小规模增加存放地点的观点。本文针对建立城市集中配送管理中心来进行城市共享单车的集中管理与配送。

1 建立模型

在本文运输网络中，包括了共享单车存放点和线路，其中每次共享单车配送量不能超过配送车辆的最大载重量。并且每辆共享单车配送车辆由共享单车配送中心出发，完成配送任务后，返回共享单车配送中心。

1.1 符号设定

1.1.1 参数符号

设有n个共享单车存放节点，每个共享单车存放的需求量为q（ii=1，2，…，n）；有m辆配送车辆（型号种类完全一致），每辆车的最大载重量为Q。客户i到客户j的距离为dij，o表示配送中心，则共享单车配送中心到共享单车存放的距离为doi（i=1，2，…，n）。由于一条线路上所有共享单车存放由一辆车进行配送，所以要求考虑货损量的前提下，每条线路共享单车存放需求量之和不超过每辆车的最大载重量。

K：配送中心车辆集合，K=1，…，m；

co：车辆单位里程的行驶费用；

cv：单辆车的一次出车固定成本；

vo：车辆匀速行驶时的速度；

tij：车辆从客户i到客户j的行驶时间；

Q：配送车辆的最大载重量；

T：在各共享单车存放点的装卸货时间；

β1：在运输过程中单位时间内的损耗比例；

β2：在运输过程中因路况因素造成的共享单车损耗比例；

β3：在共享单车存放点装卸过程中单位时间内的损耗比例；

β4：在共享单车存放点装卸过程中因装卸操作导致的损耗比例；

uijk：配送车辆k在路径i到j上行驶时的载重量；

p：单位重量货损价格；

fv：单次配送任务中，配送中心派出的送货车辆总数；

fT：单次配送任务中，所有配送车辆行驶里程数总和；

fD：单次配送任务中，所有配送线路上产生的货损量总和。

1.1.2 决策变量

1.2 模型建立

本文中的模型考虑了车辆使用数量、总行驶里程和运输共享单车不当而导致的耗损，并且通过3 个成本权重因子加权得到总成本。其中约束保证每个共享单车存放点的需求量需全部满足，同时每个共享单车存放点只能有一辆车进行配送，配送不能超出共享单车派送车辆的最大载重量，配送完后返回共享单车配送中心。

2 算法设计

2.1 模拟退火算法

模拟退火模仿了金属退火的过程，其内循环使用Metropolis 法则，通过一定概率接受相对劣解，此方法可以有效跳出局部最优，从而得到全局最优，外层则是降温的过程，具体步骤见算法流程设计。

2.2 算法流程设计

步骤1：令T=T0，即开始退火的初试温度，随机生成一个初始解S1，并计算相应的目标函数值E（x0）。

步骤2：令T等于冷却进度表中的下一个值Ti。

步骤3：根据当前解xi进行扰动，产生一新解xj，计算相应的目标函数值E（xj），计算两者之差。

步骤4：若df<0，则接受S2 作为新的当前解，即So1=So2；否则，计算So2 的接受概率exp（-df/T），随机产生（0，1）区间上均匀分布的随机数rand，若exp（-df/T）＞rand，也接受S2 作为新的当前解So1=So2，否则保留当前解So1。

步骤5：在温度Ti下，重复L次的扰动和接受过程，即执行步骤3 和4。

步骤6：判断T是否已达到了Tend，如果是，则停止，否则继续。

本文算法流程图如图1 所示。

图1 算法流程图

3 实验计算

3.1 问题数据

通过调查得出北京48 个共享单车存放点的需求，并且以北京国际机场为中心，将共享单车存放点的坐标计算出来。

实验数据如表1 所示。

表1 实验数据表

表1（续）

对于调查的配送中心的车辆参数已知：配送中心坐标（97，297），车辆总数为14 辆，单位行驶费用为1 元/km，车辆一次出行固定成本为150 元/辆，平均行驶速度为40 km/h，最大载重量为1 000 kg。运输过程损耗比例为0.8%，路况损耗比例为0.1%；装卸过程中损耗比例为0.2%，装卸操作损耗比例为0.2%。

3.2 实验结果

本文实验环境为2 GHz，8 GB RAM，采用MATLAB 编程。本文的数据实验结果如图2 所示。

图2 VRP 配送路线图

图3 给出了模拟退火求解结果的目标函数优化曲线。目标函数最优值值在第1 000 代即从最初的5 300 元下降到最小值2 800 元，显示了良好的收敛效果。目标中的车辆损耗降低了26.03%，由此可见本模型可以大幅降低损耗的浪费。通过实例可以看出，模拟退火算法在计算实例过程中表现良好。计算结果如表2 所示。

图3 算法迭代次数图

表2 实验结果

本文设计的算法与搭建的模型可作为共享单车企业配送车辆路径规划工具，可灵活求解企业中不同情况问题，具有较高的实际应用价值。