考虑时变风险的成品油二次配送路径优化

韦金银，郭琪，史彬，鄢烈祥

（武汉理工大学化学化工与生命科学学院，湖北武汉430070）

随着经济的快速发展，我国成品油需求量逐年增长。成品油在配送过程中往往需要经过医院、学校、小区等人口密集地区，一旦发生燃烧爆炸安全事故，后果不堪设想[1]，因此，在进行成品油二次配送时要综合考虑配送风险和配送成本。事实上，成品油二次配送已经成为影响石化企业利润的重要因素[2]，研究成品油二次配送路径优化问题，选择合适配送路径，降低成品油二次配送成本和风险、提高配送效率对石油石化企业具有重要的现实意义。

目前，国内外学者对成品油二次配送路径优化问题已开展理论与应用研究，Cornillier 等[3]建立了带时间窗的多车场成品油配送路径优化模型，运用启发式算法求解，并运用数组实验对算法的性能进行评估；Avella 等[4]研究了车辆有限、司机有限的成品油二次配送问题，结合分支定价算法，设计了一种快速求解的启发式算法，并用实例验证了算法的有效性；全自强等[5]针对成品油主动配送模式的新形势，利用百度地图API获取基于实时路况下的行驶时间，建立数学模型运用禁忌搜索算法进行求解，优化出来的配送路径可以提高车辆配送周转率；孙丽君等[6]建立了考虑司机工作量均衡的成品配送路径多目标优化模型，运用了改进的非支配排序遗传算法进行求解，基于实例求解分析，验证了算法的有效性，优化出来的配送方案，可以为企业提供决策支持，对于实际有类似问题有一定启发意义。

上述研究工作主要考虑了多车场、车辆与司机有限、实时路况、工作量均衡等因素进行研究，是属于传统的车辆路径问题（vehicle route problem，VRP）一类的问题[7-8]。实际上，成品油属于危险品，配送风险和成本都是影响成品油二次配送路径规划的重要因素，现有的研究鲜有考虑风险的因素，同时成品油二次配送风险和成本两者相互冲突，进行多目标优化研究具有重要意义。鉴于此，本文结合成品油配送过程的真实情况，考虑到配送风险和车速的动态变化，建立了考虑时变风险的成品油二次配送路径优化模型，提出改进的多目标列队竞争算法进行求解，以期为石化企业的成品油安全高效配送提供借鉴。

1 道路时变风险度量模型

图1 风险影响区域变化

成品油配送过程中，油罐车到站后卸油，载重量会减少，产生事故的影响随之减少，故成品油在配送过程中的风险是动态变化的，其风险影响程度可以定量地用如图1 所示的风险影响区域面积表示。

配送过程中，城市相同区域不同时间段的人群集聚程度不同，油罐车在不同时间段经过相同区域时风险量的大小不同，考虑到载重和人群聚集程度的动态变化，可将风险度量模型表示为式(1)[9-10]。

式中，RTij表示路径（i，j）上的Tij时段的风险量，次·人/km；pij表示路径（i，j）上事故的发生概率，次/km；wij表示油罐车运输过程中的载重量，t；wo表示油罐车最初的载重量，t；r表示路径（i，j）上风险影响半径，km；qTij表示路径（i，j）上Tij时段的人口密度，人/km2；Dij表示路径（i，j）上的距离，km。

2 时变人口密度和节点距离

2.1 时变人口密度获取

在上述风险度量模型中，人口密度是重要的参数之一，一天之内不同区域人口密度会发生动态变化，要准确获取实时人口密度难度较大。现有研究中是以随机的方式生成人口密度[10]，这种方式产生的人口密度数值并不准确，相应地降低了时变风险计算的有效性。为了更准确地评估时变风险，本文提出了使用百度热力图定量计算人口密度，主要流程如下。

①收集一天百度热力图的数据进行分析，在7:00—20:00 每时间间隔为30min 截取一张热力图，总截取27张热力图。

②用热力值（1～7）代表人群聚集程度，热力值越大表示人群程度聚集程度越大，根据区域内的热力值，划分为高热区（6～7）和次热区（4～5）[11]。

③可根据人群集聚程度对在7:00—20:00 这个时间段进行划分，划分的时间段为7:00—9:30、9:30—12:30、12:30—18:00 和18:00—8:00 这4 个时间段。

④把城市分成N 个区域，以城市平均人口密度为基础，不同区域在t时间段的人口密度计算公式如式(2)所示。

2.2 节点距离获取

百度地图开放平台为开发者提供程序接口，开发者可以根据自己的需求调用百度地图程序接口获取相关服务。本文运用百度地图WEB 服务的批量算路服务，根据起点和终点，批量计算两点之间的实际道路距离和耗时，Matlab环境中求两个点之间的实际距离相关代码如式(3)所示。

url='http://api.map.baidu.com/routematrix/v2/driving?output=json&origins=x1&destinations=x2&tactics=13&ak= 您的AK';

代码中x1和x2分别代表起点和终点的坐标。两点之间的来回距离并不相等，因为在实际道路中考虑了单双行道、是否禁止左右拐等因素，这样的距离更具有实际意义。

3 BP神经网络预测车速

城市交通错综复杂，车辆在相同路段不同时间段有不同的车速，车速的变化直接影响到配送风险和配送成本的度量，因此需要进行车速的预测。本文以历史车速数据为输入，建立BP 神经网络，预测各个时段车速，此网络隐含层神经元的输出如式(4)所示。

输出层的输出如式(5)所示。

式中，i ∈n，n表示输入层单元个数；j ∈o，o表示隐含层的单元个数；k ∈h，h表示输出层的个数；βij和βkj为连接权值；θj和θk为神经元阀值；xi为输入的历史车速，km/h；bj为隐含层输出值；yh为预测的车速，km/h；f(x)为传递函数。

4 配送模型和求解

4.1 问题描述

成品油二次配送主要是采用公路运输方式将成品油从油库运输到加油站的过程，其成品油配送路径优化问题描述如下。①每个加油站的需求量、油库到各个加油站的距离和各个加油站之间的距离已知。②油库的库存足够大，可以满足各个客户的需求，每辆车的载重量一定，都是同一种车型。③车的载重量大于任何一个加油站的需求量，一个加油站只能由一辆车服务，一辆车可以服务多个加油站。④车从油库出发，经过几个加油站完成配送后回到油库，而且每辆车有自己的服务时间窗，车最晚回到油库的时间不能超过时间窗。⑤每个客户只能被服务一次。

在满足上述条件下，同步考虑配送成本和配送风险进行成品油二次配送路径优化。

4.2 双目标优化模型

考虑时变风险成品油二次配送优化模型见式(6)和式(7)。

约束条件见式(8)～(15)。

式(6)和式(7)表示最小化配送成本和风险；式(8)表示每辆车的配送任务不能超过车的最大载重量；式(9)表示车辆从油库出发最后又回到油库；式(10)和式(11)表示每个加油站只能被一辆车服务；式(12)表示车辆最晚回到油库的时间不能超过T；式(13)表示车辆从加油站i 到加油站j 的时间关系；式(14)表示车辆早到和晚到的惩罚关系式；式(15)表示车辆在运输过程中载重量的变化关系式。

4.3 车速时变性分析

根据路网把路段分成高速路段和主干路段，按照车辆一天速度的变化分成n个时段，各个时段表示为[T1,T2,…,Tn]，车辆在路段(i,j)车速有两种情况：①车辆通过路段(i,j)时，恰好在第Tm个时间段内，那么车辆在路段(i,j)的车速只有一种车速为②车辆通过路段(i,j)跨过了2 个及以上时间段时，则车辆的行车速度具有两个以上的车速，车辆在第m 个时间段内先以车速行驶，依此类推，到第Tm+n时段后以车速vTm+nij行驶，相应行驶距离为。综上，车辆从加油站i 到加油站j 的时间可表示为式(16)。

根据一天内人群的群聚集程度变化情况，划分为m 个时段，各个时段表示为[Tt1,Tt2,…,Ttm]，车速的变化引起tij的变化，会导致车辆在路段(i,j)经过不同的时段,同上，车辆在路段(i,j)上Tij时段的人口密度可表示为式(17)。

4.4 算法设计

列队竞争算法（LCA）是一种并行搜索、多层竞争的全局优化搜索算法，已经成功应用于求解流程工业间歇生产调度和化工过程模拟等多种优化问题[12-14]。考虑时变风险成品油二次配送路径优化问题是双目标优化问题，针对这类问题使用多目标列队竞争算法（MOLCA）求解，可以快速得到分布均匀的Pareto 最优解[15-16]。本文在MOLCA 基础上，引入非支配排序和拥挤度排序来分配家族搜索空间，在选择父代家族无性繁殖后代时，只选择非支配解，如果非支配解低于初始种群数，再随机生成新的家族进行补充，这种方式可以很好地避免陷入局部最优解，并且可以得到更多的Pareto 最优解。算法基本步骤如下：①随机生成m组实数序列代表m 个初始家族；②计算m 个家族的配送成本和风险；③进行非支配排序，处于同一非支配排序等级时，进行拥挤度计算，拥挤度距离较大的家族排在队列的前面；④根据各个家族在列队中的位置，处于前面的家族有较大的概率进行小规模的变异，处于末位的家族有较大概率进行无性繁殖；⑤计算子代的配送成本和风险；⑥进行非支配排序，选择非支配解作为父代进行下一代繁殖，如果非支配解没有达到初始家族数，再随机生成新的家族进行补充；⑦判断当前的迭代次数是否大于最大迭代次数，如果是输出最优解，否则转②继续迭代。

4.5 算法的变异和繁殖策略

本文采用的是实数型编码，变异策略是在数列中随机产生两个点，并交换两个点的位置，繁殖策略采取的是无性繁殖，在数列中随机产生两个点，并在这两个点这间进行随机排列，具体的过程如图2所示。

图2 变异繁殖操作示意图

5 实例计算与结果分析

本文以武汉某石化企业2018年12月11日的成品油配送路径优化问题为例，以石化企业的油库为配送中心，取16 个加油站为该油库的配送客户，所选取的加油站如图3所示。客户接受的服务时间s=30min，客户时间窗在[0,660]内取值，其中0代表时刻8:00，660代表时刻19:00，时间窗转换的方式是以时刻8:00为基准，某一时刻相对于基准过去的时间，比如时刻9:10 相对时刻8:00 过去了70min，那么70 代表的是时刻9:10，油罐车的最大载重量为8t。实例数据如表1所示。

5.1 BP神经网络车速预测结果分析

图3 加油站分布图

表1 实例数据

在成品油二次运输过程中，大多时间都是在高速路/快速路和主干路上行驶，所以本文主要考虑油罐车在运输过程中高速路/快速路和主干路上的行车速度，假设次干路速度和主干路行车速度相等。BP 神经网络传递函数选择双极S 型函数，对于训练函数选取学习率可变的最速下降BP 算法，网络的迭代次数设置为1000，目标误差设置为0.01，不同数据的最佳网络结构不同，所以对于主干路车速的预测，输入层节点数为5，隐含层节点数为7，输出层节点数为1 的网络结构，对于高速路/快速路的预测，输入层节点数为5，隐含层节点数为14，输出层节点数为1的网络结构。数据收集选择从2018 年10 月29 日到12 月14 日工作日的35天数据，每天从7:00 到20:00 每30min 收集一次高速路/快速度和主干路的平均车速，样本数据为10月29日到12月9日工作日的数据，12月10日到12月14日为预测数据。本文以12月11日周二的预测为例，对预测结果进行分析，采用MATLAB 软件对数据进行处理以及分析，抽取周二组的数据对网络进行训练，高速路/快速路和主干路网络的R 值分别为0.95596、0.97337，可见预测精度较高。为了进一步评估模型，引入平均相对误差（MRE），见式(18)。

式中，yi为实际车速，km/h；y'为预测的车速数据，km/h。通过计算快速路的MRE 值为7.99%，主干路的MRE 值为5.68%，预测程度具有较高的可信度，两者的速度对比图如图4所示。

图4 预测车速和实际速度对比图

城市的交通虽然每时每刻都在变化，但是有的时候在一个时间范围内车辆速度的变化并不大，根据武汉交通委员会交通周报，早高峰时间段为7:00—9:00 和晚高峰时间段为17:00—19:00，以及收集到的数据进行分析，把一天的时间分为7:30—9:00、9:00—10:30、10:30—12:30、12:30—14:30、14:30—17:00、17:00—19:00 和19:00—20:00 这7 个时间段，划分后时间段的车速预测结果如表2所示。

表2 车速预测结果

5.2 实例计算结果分析

模型参数设计，单位运输成本C 取值为1 元，启动单个车辆成本B取值为200元，早到惩罚费用E取值为10元，晚到惩罚费用L取值为40元，事故发生概率pij取值为每106km 发生7.75 次[17]，风险半径r取值为1.6km[1]，考虑到大多加油站分布在武汉市主城区，故-Q的取值为武汉市主城区平均人口密度6362 人/km2，wt本人选择在1～3 范围内进行取值，在matlab2009 环境中分别用MOLCA 和改进的多目标列队竞争算法（I-MOLCA）求解。求得的Pareto最优解如图5所示。

由图5 可以看出，改进的MOLCA 的Pareto 最优解完全支配了MOLCA 的Pareto 最优解，且得到更多的Pareto 最优解。Pareto 最优解集只是为决策者提供了多种决策方案，为了选择合适的解，决策者可以从最优解集中选取一个妥协解，妥协解可以根据经验、实际情况或某种规则进行选取，本文妥协解取Pareto 最优解中与理想解的相对距离最小解[18]，相应的函数表达式如式(19)所示。

图5 Pareto最优解

式中，PCS为妥协指数，(W,E)为Pareto 最优解的任一最优解，(W∗,E∗)为理想解，其中W*和E∗分别表示以成本为单目标和以风险为单目标的最优解。求得的妥协解配送成本1280.2，配送风险为37.3，相应路线如表3所示。

表3 妥协解的相应路线

为了验证算法的有效性，本文用I-MOLCA 求解文献[19]的案例，得到结果对比如表4 所示，IMOLCA求得的非支配解，完全支配文献[19]的两个非支配解。

从表3 看出一共6 条路径，但是只用了2 辆油罐车。由于受到载重的限制，油罐车在完成一条线路配送任务后返回配送中心，还在油罐车的配送时间窗内，如果停止配送会导致部分油罐车闲置，且现实情境中，多启动一辆油罐车的费用是比较高的，考虑到上诉因素本文允许在油罐车的配送时间窗内可以进行多次配送。

表4 I-MOLCA求解文献结果对比

本文通过求解不考虑时变风险的模型，求得Pareto 最优解和考虑时变风险的Pareto 最优解进行比较，如图6。由图6 可知，图中不考虑时变风险的曲线的坡度相对于考虑时变风险的曲线小了很多；求得的妥协解的路径比较由图7 和图8 可知，不考虑时变风险求得的路线是7条，考虑时变风险求得的路线是6条，其中不同颜色代表不同的行车路径，两边优化的路线差异是较大的；综上两种比较结果表明动态变化的人群聚齐程度对路线优化的结果影响是比较大的。

图6 Pareto最优解对比图

图7 考虑时变风险的路径优化路线图

6 结论

图8 不考虑时变风险的路径优化路线图

考虑到成品油二次配送的特性，采用BP 神经网络预测车速，以配送过程的风险和成本为目标，提出了改进的多目标列队竞争算法，用于求解成品油二次配送路径优化双目标优化问题，并通过计算某武汉石化企业和文献的实例，获得以下结论：①预测的高速路段和主干路段的车速与实际车速的平均相对误差分别为7.99%和5.68%，预测结果具有较高的预测精度；②与文献差分进化算法求得的结果进行比较，本文提出的多目标列队竞争算法求得的结果优于文献求得的结果；③求解得到了同步考虑配送过程的时变风险和成本的成品油二次配送路径优化的解集，企业可以根据实际情况进行选择。

符号说明