李珍萍， 焦鹏博， 姜崇宇

(北京物资学院信息学院， 北京 101149)

石油石化产业在国民经济、军事、社会安全和稳定方面发挥着无可替代的作用。作为成品油供应链的末端环节，仅成品油二次配送产生的运输成本就占据成品油供应链总成本的60%～70%[1]。由于加油站的油罐容量有限，而需求量具有随机性，如何控制各个加油站的库存，避免缺货，是石油石化企业制定配送方案时首先要考虑的关键问题；另外，由于成品油属于液体危险品，在配送过程中还需要考虑隔舱运输、是否允许分卸等条件，因此成品油二次问题属于带多种约束条件的库存-路径问题(inventory routing problem， IRP)，结合实际场景研究成品油二次配送库存-路径问题可以为石油石化企业制定成品油二次配送计划，降低配送成本提供决策参考，具有重要的现实意义。

中外学者从不同角度对成品油二次配送问题开展广泛深入的研究。王博弘等[2]对成品油二次配送的两种主要模式(被动配送和主动配送模式)进行了研究。大部分学者针对被动配送模式下(即加油站需求量已知情况下)的成品油二次配送车辆路径问题开展了研究。Carotenuto等[3]研究了涉及单一产品单车型的成品油二次配送问题。张源凯等[4]针对多产品多车型多隔舱的成品油二次配送问题，提出了可求解大规模算例的启发式算法。Wang等[1]分别考虑了单车型和多车型条件下，需求可拆分的成品油二次配送问题。王旭坪等[5]和李珍萍等[6]研究了带有硬时间窗约束的成品油二次配送问题，利用启发式算法对模型进行求解。Cornillier等[7]将成品油二次配送问题扩展至多周期，并设计了多阶段启发式算法。在考虑时间窗的基础上，Cornillier等[8]进一步研究了具有多油库的成品油二次配送问题。

上述针对被动配送模式下的成品油二次配送问题研究均假设加油站的需求量和时间窗已知，将问题简化为带约束的车辆路径问题。实际中很多石油石化企业采取由供应商管理库存(vendor managed inventory， VMI)的主动配送模式，在主动配送模式下各个加油站的补货量需要由供应商确定，此时问题归结为库存-路径问题(IRP)。IRP问题在实际中有着广泛的应用，如危化品配送[9]、物流配送[10]、可持续发展配送[11]等。针对成品油二次配送场景下的IRP问题，Li等[12]对于成品油二次配送中带时间窗的单车型单一产品IRP问题，设计了一种基于禁忌搜索的启发式算法。在单车型单一产品的基础上，Wang等[13]进一步研究了带时间窗约束的成品油二次配送IRP问题，并考虑了碳税政策对总成本的影响。Li等[14]研究了直接配送模式下单车型单一产品考虑随机需求的成品油二次配送IRP问题，并使用CPLEX求解器求解模型。Wu等[15]研究了考虑时间窗和燃料消耗率的IRP问题，利用两阶段混合启发式算法确定最优的库存和路径决策方案。

虽然有关IRP的研究成果十分丰富，但现有研究均对问题进行了不同程度的简化，如严格限制单车型单隔舱、单一产品等约束，忽视需求随机性、车型隔舱种类、油罐车装载运输约束等对总成本的影响。而在实际配送过程中，补货量及配送时间窗确定、车型种类、隔舱数量等条件往往无法忽视。如为避免缺货现象以及错峰配送，需要确定合理的补货量和配送活动的时间窗；为保障成品油在途运输的安全性，车辆装载油品时需要尽可能满载；为保持油品运输的经济性，需要配备多种带有隔舱的车型等。

在已有研究的基础上，现针对随机需求、多车型多隔舱、油品可分卸配送、带软时间窗的成品油二次配送库存-路径问题开展研究。以车辆配送成本、等待成本以及非满载的惩罚成本之和最小为目标，建立混合整数规划模型。根据模型特点将求解过程分解为库存控制(确定补货量及时间窗)和路径优化两个阶段，首先利用加油站需求量的概率分布信息确定安全库存、补货量和软时间窗，并且为每个加油站选择一种车型；然后采用遗传算法求解各车型单舱车的可行配送路径，最后利用C-W节约算法对单舱车可行路径中的节点进行合并，得到多舱车对应的近似最优配送路径。

1 问题描述和模型建立

1.1 问题描述与分析

考虑一个VMI模式下的成品油二次配送网络，某地区有一个油库为n个加油站提供单一类型成品油。油库拥有R种带有隔舱的油罐车，每种类型车辆拥有一个或多个相同容量的隔舱，每辆油罐车同一隔舱中的油品允许分卸到多个加油站。已知油库与加油站、加油站与加油站之间的最短距离，各加油站的最大库存容量、期初库存和销售量服从的概率分布，各种车型的单位距离成本、最大载重量、车辆维护费用及固定费用。所有车辆均需从油库出发，完成配送任务后重新返回油库。问如何制定配送方案，才能满足各个加油站的需求，并且使总配送成本最小。

在制定成品油二次配送方案时，需要确定为每个加油站配送的油品数量(补货量)、完成配送任务需要的最少车辆数及每辆车的配送路径、配送量、等待时间等，使总成本最小。总成本包括：车辆的固定成本、行驶成本、等待成本以及非满载的惩罚成本。等待成本与车辆提前到达加油站时的等待时间有关；惩罚成本与车辆非满载运输造成的空余容量有关。

为便于问题求解，做出如下假设：①油库的库存充足，能够满足所有加油站需求；②各个加油站在一天中不同时段的销售速率稳定；③一个加油站在同一时间只能接受一辆油罐车的服务；④在给定的服务水平下，各个加油站不允许缺货；⑤加油站每天的销售量不超过罐容量。

1.2 混合整数规划模型

考虑多车型多隔舱软时间窗的成品油二次配送库存-路径问题可表示为如下混合整数规划模型，其中目标函数可表示为

(1)

式(1)中：N={0，1，2，…，n，n+1}为配送网络节点集合，其中0、n+1为油库，其余节点为加油站；R={1，2，…，l}为车辆类型集合；Kr={1，2，…，mr}为每种类型车辆的集合；e为车辆的单位距离行驶成本；cij为节点i到节点j的最短距离；xijkr为0-1变量，若车型为r的车辆k经过弧(i，j)为1，否则为0；OC为车辆的固定派遣费用；ykr为0-1变量，使用车型为r的车辆k为1，否则为0；WC为车辆的单位时间等待成本；wikr为车型为r的车辆k到达加油站i时的等待时间；PC为车辆非满载的单位惩罚成本；hkr为车型为r的车辆k的非满载容量。式(1)表示极小化总配送成本，包括车辆行驶成本、车辆固定成本、早于时间窗到达的等待成本和非满载时的惩罚成本。

流量平衡约束：

(2)

(3)

(4)

式(2)和式(3)表示每条路径的起点和终点均为油库；式(4)表示若一辆车服务加油站，则要从该加油站离开。

车容量和加油站需求量约束：

(5)

(6)

(7)

式(5)中：qikr为车型为r的车辆k为加油站i配送的油品数量；Qkr为车型为r的车辆k拥有的最大载重量；T为加油站每天的工作时间；ui为加油站i的单位时间销售率；Ii为加油站i的期初库存；Si为加油站i的有效库存容量；ETi为加油站i的最早服务时间。

式(5)表示车辆容量约束；式(6)表示只有车辆经过加油站才能为其提供服务；式(7)表示加油站可接受的配送量范围。

时间窗约束：

sikr+vi+tij-sjkr≤M(1-xijkr)，

∀i，j∈N，i≠j，k∈Kr，r∈R

(8)

∀i∈N，i≠j，k∈Kr，r∈R

(9)

∀i∈N，k∈Kr，r∈R

(10)

式(8)中：sikr为车型为r的车辆k到达加油站i的时间；M为足够大的正数；vi为车辆在加油站i的服务时间；tij为车辆从节点i到节点j的行驶时间；LTi为加油站i的最晚服务时间；bikr为车型为r的车辆k到达加油站i时晚于ETi的时间。

式(8)表示车辆到达两个相邻加油站之间的时间关系；式(9)和式(10)表示不允许车辆晚于最晚时间到达加油站，但允许提前到达。

车辆与路径之间的关系约束：

(11)

(12)

(13)

式(11)表示只有动用的车辆才能从一个加油站到达其他节点；式(12)表示一个加油站至少被服务一次；式(13)表示对一个加油站同一辆车最多提供一次服务。

决策变量取值约束：

xijkr∈{0，1}， ∀i，j∈N，i≠j，k∈Kr，r∈R

(14)

ykr∈{0，1}， ∀i∈N，k∈Kr，r∈R

(15)

sikr≥0， ∀i∈N，k∈Kr，r∈R

(16)

qikr≥0， ∀i∈N，k∈Kr，r∈R

(17)

wikr≥0， ∀i∈N，k∈Kr，r∈R

(18)

bikr≥0， ∀i∈N，k∈Kr，r∈R

(19)

hkr≥0， ∀k∈Kr，r∈R

(20)

式(14)～式(20)为决策变量取值约束。

2 算法设计

由于库存-路径问题属于NP-hard问题，对于大规模成品油二次配送问题，采用多阶段分解策略求解，既可以降低问题复杂度，又可以设计启发式算法在满足精度要求的同时兼顾问题求解的速度。因此，将结合模型特征，将问题分解为库存控制和路径优化两个阶段，首先根据加油站销售量的概率分布信息和给定的服务水平确定各加油站的补货量，为每个加油站选择合适的车型，然后利用车型分组结合遗传算法和C-W节约算法对路径进行优化。

2.1 库存控制

2.1.1 确定各加油站最晚配送时间窗

根据各个加油站的历史销售数据，确定计划期内每天加油站销售量服从的概率分布(销售量均值di和标准差σi)，在给定的服务水平下，确定各加油站的安全库存水平SIi。假设加油站每天各个时段的销售速率稳定，根据每天的销售量均值di和加油站每天的工作时间T，计算单位时间的销售速率ui=di/T。为保证配送车辆到达时，加油站的实际库存水平不低于安全库存，按照式(21)可确定车辆到达加油站的最晚时间LTi：

(21)

2.1.2 确定各加油站补货量和最早配送时间窗

每个加油站的配送时间点根据最晚配送时间和加油站的平均工作时间T/2确定，如式(22)所示：

(22)

进一步根据加油站的有效库存容量、期初库存量和配送时间点T′，按照式(23)确定补货量：

(23)

根据式(23)可知，当加油站的期初库存量大于平均需求量和安全库存量之和时，不需要安排补货，否则安排补货，按照使加油站在配送时间点的库存量恢复到有效库存容量为标准，确定实际补货量。

为保证配送车辆到达时加油站有足够空余容量装载配送量，按照式(24)可确定每个加油站接受服务的最早时间ETi：

(24)

2.1.3 确定各加油站最佳服务车型

在多车型成品油配送问题中，由于不同车型隔舱容量和总装载量不同，对应的配送成本也不同，因此制定配送计划应该尽可能提高车辆利用率，减少车辆的使用数和空载率。在允许分卸的情况下，车容量越大，可以服务加油站越多，平均使用成本越低。因此优先使用大容量车型可以有效减少配送成本。

另一方面，由于不同加油站的补货量不同，对于补货量较少的加油站，如果使用大容量车型进行配送，车辆空载率较高。因此应该将加油站的补货量与车型进行匹配，尽可能提高车辆的满载率。

根据各个加油站的补货量和各种车辆的隔舱容量，为每个加油站匹配一种合适的隔舱容量和车型。对于某个加油站，根据其补货量，分别计算使用各种隔舱对应的满载率。选择满载率最大的隔舱对应的车型作为该加油站的实际使用车型。然后，根据各加油站的匹配车型，将加油站进行分组，同一组加油站使用相同的车型。这样，同一组加油站的成品油配送问题简化为单一车型VRP问题。

2.2 路径优化

2.2.1 遗传算法

加油站的补货量和匹配车型隔舱确定之后，多车型IRP问题转化为多个单车型VRP问题。对服务加油站的同一种车型，首先假设每辆车只有一个隔舱，根据隔舱容量确定需要使用的单舱车数量及配送路径。按照下列规则设计遗传算法求解。

(1) 编码。采用自然数编码表示染色体结构，0表示油库，1，2，…，n表示加油站。为方便运算，去掉每条路径中的起点和终点0，将所有路径合并在一起形成一条染色体。

(2) 解码。对于编码[4 5 7 3 6 1 9 2 8]，首先安排车辆从油库出发前往加油站4，考虑时间窗、车辆剩余油品量、加油站5的补货量等约束决定是否服务加油站5，如果满足约束，则继续服务加油站5，即[0-4-5]，否则回到油库，即[0-4-0]，之后重新安排车辆服务加油站5，然后判断约束决定是否服务后续加油站。循环上述过程，直到遍历完所有染色体编码为止，此时恰好将染色体序列拆分为若干个满足约束的配送回路，得到一个可行解。

(3) 种群初始化。通过随机生成M个含有1～9序列，形成初始种群。

(4)适应度计算。对于种群中的每个个体si(i=1，2，…，M)，首先通过解码得到一组可行路径，计算其对应的总配送成本Ci。找出所有个体对应的总成本最大值Cmax，按照式(25)计算每个个体的适应度f(si)：

f(si)=2Cmax-Ci

(25)

(5) 选择。采用轮盘赌法选择个体，质量较优的个体优先进入下一代。

(6) 交叉。采用部分匹配交叉法。

(7) 变异。采用逆转变异方法，在选定个体中随机产生两个逆转点，把两个逆转点的基因对调，得到新个体。

(8) 终止条件。达到最大迭代次数则终止迭代，否则转规则(3)。

(9) 输出结果。将种群中适应度最优个体作为最优解输出，得到最优路径。

2.2.2 C-W节约算法

根据遗传算法求出服务所有加油站需要使用的各车型单舱车数量及配送路径，该方案可以看成单舱车的可行配送方案。接下来根据C-W节约算法将单舱车配送方案合并，得到多舱车对应的配送方案。

算法的基本步骤如下。

(1) 合并节点。先将遗传算法得到每条单舱车配送路径上的客户点合并为一个节点，同时更新单舱车到达各个节点的时间，得到的新序列作为节约算法的初始解。节点合并过程如图1所示。

图1可表示为解码后的序列，黄色节点代表油库，橙色与蓝色节点代表客户。合并节点即将一条路径内的客户点合并为一个节点，得到的序列可以看作是直接配送路径的集合。

图1 节点合并示意图Fig.1 Nodes merging diagram

(2) 节约操作。应用经典C-W节约算法，将合并后的独立节点进行连接，计算连接后的里程节约值，按照里程节约值由大到小的顺序，在满足时间窗的条件下对路径进行合并操作，对初始解进行优化。如，路径0-1-0和0-4-0(0为油库)的里程分别是5、8 km，合并后总里程为10 km，合并后的路径长度比两条独立路径的总长度节约了3 km，此时可以将两条路径合并为0-1-4-0或0-4-1-0(由时间窗顺序决定)。节约操作中路径合并数量不超过车辆的隔舱数，合并后得到多舱车的配送路径。

(3) 输出结果。将节约算法得到的最优路径展开还原，如合并后序列为0-a-b-0，a包含2-4，b包含3-1，则展开还原后的路径为0-(2-4)-(3-1)-0，该路径即为双舱车的实际配送路径。

对每种车型执行以上算法，得到最终配送计划。

3 模拟计算与结果分析

3.1 算例描述

在VMI模式下，一个油库为50个加油站配送单一品种成品油，使用的车辆类型有4种，油罐车的行驶速度相同均为30 km/h。给出一个油库(编号为0)和前10个加油站(编号为1～10)，各个加油站的横坐标(X)、纵坐标(Y)等信息如表1所示，车辆信息如表2所示，各项成本信息如表3所示，其中加油站及油库的位置由平面直角坐标系确定，各加油站最大库存容量、期初库存、服务时间，根据加油站前30日销量服从的概率分布确定的销量均值和给定90%服务水平确定的安全库存已知，各加油站每天的工作时间为24 h。

3.2 算例求解与结果分析

根据上述算例数据，首先利用第一阶段算法确定需要服务的加油站以及各加油站的补货量和时间窗，然后利用第二阶段算法优化各车型对应的路径。设置种群规模为30，最大迭代次数为200次，得到按车型分组后的计算结果如表4所示。

结果显示，50个加油站中，有30个加油站的库存量可以满足加油站的销量，不需要安排补货，其余20个加油站需要配送油品。配送计划使用了4种车型共12辆车，其中车型2与车型3均使用双舱车进行配送，车型4则动用了3舱车与4舱车。对于大部分加油站来说，允许服务的最早时间与最晚时间之间的跨度较长，时间窗较为宽松，因此需要服务的加油站均可满足时间窗要求，未出现等待现象。在50个节点的算例规模下，总配送成本为7 438.6 元，程序运行10次的平均总用时为 1.717 s。

由于VMI模式下的成品油二次配送库存-路径问题属于NP-hard问题，因此，将通过小规模算例分析两阶段启发式算法的求解质量与时间。根据表1～表3的加油站、车辆、各项成本信息，在各种信息保持不变的基础上，随机选取n个加油站(n=5，7，9，11)，生成4个小规模算例。利用商业求解器Gurobi直接求解针对每个算例的混合整数规划模型得到精确解。然后利用两阶段启发式算法对同一算例运行10次得到近似最优解，将求解器得到的精确解与算法运算10次得到的平均近似最优解进行对比，其中第二阶段算法参数设置不变。

表1 油库及加油站信息Table 1 Information of the oil deport and petrol stations

表2 车辆信息Table 2 Information of the vehicles

表3 成本信息Table 3 Information of the cost

表4 配送方案Table 4 Results of the distribution

两种方法得到的结果如表5所示。从表5可以观察到，对于包含加油站个数最多的算例，两阶段启发式算法的平均求解时间在1 s左右，而求解器的求解时间则随加油站个数的增加呈指数级增长。对于包含5个加油站的最小规模算例，求解器求解出最优解需要359.52 s，但随着算例规模的增加，求解器的求解时间远远超过两阶段启发式算法的平均时间，当算例包含11个加油站时，求解器无法在可接受时间内求出最优解。在求解质量方面，Gurobi求解器得到的最优总成本比两阶段启发式算法的结果更优，但两者结果的差值在包含不同加油站个数的算例中仍可接受且较为稳定。并且当加油站个数超过9个时，求解器无法在可接受时间内得到最优解，而两阶段启发式算法则可以快速求出近似最优解，因此当问题规模逐渐增加时，两阶段启发式算法的时间优势将更加明显。

表5 小规模算例的求解结果Table 5 Results of small instances

为验证本文算法的有效性，设计求解该问题的单阶段算法，在单阶段算法中，油库只能在已知初始库存和库存容量的前提下选择合适车型，采用直接配送模式避免加油站出现缺货现象。设置Gurobi求解时间为1 800 s，得到可接受时间内的最佳可行解。针对表1的50个加油站，将本文两阶段算法(算法1)与单阶段算法(算法2)、Gurobi最佳可行解算法(算法3)进行比较，结果如表6所示。

由表6可知，虽然两阶段启发式算法在计算时间上不如单阶段算法，但也远远优于Gurobi求解器算法，同时两阶段启发式算法比单阶段算法和Gurobi最佳可行解算法的求解效果更好。

表6 算法结果对比Table 6 Comparison of algorithm results

此外，为验证本文算法与研究结果的可靠性，在不同规模算例中对算法进行测试，并对比不同算法得到的结果。加油站个数从100 开始，每次递增50，直到加油站数量达到500。分别调用算法1、算法2 求解9组算例，每组算例分别运行10次并记录平均总配送成本以及平均求解时间，记算法3求解时间为1 800 s。针对算法2，使用SC表示算法2的总成本(元)；ST表示算法2的求解时间(s)。调用三种算法得到不同规模算例的结果如表7所示。

由表7可知，在不多于500个加油站的算例中，算法1与算法2耗时随算例规模的增加存在缓慢上升趋势，并且虽然算法2的平均求解时间小于算法1的求解时间，但对于规模最大的算例，算法1的平均求解时间也不超过6 s，说明针对此数量级下的问题规模，本文研究的两阶段启发式算法仍然可以保持满意的求解速度。

表7 不同规模算例下的结果Table 7 Results of instances under different sizes

综合对比三种算法的求解时间，以及得到的平均总成本或最佳可行成本可知，虽然算法1在各个算例中的平均求解时间大于算法2，但在实际应用中仍可接受并且明显小于算法3的求解时间，同时，算法1的平均总成本优于另外两种算法，算法3的平均总成本次于算法1但优于算法2，说明本文的两阶段启发式算法在不同规模算例下得到的结果仍然具有较高的可靠性。

4 结论

结合成品油二次配送问题的实际场景，研究了随机需求、多车型软时间窗、满载可分卸的成品油二次配送库存-路径问题，以总配送成本极小化为目标建立了混合整数规划模型，利用分解策略将问题求解过程分解为库存控制和路径优化两个阶段，并设计了路径优化阶段的遗传算法和C-W节约算法，通过不同规模算例验证了模型和算法的有效性。

本文算法的设计思路可推广其他类似问题，为解决其他背景下考虑随机需求的多车型软时间窗库存-路径问题提供了研究思路。

在成品油二次配送库存-路径问题的研究中，对加油站的销售量进行了一定的简化，假设加油站的销售量在一天中各个时段服从相同的分布规律。实际中，加油站每天不同时段的销量变化可能比较大，此时需要分时段考虑销售量服从的分布规律，这种情况下，为了确保加油站不断货，需要用更科学的方法计算补货时间窗和补货量。另外，本文算法仍然属于启发式算法，无法保证找到精确最优解，接下来可以结合模型特点，研究精确算法或其他类型的智能算法。