成品油二次配送是石油供应链中的最后环节^[1-2], 目的是将油库中的成品油运送至各个加油站, 直接服务于用户。对成品油二次配送进行优化, 可以提高成品油销售企业的运行效率, 降低运行成本, 为成品油销售企业带来巨大的经济效益^[3]。成品油二次配送问题属于车辆路径问题(VRP), 是一个经典的组合优化问题, 其目的是设计一套车辆行驶路线方案, 包括从仓库出发、访问一个或多个客户、返回仓库。一般以最短总行驶距离或最少运行费用为目标, 优化车辆的行驶路线、参与配送的车辆数量以及访问客户的时间等。对于成品油二次配送问题, 车辆从车库出发前往油库, 在油库装载油品后, 前往加油站配送油品, 完成配送任务后返回油库继续装载下一批油品或直接返回车库。成品油销售企业每日需做出成品油配送计划决策, 决策变量包括车辆分配、路线安排、派出车辆时间、运送油品种类等。在决策过程中, 需考虑车辆每天可以被派出次数, 加油站的交货时间窗等约束。因此, 成品油二次配送问题是一个更为复杂的车辆路径问题, 其决策变量更多, 约束条件更为苛刻。成品油二次配送的优化问题主要包括行车路线选择、货物分配方案、出发时间点选取等子问题, 是较为典型的NP难问题^[4-5]。随着成品油二次配送规模的扩大、客户数量的增加, 研究模型存在着“维数灾难”等问题。已有的研究成果表明只有在一定规模范围内, 才可以在合理的时间内解决问题。因此, 在研究过程中, 需要探索最优解和最佳求解速度的平衡, 这大大增加了研究此类问题的难度。基于此, 详细调研了国内外成品油二次配送的研究进展, 尤其对求解算法进行了深度分析, 并结合中国成品油二次配送现状, 提出了优化建议。

1.   研究进展

1.1   配送模式

在成品油二次配送中, 加油站配送模式分为2种: ①被动配送, 即销售企业根据各个加油站上报的需求输送油品, 加油站每次订购一种或多种石油产品, 并确定每种产品的最小和最大配送量; ②主动配送, 即加油站不必订购油品, 成品油销售企业利用历史数据对各加油站一天中不同时段的销量进行预测, 并制定油品的配送计划。

1.1.1   被动配送

被动配送是指加油站在下一工作日之前订购油品, 每种订购产品的最小量和最大量是确定的。最小量通常是由加油站平均日销量确定, 最大量是加油站的地下储存罐容量与运油车辆到达时储库估计剩余量之差。带时间窗的二次配送问题是对基本二次配送问题的扩展, 引入时间窗后, 所建立的成品油二次配送模型变量规模增大, 使问题更难求解, 因而成为近期研究的热点问题。

1.1.1.1   不带时间窗

众多学者针对不带时间窗的成品油二次配送问题展开了相关研究, 最早由Brown等^[6]提出, 建立了整数规划模型, 用于求解油罐卡车运输问题。该模型以运输费用最小化为目标, 每辆油罐车一次只能前往一个加油站, 考虑了人力资源、设备工作量的分配、消费者需求、设备容量限制以及安全方面的因素。采用该模型可以求解300辆油罐车对80个加油站的配送问题。在后续研究中, Brown等^[7]提出了在现实时间内、交易运行信息系统中利用整数规划的方法, 并以因产品订购量变化导致的罚款最低为目标函数, 求解430辆油罐车对120个加油站的配送问题。Ng等^[8]针对香港石油输送公司油罐车分配和路径问题, 采用了结合启发式聚类和最优路径的决策支持系统(Decision Support System, DSS), 将最少油罐车数量、沿途最少停车次数、运送产品最大利润、资源最大利用程度多个目标按照一定权重组合成目标函数, 求解最优编队分配方案和最优路径。Cornillier等^[9]设定了成品油二次配送的总利润概念, 即销售收入减去与路径长度相关的车辆行驶费用、每辆车的常规费用及加班费, 将总利润最大作为目标函数, 求解多油库加油站配送问题, 使用启发式算法求解, 将整个问题划分为路径设置、油罐车装载过程、路线分配过程、运输时间安排过程。Cornillier等^[10]将成品油二次配送问题分解为装车问题和路径问题, 提出采用ILP(Integer Linear Programming)模型以求得该问题的精确解。

1.1.1.2   带时间窗

时间窗的加入将大幅度增大成品油二次配送问题求解的难度和规模, 采用全局搜索算法很难在合理时间内搜索到合适解, 因此, 学者们更加倾向于使用启发式算法求解, 如遗传算法、C-W节约算法、蚁群算法等^[11-14]。Brandao等^[15-16]针对油罐车的多线路规划问题, 考虑了由加油站确定的运输时间窗, 并允许1辆车进行多次油品的配送服务, 采用禁忌搜索算法求解。Olivera等^[17]根据适应性记忆过程(Adaptive Memory Programming, AMP), 选用启发式算法求解多线路下油罐车路径问题, 求得更多的可行解, 且可行解更加接近最优解。Wang等^[18]在给定油罐车数量的情况下, 提出考虑时间窗的车辆路径规划问题模型, 并使用遗传算法求解。Cornillier等^[19]考虑了当成品油储存在多个不同的油库中、需要被输送至多个不同加油站、每个油库都配备有油罐车、油罐车的型号不同时的二次配送问题, 使用启发式算法求解, 确定每种油品的运输数量、油罐车不同油舱的油品分配以及运输路径, 并将时间窗考虑在内。Cornillier等^[20]在后续研究中, 使用启发式算法计算了一组可行路径, 并求解含有时间窗的多油库成品油的配送问题。Boctor等^[21]针对成品油二次配送问题, 考虑了油罐车的型号、油罐车工作时间限制、不同路线的长度、每条路线的净收益、每趟配送任务的时间范围等因素, 并使用启发式算法模型求解。李敏等^[22]在初始化车辆路径规划种群时, 构建了订单邻域系统, 并使用改进量子遗传算法求解, 提升了所求解的质量。

1.1.2   主动配送

由于成品油二次配送的被动配送通常存在以下问题: ①不同加油站接收油品的时间需求可能相近, 因而导致成品油销售企业的运输车辆在一定时间内不足, 但在其余时间闲置的情况; ②单个加油站每日应该从石油公司接收多种油品, 对于每种油品的合理分配时间难以预估。主动配送时间由每个加油站的存余量和预测销售情况确定, 因此主动配送可以解决在单日内对加油站多次配送的分配问题, 同时也可以减少运输车辆, 将配送时间合理划分, 确保司机有充足的休息时间。因此, 主动配送使整个成品油二次配送系统更加高效, 且运输时间和运输工具的分配更加合理。

目前, 已有的研究成果大都针对被动配送模式。但主动配送的优点是将整个配送过程视为一个整体, 系统依此而不再根据每个加油站的要求确定配送时间, 运输工具在一天内的工作时间会更加平衡, 不会导致各站需求集中在一个时间点, 从而出现运输工具不足的问题。随着智能物流研究的进步, 结合主动配送的优点, 主动配送将会成为加油站配送的主要模式。虽然成品油主动配送相关的研究较少, 但可以借鉴其他车辆配送问题的研究思想。柳伍生等^[23]针对订货信息不断更新条件下的车辆调度问题开展了研究, 以局部搜索法求得初始解, 以遗传算法优化初始解, 以禁忌搜索法改进订货信息更新后的调度方案, 具有求解速度快的特点。葛显龙等^[24-25]先将基于时间轴的动态车辆调度问题模型转换为静态配送问题, 再采用混合量子遗传算法和云自适应遗传算法对实时生成的订单进行再优化。

1.2   车辆路径规划问题

已有学者针对车辆路径问题做了大量研究, 可以参考相关方法, 应用于成品油的二次配送问题中。由于车辆路径问题存在随模型规模扩大, 求解时间急剧增长的情况, 较少采用搜索全局最优解的算法, 而是考虑寻求最优解和最佳求解速度的平衡, 常采用启发式算法求解。

1.2.1   全局搜索

Fisher等^[26]采用图论的方法, 考虑了车辆配送能力和每个客户每天只能被访问一次的限制, 使用k树建立数学模型以寻找最小成本, 并采用分支定界法求出最优解。Xiao等^[27]使用了混合整数线性规划模型, 以车辆总碳排放最少为目标, 考虑了不同车型随时间变化的交通流、客户的允许进货时间窗限制、车辆载荷对排放污染的影响以及车辆的容量等因素, 该模型还允许运货车辆停在半路上。Batista等^[28]对于车队送货问题, 以总行驶距离最短为目标, 建立双目标混合整数线性规划模型, 分别对于25、50、100个客户进行试验。

1.2.2   启发式算法

1.2.2.1   邻域搜索

邻域搜索(Local Search)常常被应用于VRP问题中, 特别是针对大型车辆路径的调度问题。Maden等^[29]以总行驶时间最小为目标, 考虑了速度随时间的变化, 采用邻域搜索算法求解。Wen等^[30]提出了一种新的启发式算法, 以最小车辆行驶费用为目标, 考虑了燃油费用、司机工资以及堵车所造成的额外费用, 其中燃料费用与车速有关, 堵车费用是在车辆进入拥堵区后产生的固定费用。

采用邻域搜索还可以解决包含两个层级的车辆路径问题: 在第1层中, 车辆由配送中心开往中转站; 在第2层中, 车辆由中转站再开往客户处。在此类问题中, 配送中心是一个大型的仓库, 其所派出的车辆为大型货车, 在一个区域中, 一般只有一个配送中心; 中转站靠近客户, 其储存能力很小, 只能对配送中心发过来的车辆的货物暂时储存, 从中转站开往客户的车辆一般为小型货车, 比配送中心使用的大型货车装载能力小。Grangier等^[31]针对双层级车辆路径问题, 考虑了时间窗约束, 使用自适应大领域搜索解决问题。Breunig等^[32]针对双层物流问题, 使用包含了破坏和修复原则的改进邻域搜索算法以优化中转站的选择, 该改进算法使求得的解更优, 并加快了计算速度。

1.2.2.2   智能算法

智能算法具有求解速度快、极易找到最优解的特点, 也大量应用于车辆路径规划问题中, 其多采用遗传算法、粒子群算法、蚁群算法等。

产品路径和污染路径问题是VPR问题中的两个重要问题, 共同决定车辆的最优行驶路线。其中, 产品路径规划可以决定产品的最佳分发路线, 污染路径规划可以减少碳排放。Kumar等^[33]在研究中同时考虑带有时间窗的产品和污染路径规划问题, 以最小总运行花费和最小排放量为目标, 使用多目标、自学习的粒子群算法解决问题。

乳品厂的原料奶收集问题与成品油二次配送问题相接近, 其过程与二次配送问题相反, 是将不同养牛场的牛奶收集到乳品厂。这类问题也具有与二次配送问题相似的车辆特征, 即每辆车包含了不同容积的多个罐, 来自不同奶牛厂的牛奶不能放置于同一个罐中。Sethanan等^[34]针对此问题, 以总成本最小为目标, 考虑了燃油花费、车辆的清洁和消毒有关的花费, 提出了改进的微分进化算法, 以求得在尽量少使用车辆情况下的最短行驶路径。在研究对象的规模方面, 垃圾收集问题与成品油二次配送问题类似, 需要访问节点的个数常以百计。Huang等^[35]在解决垃圾收集问题时, 提出了两阶段优化模型: ①优选垃圾收集点, 目标是使收集点能够覆盖整个居民区; ②使用蚁群算法, 实现最少车辆最短路径收集所有垃圾的目标。Yanik等^[36]针对电子超市多供应商多产品的多次提货配送问题(小单交付), 使用遗传算法用于供应商选择和配置, 节约算法用于包含时间窗的多个小单交付问题求解, 对于遗传算法得到的每一代的解, 都用节约算法求得最终最小的配送成本。Sprenger等^[37]提出了一个食品制造商的VRP问题模型, 几个食品制造商对共同拥有的客户共享车队。考虑带时间窗的订单, 基于交货能力的限制、车辆最大运行时间、外包选择等因素, 使用改进的蚁群算法求解。Xiao等^[38]以燃料消耗最小值为目标, 使用模拟退火算法, 改进了混合交换规则, 在与经典车辆路径问题模型对比后, 证明该模型可以减少燃料消耗。

上述求解算法在针对特定问题时均取得了较好的效果, 但不同问题之间存在变量、约束等差异, 简单套用某一种方法不一定能实现对二次配送问题的高效求解, 因此, 应该借鉴上述建模方法及求解算法上的创新之处, 改进智能算法, 开发适用于成品油二次配送问题的高效求解算法。

2.   优化建议

目前, 中国在成品油二次配送优化方面的研究多集中于问题分析、定性指导措施等方面, 在二次配送优化模型建立与求解方面暂时落后于国外。国内外在成品油配送车型、配送时间、配送方式、管理调度方面均存在一些差异, 需要结合中国国情开展成品油二次配送优化研究, 主要解决出发时间点选取、货物分配方案、行车路线选择优化等子问题。基于此, 以总运行成本最小为目标, 考虑道路拥堵状况不确定性、下游市场需求不确定性、多油库多种型号油罐车等因素建立优化模型, 针对成品油二次配送每日需要做出一次计划的特点, 急需开发在合理时间内求解得到最优配送方案的模型及算法, 主要优化建议如下:

(1) 采用启发式算法求解大规模二次配送问题时, 不一定能求得全局最优解。已有的成品油二次配送算法因各算例规模、约束条件等不尽相同, 很难对算法的求解效果进行定量分析, 以探求各算法对求解结果的影响并提出改进算法。因此, 应该使用不同求解算法对相同模型进行求解, 并对比各算法的优劣。

(2) 随着城市规模的日益扩大, 加油站数量增加、分布范围扩大, 目前中国已有的研究成果不适应大规模数据应用^[13], 因此有必要开展规模较大的成品油二次配送问题的求解方法研究, 以寻求合理时间范围内更快的求解速度和更优解。

(3) 针对目前中国油库存在的单日内对单个加油站多次配送的问题, 应当结合大数据预测各加油站每小时油品消耗量, 以实现主动配送模式下的成品油二次配送。

(4) 目前尚未开展针对城市实际道路的成品油二次配送优化问题的研究, 多是直接将两个加油站之间的距离简化为一个值, 但在实际情况中, 当车辆在路上行驶, 交通通畅程度是必须考虑的因素, 一旦遇到交通堵塞, 运输时间将会延长导致油品不能按时运送至加油站, 因而影响加油站销售量。同时, 不同道路的选择也会影响配送时间、效率及成本。因此, 需要针对城市实际道路, 将两点之间的实际路况考虑在内, 并加入道路堵塞因素。但这将大幅度增加问题的复杂程度, 因此, 针对此类问题建立模型并求解是成品油二次配送优化的研究思路之一。

3.   结束语

近年来, 成品油二次配送相关研究取得了较大进展, 随着成品油市场和城市规模的不断扩大, 成品油二次配送越来越受到成品油销售企业的关注。国外对成品油二次配送优化问题开展了较为深入的研究。中国在该领域的研究起步较晚, 需要针对中国的实际情况, 抓住智能物流发展的大好趋势, 开展成品油主动配送方面的研究工作, 提出切合实际需求的模型和算法。