一种推式配送模式下加油站连续多次补货的配送优化方法

1.本发明涉及成品油物流配送技术领域，尤其涉及一种推式配送模式下加油站连续多次补货的配送优化方法。


背景技术：

2.石油石化产业是国民经济发展的血液，石油是国家发展的重要资源，随着汽车保有量的持续增加，我国汽油消费量持续稳定增长。而石油市场上的大型石油企业的成品油流通成本中，最主要部分是其中的物流成本。通过制定高效的配送策略可以有效控制成品油流通成本，对于提高石油企业的竞争力有着重要的战略意义。
3.成品油的物流配送可分为一次配送和二次配送。一次配送指从炼油厂配送至各地区油库的过程，多采用管道配送，设施固定不具备灵活性，因此物流成本降低空间较小；二次配送是由专用油罐车将成品油由油库输送至各个加油站的过程，二次配送成本约占总物流成本的60％-70％，是石油企业提高配送效率、降低物流成本的核心环节。在组织二次配送时，不同企业往往采用不同的物流组织模式。中国石化、中油bp等企业采取外包物流模式，由专业化的第三方运输商承运，在这种模式下，供应方完全掌握加油站的销售终端数据，通过销售预测结合供应总量来制定各加油站的补货计划。加油站无须关心库存和配送，只需将精力集中于市场营销与销售。站在配送管理的角度，这是一个“推”的动作，即将供应总量以合理的方式分配给各个加油站，即推式配送模式。
4.成品油二次配送问题本质上是一类车辆路径问题(vehicle routing problem，vrp)。vrp问题一般是指，已知多个客户以及车场的位置、所需配送物品的需求量等，在满足车辆容量约束、配送时间窗、调度期约束等一系列约束条件下，寻找满足所有配送需求的配送路径，使配送成本最小或路程最短。其中带隔舱车辆路径问题(multi-compartment vehicle routing problem，mcvrp)是一个亟待解决的问题。
5.目前，现有技术中有学者提出了多隔舱车辆路径问题mcvrp，并对其进行了系统的描述，自此多隔舱车辆路径问题正式成为了车辆路径问题的研究分支之一。为解决这个问题，有方案提出了基于路径链接的模因算法(memeticalgorithm，ma)与禁忌搜索算法，并通过实验证明了算法的有效性。还有方案提出了一个局部搜索过程，首先使用节约算法获得初始解，再通过经典的移动、交换、重新定位、2-opt等算子进行优化，并且利用邻域列表与标记机制加速搜索。其算法运行时间更短，解质量更高，算例结果表明在产品种类更多、车辆容量较大、客户分布较分散的场景下，更适合使用多隔舱车辆配送，在相反情况下，单隔舱车辆配送更优。还有方案提出了一种新的禁忌搜索算法对基础mcvrp求解，基本思想是利用禁忌搜索算法搜索局部最小值再对其施加扰动跳出局部最优，通过不断迭代向最优解逼近，解质量得到进一步优化。还有方案限制每趟车最多可访问的客户数，以最小配送成本为目标，使用遗传算法求解此问题。但作者通过实验得出遗传算法只在较小的局部内可得到最优解，缺乏全局搜索能力。除了以最短路径和最小配送成本为优化目标以外，还有方案以便利店补货为场景，考虑制冷成本、配送成本与车辆固定使用成本最小为目标函数构建了
优化模型。研究中采用拉格朗日松弛算法求得了满意解，证实了其对实际场景的应用价值。还有方案以最小配送时长为目标，提出了一种禁忌搜索启发式算法，并将其嵌入到迭代局部搜索中求解mcvrp。研究中分析了迭代禁忌搜索的性能，并将其与其他文献算法进行了比较。证明此算法始终能产生比现有启发式算法更好的解决方案。
6.(1)上述现有技术方法研究的场景为高速公路上加油站的成品油配送。高速公路加油站的布局呈线状分布，并且间距很远，整车配送更经济。配送油罐车为单隔舱，且必须以整车为单位进行配送，即订单的配送量只能等于油罐车的容积，并且每次配送只能服务于一个加油站。
7.(2)上述现有技术方法设置了最小时间间隔概念，用此间隔将一个调度期分成了多个时段。行驶、装油、卸油等任务的开始时刻只能为各时段的开始时刻，也就是说，此问题中的任务开始时间是离散变量而非连续的，从而进一步简化了问题。
8.(3)上述现有技术方法没有设计启发式算法，因此只能解决小规模问题。本发明建立了pdm-cmd问题的数学规划模型，并设计了融合vns的混合aco算法，并且针对某公司的实际配送网络规模(72个加油站)，均能在可接受时间内求解出满意的配送方案，更具实际应用性。
9.(4)上述现有技术方法所设计的交互式算法比较简单，采用的是传统的通用型局部优化算子，并未针对该问题的特点进行设计。


技术实现要素：

10.本发明的实施例提供了一种推式配送模式下加油站连续多次补货的配送优化方法，以实现有效地对成品油进行物流配送。
11.为了实现上述目的，本发明采取了如下技术方案。
12.一种推式配送模式下加油站连续多次补货的配送优化方法，包括：
13.将每个油罐作为客户，将每个客户的每次成品油配送需求作为一个订单，获取每个调度期中各个客户的订单；
14.根据所设计的配送量离散化的配送网络构建策略完成配送网络构建，根据所设计的车辆并行路径构建策略完成配送路径的构建；
15.以所有客户的订单的运输成本、车辆卸油成本与缺货成本构成的总成本最小为目标，基于所述配送网络和配送路径建立连续多次配送、多行程、带隔舱的车辆路径问题问题的混合整数数学规划模型；
16.采用融合变邻域搜索算法的蚁群算法迭代求解所述混合整数数学规划模型的目标函数，完成每次迭代后，采用变邻域搜索算法对精英蚂蚁生成的解进行优化，输出迭代完成后的最优解，得到各个客户的订单的配送方案。
17.优选地，所述的根据所设计的配送量离散化的配送网络构建策略完成配送网络构建，包括：
18.将各加油站内装着不同油品的油罐表示为节点，车辆在中途需要多次到油库装油，为表示油库节点每次被访问的状态，为每台车设置一个虚拟的油库节点，用有向图g＝(v,e)表示成品油的配送网络，v表示顶点集，v＝c∪f0∪f1，c＝{1,
…
n}表示油罐节点集合，n表示油罐的总数，f0＝{n+1,
…
,n+m}表示起点油库的虚拟油库集合，f1＝{n+m+1,
…
,n+2m}
表示终点油库的虚拟油库集合，m表示油罐车的总量，车辆k始终从油库节点n+k装油并出发，配送后返回节点n+m+k。e表示边集，e＝{(i,j)|i,j∈v,i≠j}。
19.优选地，所述的根据所设计的车辆并行路径构建策略完成配送路径的构建，包括：
20.采用车辆并行路径构建策略构建配送路径，将车辆k每一趟的成品油配送方案称为一个行程trip，车辆k在调度期内执行的所有行程trip构成车辆k的回路tourk，蚂蚁f模拟车队所构造的路线称为蚂蚁f的配送路径方案planf＝{tour
k1
,tour
k2
,
…
,tour
km
}。
21.优选地，所述的以所有客户的订单的运输成本、车辆卸油成本与缺货成本构成的总成本最小为目标，基于所述配送网络和配送路径建立连续多次配送、多行程、带隔舱的车辆路径问题问题的混合整数数学规划模型，包括：
22.以所有客户的订单的运输成本、车辆卸油成本与缺货成本构成的总成本最小为目标，基于所述配送网络和配送路径建立连续多次配送、多行程、带隔舱的车辆路径问题问题的混合整数数学规划模型的目标函数为：
[0023][0024]
所述总成本由三部分构成，第一部分c_1为车辆的运输成本，与车辆行驶距离相关，第二部分c2为车辆卸油成本，与卸油时长相关，第三部分c3为缺货成本，由销售损失来表示；
[0025]
所述混合整数数学规划模型的约束条件包括：节点访问约束、配送量约束与时间约束，具体如下：
[0026]
节点访问约束包括：
[0027]
[0028][0029]
上述式子依次表示油罐车到达油罐节点后必须离开该节点；油罐车从专属虚拟油库节点出发并到达专属虚拟油库节点，且在调度期内同一台油罐车运行趟数有上限；每台车都需要被启用；如果节点第r次访问不存在，则一定不存在第r+1次配送；节点之间的访问顺序约束，应从虚拟油库起点出发，访问若干油罐后，返回虚拟油库终点，然后再从虚拟油库起点出发或终止行程；节点的某次访问最多只能作为路线的到达节点一次，离开节点一次。
[0030]
配送量约束包括：
[0031][0032]
其中，式1表示从车场出发时油罐车的可用隔舱数都为n；式2表示配送方案中前后两个访问节点的可用隔舱数关系，后访问节点的可用隔舱数为前节点的可用隔舱数减去前节点所需隔舱数，以及油罐车的最大隔舱限制；式3表示油罐的每次配送量不能超过车辆容量，且每个隔舱至少要达到最小装载率要求；式4表示一个订单，只由一个车次满足；式5表示对于油罐节点，如果存在某次访问，则必需在这次访问中对其配送；式6表示调度期内供应总量要满足上下限要求；
[0033]
时间相关约束包括：
[0034][0035]
其中，式1表示同一油罐前后两次服务存在时间先后顺序，第r+1次补货一定在第r次补货后；式2表示同一节点前后两次访问存在时间先后顺序，第r+1次访问一定在第r次访问后；式3、4表示油罐车配送路径上前后节点的到达时间关系；油库到油罐节点的路径上，油库出发时刻加行驶时长为到达油罐节点时刻；油罐到油罐节点或油库节点的路径上，前一油罐节点到达时刻加等待时长加卸油时长加行驶时长为到达后一节点的时刻；式5表示油罐车需在调度期内工作，即在调度期开始后离开油库，在调度期结束前返回油库；式6表示，车辆回到油库后需要消耗一定时间装油后再出发；式7是0-1变量约束。
[0036]
优选地，所述的采用融合变邻域搜索算法的蚁群算法迭代求解所述混合整数数学规划模型的目标函数，完成每次迭代后，采用变邻域搜索算法对精英蚂蚁生成的解进行优化，输出迭代完成后的最优解，得到各个客户的订单的配送方案，包括：
[0037]
初始化各参数，设置迭代次数为t
←
1、最大迭代次数为max_iter，蚂蚁种群为ant，在每一轮迭代计算过程中，从ant中依次选取每个蚂蚁f，根据并行路径构建规则生成蚂蚁f的可行解sf，对精英蚂蚁生成的解采用变邻域算法优化，采用精英蚂蚁策略和max-min策略
进行信息素更新，进行下一轮的迭代计算过程，直到迭代计算收敛，输出迭代完成后的最优解，得到各个客户的订单的配送方案。
[0038]
优选地，所述的对精英蚂蚁生成的解采用变邻域算法优化，包括：
[0039]
采用变邻域算法基于贪婪算法思想生成初始解，所述变邻域算法分为抖动阶段和局部搜索阶段，在抖动阶段，随机选择一个抖动邻域结构中的一个解作为新解，在局部搜索阶段，采用局部搜索在新解的邻域中寻找局部最优解，如果该局部最优解比当前解更优，则以该局部最优解作为新的当前解，从第一个邻域开始搜索，否则继续搜索下一个邻域，邻域结构采用最先改进策略，为邻域内设置局部最大迭代次数max_iter2，在max_iter2次循环内找到更优方案则立即停止本邻域的迭代，更新最优解并跳回第一个邻域，若迭代数达到max_iter2仍未找到更好解，则跳到下一个邻域，当v_iter次搜索过全部邻域结构，都没有找到比当前解更好的解即完成搜索。
[0040]
优选地，所述的采用变邻域算法基于贪婪算法思想生成初始解，包括：
[0041]
基于贪婪思想以避免缺货为原则构建初始解，采用车辆并行路径构建策略，车辆每次选择客户节点时，均以当前配送网络状态为基础，选择断货时间最小的客户，而配送量则设置为不发生等待的最大值，不断重复上述过程，直到总配送量达到总配送量区间[h-,h
+
]，得到初始解。
[0042]
优选地，所述的变邻域算法包括：订单交换、缺货优化、同加油站配送优化和非必要配送优化4个类别共9个邻域结构，其中单回路内订单交换邻域结构、多回路间订单交换邻域结构与单回路缺货优化邻域结构为抖动邻域结构，全部9个邻域结构都为局部搜索邻域结构。
[0043]
由上述本发明的实施例提供的技术方案可以看出，本发明实施例定义了拉式/推式配送模式，提出了pdm-cmd问题并建立了混合整数规划模型，丰富了vrp问题理论体系。该问题同时考虑了推式配送模式、多隔舱、多行程、罐容约束、多次连续配送等复杂场景，相较于其它同类研究，问题更加复杂、解空间更加庞大、求解难度更大，也更具实用价值。
[0044]
本发明附加的方面和优点将在下面的描述中部分给出，这些将从下面的描述中变得明显，或通过本发明的实践了解到。
附图说明
[0045]
为了更清楚地说明本发明实施例的技术方案，下面将对实施例描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
[0046]
图1为本发明实施例提供的一种融合变邻域搜索的混合蚁群算法的具体流程图；
[0047]
图2为本发明实施例提供的一种某个配送问题的车辆行驶路线与装载方案示意图；
[0048]
图3为本发明实施例提供的一种配送路径方案示意图；
[0049]
图4为本发明实施例提供的一种单行程内订单交换邻域结构示意图；
[0050]
图5为本发明实施例提供的一种单回路内订单交换邻域结构示意图；
[0051]
图6为本发明实施例提供的一种多回路间订单交换邻域结构示意图；
[0052]
图7为本发明实施例提供的一种单回路缺货优化邻域结构示意图。
具体实施方式
[0053]
下面详细描述本发明的实施方式，所述实施方式的示例在附图中示出，其中自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描述的实施方式是示例性的，仅用于解释本发明，而不能解释为对本发明的限制。
[0054]
本技术领域技术人员可以理解，除非特意声明，这里使用的单数形式“一”、“一个”、“所述”和“该”也可包括复数形式。应该进一步理解的是，本发明的说明书中使用的措辞“包括”是指存在所述特征、整数、步骤、操作、元件和/或组件，但是并不排除存在或添加一个或多个其他特征、整数、步骤、操作、元件、组件和/或它们的组。应该理解，当我们称元件被“连接”或“耦接”到另一元件时，它可以直接连接或耦接到其他元件，或者也可以存在中间元件。此外，这里使用的“连接”或“耦接”可以包括无线连接或耦接。这里使用的措辞“和/或”包括一个或更多个相关联的列出项的任一单元和全部组合。
[0055]
本技术领域技术人员可以理解，除非另外定义，这里使用的所有术语(包括技术术语和科学术语)具有与本发明所属领域中的普通技术人员的一般理解相同的意义。还应该理解的是，诸如通用字典中定义的那些术语应该被理解为具有与现有技术的上下文中的意义一致的意义，并且除非像这里一样定义，不会用理想化或过于正式的含义来解释。
[0056]
为便于对本发明实施例的理解，下面将结合附图以几个具体实施例为例做进一步的解释说明，且各个实施例并不构成对本发明实施例的限定。
[0057]
推式配送模式是由供应方(油库)确定加油站的补货需求，并组织车辆进行配送。pdm-cmd问题是指连续多次配送、多行程、带隔舱的车辆路径问题，量小而销量大的油罐需多次补货，配送量的不同会影响后续配送的时间窗，油罐每次补货的配送量、订单交付时间以及车辆调度方案均为决策变量。
[0058]
本发明实施例针对城乡一体化的加油站配送场景，其场景远比高速公路加油站配送复杂，规模庞大，既有城区的高密度加油站布局，也有乡村和高速公路的低密度加油站布局，小罐销比油罐更为普遍，并且为提高效率，采用了带隔舱的车辆，使得同加油站的不同油品可由同一台车配送。车辆在一次配送中也一般要服务于多个加油站。
[0059]
本发明的pdm-cmd问题针对城乡一体化的加油站配送，既有城区的高密度加油站布局，也有乡村和高速公路的低密度加油站布局，小罐销比油罐更为普遍，采用带隔舱的车辆，使得同加油站的不同油品可由同一台车配送。车辆在一次配送中也一般要服务于多个加油站。但在本发明解决的pdm-cmd问题中，任务可以在调度期内的任意时刻开始执行，更灵活且更符合实际，但求解难度也更大。
[0060]
本发明实施例提供的一种推式配送模式下加油站连续多次补货的配送优化方法的首先根据研究问题的特点，给出基本假设，考虑传统车辆路径问题(vehicle routing problem，vrp)问题常见的节点访问约束与本问题特有的配送量约束与时间相关约束，以由运输成本、车辆卸油成本与缺货成本构成的总成本最小为目标，建立连续多次配送、多行程、带隔舱的车辆路径问题(pdm-cmd)问题的混合整数数学规划模型。针对问题，以蚁群算法与变邻域搜索算法为算法设计的理论基础，结合供应链推拉策略原理，设计了可用于求解上述混合整数数学规划模型的融合变邻域搜索的混合蚁群算法。在混合蚁群算法中将油
罐的配送量离散化，将离散后的各个配送量与油罐以及配送次数结合，共同构建节点，同时针对pdm-cmd问题特点设计了启发式因子与车辆并行构建路径策略。针对vns(variable neighborhood search，变邻域搜索算法)算法，从订单、配送量和服务时间三个维度设计了九个邻域结构，并采用变邻域搜索框架进行局部优化。将两种算法有机结合，在蚁群每次迭代后，对精英解应用vns算法进一步优化，从而构建一种融合vns的混合aco(ant colony optimization，蚁群算法)算法。
[0061]
在本发明实施例的pdm-cmd问题中，通过优化方法得到的配送方案包括以下几个部分：(1)每个油罐的一个(或多个)订单，以及各订单的配送量；(2)同一油罐的多个订单的交付先后顺序；(3)各个订单由哪台车辆来配送；(4)车辆访问订单的顺序；(5)车辆交付各个订单的时刻。
[0062]
本发明实施例融合变邻域搜索算法的混合蚁群算法，将变邻域搜索算法和蚁群算法两种算法有机结合，在aco每次迭代后，对精英解应用vns算法进一步优化，从而构建一种融合vns的混合蚁群算法。
[0063]
本发明实施例提供的一种融合变邻域搜索的混合蚁群算法的具体流程图如图1所示，其中最大迭代次数为max_iter，蚂蚁数为ant_coint。本发明实施例提供的一种推式配送模式下加油站连续多次补货的配送优化方法的处理流程包括如下的处理步骤：
[0064]
步骤s10：将每个油罐作为客户，将每个客户的每次成品油配送需求作为一个订单，获取每个调度期中各个客户的订单。
[0065]
步骤s20：根据所设计的配送量离散化的配送网络构建策略完成配送网络构建，根据所设计的车辆并行路径构建策略完成配送路径的构建。
[0066]
步骤s30：以所有客户的订单的运输成本、车辆卸油成本与缺货成本构成的总成本最小为目标，基于所述配送网络和配送路径建立连续多次配送、多行程、带隔舱的车辆路径问题问题的混合整数数学规划模型。
[0067]
步骤s40：采用混合蚁群算法迭代求解所述混合整数数学规划模型，完成每次迭代后，采用变邻域搜索算法对精英蚂蚁生成的解进行优化，采用精英蚂蚁策略和max-min策略进行信息素更新，输出迭代完成后的最优解，得到各个客户的订单的配送方案。
[0068]
下面以一个例子来说明pdm-cmd问题的解方案。图2展示的是某个配问题的车辆行驶路线与装载方案示意图。附表1中为两辆车详细的配送方案。在该成品油配送网络中，有1个油库，4个加油站，各加油站销售单种或多种油品。车队共有两台油罐车，各有三个容积为10000l的隔舱送。
[0069]
表1 pdm-cmd解方案示例
[0070][0071]
以车量x第一趟配送方案为例说明解方案，其余趟同理：
[0072]
第一趟：0时开始装油，0.5h从油库出发
→
于1时到达a加油站并向95油罐补货10000l油，1.4时离开
→
于1.9时到达b加油站，等待至2.3时向98油罐补货19000l油，3时离开
→
3.5时回到油库装油；值得注意的是，加油站a的95油罐在此调度期内被配送了两次。第一次是由车辆x于1时配送了10000l，第二次是由车辆y于5.5时配送了10000l。
[0073]
根据问题构建pdm-cmd问题的数学模型。用有向图g＝(v,e)表示成品油的配送网络。其中，v表示顶点集，v＝c∪f0∪f1。f＝{1,
…
n}表示油罐节点集合，将各加油站内装着不同油品的油罐表示为节点。车辆在中途需要多次到油库装油，为保证可以表示油库节点每次被访问的状态，为每台车设置一个虚拟的油库节点。f0＝{n+1,
…
,n+m}表示起点油库的虚拟油库集合，f1＝{n+m+1,
…
,n+2m}表示终点油库的虚拟油库集合，其中m是油罐车的总量。车辆k始终从油库节点n+k装油并出发，配送后返回节点n+m+k。e表示边集，e＝{(i,j)|i,j∈v,i≠j}。
[0074]
目标函数
[0075][0076]
以总成本最小为目标的目标函数，总成本由三部分构成，第一部分c_1为车辆的运输成本，与车辆行驶距离相关。第二部分c2为车辆卸油成本，与卸油时长相关。第三部分c3为缺货成本，由销售损失来表示，即油罐在本调度期与下调度期初由于断货所减少的销售利润，缺货成本与该油罐销售速度与缺货时长相关。
[0077]
约束条件
[0078]
pdm-cmd问题的约束条件分为三类：节点访问约束、配送量约束与时间约束，具体如下：
[0079]
节点访问约束包括：
[0080][0081][0082]
上述式子依次表示对于油罐节点需要满足流量平衡，即油罐车到达油罐节点后必
须离开该节点；油罐车从专属虚拟油库节点出发并到达专属虚拟油库节点，且在调度期内同一台油罐车运行趟数有上限；每台车都需要被启用；如果节点第r次访问不存在，则一定不存在第r+1次配送；节点之间的访问顺序约束，应从虚拟油库起点出发，访问若干油罐后，返回虚拟油库终点，然后再从虚拟油库起点出发或终止行程；任意节点的某次访问最多只能作为路线的到达节点一次，离开节点一次。
[0083]
配送量约束包括：
[0084][0085]
其中，式1表示从车场出发时油罐车的可用隔舱数都为n；式2表示配送方案中前后两个访问节点的可用隔舱数关系，后访问节点的可用隔舱数为前节点的可用隔舱数减去前节点所需隔舱数，以及油罐车的最大隔舱限制；式3表示油罐的每次配送量不能超过车辆容量，且每个隔舱至少要达到最小装载率要求；式4表示一个订单，只由一个车次满足；式5表示对于油罐节点，如果存在某次访问，则必需在这次访问中对其配送；式6表示调度期内供应总量要满足上下限要求；
[0086]
时间相关约束包括：
[0087][0088]
其中，式1表示同一油罐前后两次服务存在时间先后顺序，第r+1次补货一定在第r次补货后；式2表示同一节点前后两次访问存在时间先后顺序，第r+1次访问一定在第r次访问后；式3、4表示油罐车配送路径上前后节点的到达时间关系；油库到油罐节点的路径上，油库出发时刻加行驶时长为到达油罐节点时刻；油罐到油罐节点或油库节点的路径上，前一油罐节点到达时刻加等待时长加卸油时长加行驶时长为到达后一节点的时刻；式5表示油罐车需在调度期内工作，即在调度期开始后离开油库，在调度期结束前返回油库；式6表示，车辆回到油库后需要消耗一定时间装油后再出发；式7是0-1变量约束。
[0089]
针对该问题模型设计一种蚁群算法，蚁群算法设计精英蚂蚁、max-min等信息素更新策略，并针对pdm-cmd问题的特点设计了启发式因子与车辆并行构建路径策略。算法框架的伪码如附表2所示。
[0090]
附表2
[0091][0092][0093]
将加油站各油品的油罐(tank)看作客户，将客户的每次配送需求看作订单(order)，车辆k每一趟的配送方案称为一个行程(trip)，车辆k在调度期内执行的所有trip构成车辆k的回路tourk。蚂蚁f模拟车队所构造的路线称为蚂蚁f的配送路径方案planf＝{tour
k1
,tour
k2
,
…
,tour
km
}。
[0094]
本发明实施例提供的一种配送路径方案示意图如图3所示，图3中路径共有4条。实线的trip1和trip2属于车a，共同构成了toura。虚线的trip3和trip4属于车b，共同构成了tourb。其中，客户t5分别被车a和b各配送了一次。在蚁群算法中，蚂蚁模拟车辆，遵循状态转移规则在节点间移动，从而完成配送方案的构造。因此状态转移规则是蚁群算法中构造路径的关键步骤之一，它决定着蚂蚁基于何种方式选择下一个节点。一般地，蚂蚁根据节点的吸引力来随机选择。节点的吸引力越大，选择它的概率越高。传统蚁群算法中常使用信息素浓度与节点间距离作为启发式因子。除此以外，根据pdm-cmd问题特点，将断货紧迫性以及装载率作为衡量转移概率的关键性指标，以提升蚂蚁的寻优能力。
[0095]
配送路径的构建中采用车辆并行路径构建策略。即蚂蚁先模拟车辆集合k＝{k1,k2,
…
,km}中的一台车k，按照路径构造规则移动r次(r为[1,2]的随机整数)，并更新网络中的油罐容量与车辆状态等信息。然后再切换模拟车k+1，在更新后的网络中按规则移动r次。直到配送量满足总配送量区间要求h-≤qtotal≤h
+
，从而得到一个可行解。
[0096]
蚂蚁在行驶的路径中会释放信息素，以吸引后续的蚂蚁选择这条路径。网络中所有节点间的边上均设定了初始信息素浓度。当种群内所有蚂蚁均完成可行解的构造后，需要对网络中各条边的信息素进行更新。针对pdm-cmd问题，对信息素更新采用精英蚂蚁策略
与max-min策略。
[0097]
变邻域算法采用贪婪算法思想生成初始解，并从订单，配送量，服务时间三个维度设计了9个邻域结构，并采用vns框架对初始解进行优化。
[0098]
本发明采用的变邻域算法分为抖动阶段和局部搜索阶段，抖动阶段会随机选择一个抖动邻域结构中的一个解作为新解，然后采用局部搜索在新解的邻域中寻找局部最优解。局部搜索阶段具体来说，如果该解比当前解更优，则以该解作为新的当前解，从第一个邻域开始搜索，否则继续搜索下一个邻域。为提高效率减少运行时间，邻域结构采用最先改进策略，为邻域内设置局部最大迭代次数max_iter2，在max_iter2次循环内找到更优方案则立即停止本邻域的迭代，更新最好解并跳回第一个邻域，若迭代数达到max_iter2仍未找到更好解，则跳到下一个邻域。vns算法的终止条件是，完成全部邻域结构搜索的次数达到v_iter，即有v_iter次搜索过全部邻域结构，都没有找到比当前解更好的解即完成搜索。
[0099]
针对pdm-cmd问题的特点，从订单、配送量和服务时间三个维度对配送方案进行局部优化，设计订单交换、缺货优化、同加油站配送优化、非必要配送优化4个类别共9个邻域结构。其中单回路内订单交换邻域结构、多回路间订单交换邻域结构与单回路缺货优化邻域结构为抖动邻域结构，全部9个邻域结构都为局部搜索邻域结构。各邻域结构设计如下：
[0100]
(1)随机订单的位置优化
[0101]
订单的交换可能对行驶成本与缺货成本的减少带来积极影响，本发明设计单行程内订单交换、单回路内订单交换和及多回路间订单交换三个邻域结构。
[0102]
1)单行程内订单交换邻域结构
[0103]
随机选择某台车的一个行程trip，在trip上随机选择两个订单o1和o2，交换两订单位置。图4为本发明实施例提供的一种单行程内订单交换邻域结构示意图，图4中方形代表油库节点，三角形代表油罐节点，三角形中的数字代表配送这个油罐需要的隔舱数。
[0104]
需要强调的是，如果交换的订单所涉及的油罐后续还有其它配送订单，则该交换操作可能会影响后续配送的时间窗，从而影响后续路径的成本以及其它相关车辆的订单交付时间。因此为了判断改变后的新解是否能满足调度期约束，以及成本是否减少，需要对新解中所有订单的交付时间与总成本重新进行计算。同理，其它邻域结构也需要如此处理。
[0105]
2)单回路内订单交换邻域结构
[0106]
图5为本发明实施例提供的一种单回路内订单交换邻域结构示意图，随机选择某台车a的回路toura，在toura上随机选择满足约束的两个订单o1和o2，交换两个订单位置，从而形成新解。
[0107]
约束：所选o1和o2所用隔舱数相同；所有油罐车最终返回油库的时间早于调度期结束时刻。
[0108]
3)多回路间订单交换邻域结构
[0109]
图6为本发明实施例提供的一种多回路间订单交换邻域结构示意图，附图6所示，随机选择某台车a的行程toura，找到toura上缺货成本最大的订单o1。随机选择某台车b的行程tourb，随机选择tourb上满足约束的订单o2，交换两订单位置，从而形成新解。
[0110]
约束：所选o1和o2所用隔舱数相同；交换后o1和o2都不应到达过晚造成缺货；toura，tourb最后一次返回油库时间早于调度期结束时刻。
[0111]
(2)缺货订单的优化
[0112]
减少缺货成本是vns邻域结构设计的重要方向。缺货优化邻域结构的设计思路借鉴了自适应大邻域搜索算法(alns)中的worst-time移除算子，根据pdm-cmd问题的特点进行改编，设计同回路缺货优化邻域结构与多回路缺货优化邻域结构。
[0113]
1)单回路缺货优化邻域结构
[0114]
图7为本发明实施例提供的一种单回路缺货优化邻域结构示意图，随机选择某台车a的行程toura，找到toura内缺货成本最大的订单o1，将o1从toura内移除，再重新插入至toura内。以不违反可用隔舱约束为前提，可调整toura内油库节点的位置。
[0115]
如图7所示，假设车辆隔舱数为3，将o1插入o2与o3之间后，第一个行程所需隔舱数变为5，不再满足隔舱约束，因此在行程所需隔舱数达到3后，让车辆返回油库装油后再出发，即可在满足隔舱约束的前提下完成此回路上各订单的配送。令o1遍历插入toura内所有位置，找到满足约束且使成本最小的插入位置，形成新解。
[0116]
约束：o1插入后不需要等待，即晚于订单容纳点ut1到达；o1插入后，新方案中所有车最后一次返回油库时间早于调度期结束时刻。
[0117]
2)多回路缺货优化邻域结构
[0118]
随机选择某台车a的行程toura，找到toura内缺货成本最大的订单o1，将o1从toura内移除。随机选择某台车b的行程tourb，随机选择tourb的订单o2。将o1与o2交换。遍历交换o1与tourb内所有可交换订单，找到满足约束且使成本最小的交换方式与调整后方案。
[0119]
约束：o1交换后不需要等待，即晚于订单容纳点ut1到达；o1，o2所用隔舱数相同；o1，o2交换后，新方案中所有车最后返回油库时间早于调度期结束时刻。
[0120]
(3)同加油站订单的拼车优化
[0121]
在pdm-cmd问题中，某些油罐属于同一加油站，它们之间距离为0。若将同一加油站的订单进行拼车配送，显然会对行驶成本的降低有积极影响。基于此本发明针对同加油站的配送订单设计一个邻域结构。
[0122]
1)同加油站订单拼车邻域结构
[0123]
依据配送方案，找到属于同一加油站但不属于同一油罐，且开始服务时刻相差小于一定时间间隔(如30min)，且不属于同一个回路的订单对放入集合e，并按各个订单对的开始服务时刻之差从小到大排序。按顺序取第一个订单对(o1,o2)，o1∈toura,o2∈tourb进行拼车操作。共有4种插入方式：将o1从toura移除，插入tourb中的o2之前或之后；将o2从tourb移除，插入toura中的o1之前或之后。找到满足约束且使成本最小的新解。若新解的成本得到减少，则退出；若新解的成本没有得到减少，则按顺序从集合e中选择下一个订单对并执行同样的插入操作，直到找到更好解或者遍历集合e中所有订单对为止。
[0124]
(4)非必要配送订单的优化
[0125]
若油罐节点i的期末库存能够满足在下期初t0内的需求，则没有必要再对油罐i进行配送。但为了保证全部油罐的总配送量在[h-,h
+
]内，可能需要对这些已经满足期末库存要求的油罐再进行配送。称这种配送为非必要配送订单。这部分订单具有一定的优化空间，有利于整体成本的进一步降低，因此设计三个邻域结构对非必要配送订单进行优化。
[0126]
1)缺货优先单回路订单转移邻域结构
[0127]
将非必要配送订单转移到下期初缺货成本较大的油罐上，则能有效减少缺货成本。
[0128]
首先将所有下期初发生缺货的油罐放入集合e。再随机选择某台车a的行程toura，依据配送方案，随机选择toura中一个非必要配送订单o1，将其配送量保留，遍历选择集合e中的油罐，将上述配送量赋给该油罐，找到符合调度期约束且使成本最小的方案。
[0129]
2)多回路非必要订单交换邻域结构
[0130]
非必要配送订单无论何时以何顺序配送，都不会引起卸油成本和缺货成本的变化，但访问的顺序会改变行驶成本，所以此邻域结构试图找到非必要配送订单的合理访问顺序，以减小行驶成本。
[0131]
随机选择某两台车的回路toura，tourb，依据配送方案，找到toura，tourb[0132]
中断货点晚于下调度期初t0时刻的非必要配送订单，分别放入集合fa与fb。从fa与fb中各随机取一个订单，组成订单对，交换两订单位置，形成新解。若新解的成本得到减少且符合约束，则退出；若新解的成本没有得到减少，则取下一对订单执行同样的交换操作，直到找到更好解或者遍历fa与fb集合所能形成的所有订单对为止。约束：新解中所有车返回油库时间均早于调度期结束时刻。
[0133]
3)非必要订单移除邻域结构
[0134]
将非必要配送订单移除，是减小总成本最直接的方式，但考虑到[h-,h
+
]的配送总量区间要求，在消除部分非必要配送订单后，可能需要在其他装载率较低的订单中增加配送量。具体策略为，随机选择某台车的行程toura，依据配送方案，找到toura中非必要配送订单，并放入集合fa。随机选择一个fa中的订单o1，将o1从toura中移除。计算配送方案中各订单的隔舱装载率，从装载率最低的订单开始增加配送量(须满足约束)，直到配送量满足总量区间要求。
[0135]
约束：增加配送量后所需隔舱数不增加，新方案中所有车最后一次返回油库时间早于调度期结束时刻。
[0136]
蚁群算法每次迭代后，对精英蚂蚁生成的解分别采用变邻域搜索算法进行优化。通过蚁群与变邻域搜索的多次迭代逐渐使可行解向最优解逼近，从而得到满意的配送方案。
[0137]
综上所述，本发明实施例方法将aco和vns相结合，设计了求解pdm-cmd问题的混合启发式算法aco-vns。针对问题特点，设计了配送量离散化的配送网络构建策略以及车辆并行路径构建策略，并从订单、配送量、服务时间三个维度设计了四类共九个邻域结构。经实验证实aco-vns算法具有优秀的算法性能，所求解具有同加油站油罐的订单拼车配送、优先配送断货紧迫性高客户、装载率高等优质解的特点，且可解决实际规模pdm-cmd问题，从而为企业制定成品油二次配送计划提供决策支持。
[0138]
本发明实施例方法梳理了pdm-cmd问题相关的供应链推拉策略相关理论，并提出了成品油二次配送场景下的推式配送模式。建立了pdm-cmd问题的混合整数数学规划模型，提出了推式配送模式下、考虑罐容约束的连续配送、多行程、多隔舱的车辆路径问题pdm-cmd。
[0139]
本发明实施例方法在蚁群算法中将油罐的配送量离散化，将离散后的各个配送量与油罐以及配送次数结合，共同构建节点，同时针对pdm-cmd问题特点设计了启发式因子与车辆并行构建路径策略。变邻域搜索算法中采用贪婪算法思想生成初始解，并从订单，配送量，服务时间三个维度设计了9个邻域结构对初始解按照vnd框架进行调整与优化。将两种
算法相结合在蚁群每次迭代后，对精英解应用vns算法进一步优化，从而构建一种融合vns的混合aco算法。
[0140]
本发明实施例方法定义了拉式/推式配送模式，提出了pdm-cmd问题并建立了混合整数规划模型，丰富了vrp问题理论体系。该问题同时考虑了推式配送模式、多隔舱、多行程、罐容约束、多次连续配送等复杂场景，相较于其它同类研究，问题更加复杂、解空间更加庞大、求解难度更大，也更具实用价值。
[0141]
本领域普通技术人员可以理解：附图只是一个实施例的示意图，附图中的模块或流程并不一定是实施本发明所必须的。
[0142]
通过以上的实施方式的描述可知，本领域的技术人员可以清楚地了解到本发明可借助软件加必需的通用硬件平台的方式来实现。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品的形式体现出来，该计算机软件产品可以存储在存储介质中，如rom/ram、磁碟、光盘等，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个实施例或者实施例的某些部分所述的方法。
[0143]
本说明书中的各个实施例均采用递进的方式描述，各个实施例之间相同相似的部分互相参见即可，每个实施例重点说明的都是与其他实施例的不同之处。尤其，对于装置或系统实施例而言，由于其基本相似于方法实施例，所以描述得比较简单，相关之处参见方法实施例的部分说明即可。以上所描述的装置及系统实施例仅仅是示意性的，其中所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部模块来实现本实施例方案的目的。本领域普通技术人员在不付出创造性劳动的情况下，即可以理解并实施。
[0144]
以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到的变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应该以权利要求的保护范围为准。

技术特征：
1.一种推式配送模式下加油站连续多次补货的配送优化方法，其特征在于，包括：将每个油罐作为客户，将每个客户的每次成品油配送需求作为一个订单，获取每个调度期中各个客户的订单；根据所设计的配送量离散化的配送网络构建策略完成配送网络构建，根据所设计的车辆并行路径构建策略完成配送路径的构建；以所有客户的订单的运输成本、车辆卸油成本与缺货成本构成的总成本最小为目标，基于所述配送网络和配送路径建立连续多次配送、多行程、带隔舱的车辆路径问题问题的混合整数数学规划模型；采用融合变邻域搜索算法的蚁群算法迭代求解所述混合整数数学规划模型的目标函数，完成每次迭代后，采用变邻域搜索算法对精英蚂蚁生成的解进行优化，输出迭代完成后的最优解，得到各个客户的订单的配送方案。2.根据权利要求1所述的方法，其特征在于，所述的根据所设计的配送量离散化的配送网络构建策略完成配送网络构建，包括：将各加油站内装着不同油品的油罐表示为节点，车辆在中途需要多次到油库装油，为表示油库节点每次被访问的状态，为每台车设置一个虚拟的油库节点，用有向图g＝(v,e)表示成品油的配送网络，v表示顶点集，v＝c∪f0∪f1，c＝{1,
…
n}表示油罐节点集合，n表示油罐的总数，f0＝{n+1,
…
,n+n}表示起点油库的虚拟油库集合，f1＝{n+m+1,
…
,n+2m}表示终点油库的虚拟油库集合，m表示油罐车的总量，车辆k始终从油库节点n+k装油并出发，配送后返回节点n+m+k。e表示边集，e＝{(i,j)|i,j∈v,i≠j}。3.根据权利要求2所述的方法，其特征在于，所述的根据所设计的车辆并行路径构建策略完成配送路径的构建，包括：采用车辆并行路径构建策略构建配送路径，将车辆k每一趟的成品油配送方案称为一个行程trip，车辆k在调度期内执行的所有行程trip构成车辆k的回路tour
k
，蚂蚁f模拟车队所构造的路线称为蚂蚁f的配送路径方案plan
f
＝{tour
k1
,tour
k2
,
…
,tour
km
}。4.根据权利要求2或者3所述的方法，其特征在于，所述的以所有客户的订单的运输成本、车辆卸油成本与缺货成本构成的总成本最小为目标，基于所述配送网络和配送路径建立连续多次配送、多行程、带隔舱的车辆路径问题问题的混合整数数学规划模型，包括：以所有客户的订单的运输成本、车辆卸油成本与缺货成本构成的总成本最小为目标，基于所述配送网络和配送路径建立连续多次配送、多行程、带隔舱的车辆路径问题问题的混合整数数学规划模型的目标函数为：min(c1+c2+c3)))所述总成本由三部分构成，第一部分c_1为车辆的运输成本，与车辆行驶距离相关，第
二部分c2为车辆卸油成本，与卸油时长相关，第三部分c3为缺货成本，由销售损失来表示；所述混合整数数学规划模型的约束条件包括：节点访问约束、配送量约束与时间约束，具体如下：节点访问约束包括：节点访问约束包括：节点访问约束包括：节点访问约束包括：节点访问约束包括：节点访问约束包括：节点访问约束包括：节点访问约束包括：节点访问约束包括：节点访问约束包括：节点访问约束包括：节点访问约束包括：节点访问约束包括：节点访问约束包括：节点访问约束包括：
上述式子依次表示油罐车到达油罐节点后必须离开该节点；油罐车从专属虚拟油库节点出发并到达专属虚拟油库节点，且在调度期内同一台油罐车运行趟数有上限；每台车都需要被启用；如果节点第r次访问不存在，则一定不存在第r+1次配送；节点之间的访问顺序约束，应从虚拟油库起点出发，访问若干油罐后，返回虚拟油库终点，然后再从虚拟油库起点出发或终止行程；节点的某次访问最多只能作为路线的到达节点一次，离开节点一次。配送量约束包括：配送量约束包括：配送量约束包括：配送量约束包括：配送量约束包括：配送量约束包括：其中，式1表示从车场出发时油罐车的可用隔舱数都为n；式2表示配送方案中前后两个访问节点的可用隔舱数关系，后访问节点的可用隔舱数为前节点的可用隔舱数减去前节点所需隔舱数，以及油罐车的最大隔舱限制；式3表示油罐的每次配送量不能超过车辆容量，且每个隔舱至少要达到最小装载率要求；式4表示一个订单，只由一个车次满足；式5表示对于油罐节点，如果存在某次访问，则必需在这次访问中对其配送；式6表示调度期内供应总量要满足上下限要求；时间相关约束包括：时间相关约束包括：时间相关约束包括：时间相关约束包括：时间相关约束包括：时间相关约束包括：x
irjsk
,s
ir
∈{0,1}其中，式1表示同一油罐前后两次服务存在时间先后顺序，第r+1次补货一定在第r次补货后；式2表示同一节点前后两次访问存在时间先后顺序，第r+1次访问一定在第r次访问后；式3、4表示油罐车配送路径上前后节点的到达时间关系；油库到油罐节点的路径上，油库出发时刻加行驶时长为到达油罐节点时刻；油罐到油罐节点或油库节点的路径上，前一油罐节点到达时刻加等待时长加卸油时长加行驶时长为到达后一节点的时刻；式5表示油罐车需在调度期内工作，即在调度期开始后离开油库，在调度期结束前返回油库；式6表示，车辆回到油库后需要消耗一定时间装油后再出发；式7是0-1变量约束。5.根据权利要求4所述的方法，其特征在于，所述的采用融合变邻域搜索算法的蚁群算
法迭代求解所述混合整数数学规划模型的目标函数，完成每次迭代后，采用变邻域搜索算法对精英蚂蚁生成的解进行优化，输出迭代完成后的最优解，得到各个客户的订单的配送方案，包括：初始化各参数，设置迭代次数为t
←
1、最大迭代次数为max_iter，蚂蚁种群为ant，在每一轮迭代计算过程中，从ant中依次选取每个蚂蚁f，根据并行路径构建规则生成蚂蚁f的可行解s
f
，对精英蚂蚁生成的解采用变邻域算法优化，采用精英蚂蚁策略和max-min策略进行信息素更新，进行下一轮的迭代计算过程，直到迭代计算收敛，输出迭代完成后的最优解，得到各个客户的订单的配送方案。6.根据权利要求5所述的方法，其特征在于，所述的对精英蚂蚁生成的解采用变邻域算法优化，包括：采用变邻域算法基于贪婪算法思想生成初始解，所述变邻域算法分为抖动阶段和局部搜索阶段，在抖动阶段，随机选择一个抖动邻域结构中的一个解作为新解，在局部搜索阶段，采用局部搜索在新解的邻域中寻找局部最优解，如果该局部最优解比当前解更优，则以该局部最优解作为新的当前解，从第一个邻域开始搜索，否则继续搜索下一个邻域，邻域结构采用最先改进策略，为邻域内设置局部最大迭代次数max_iter2，在max_iter2次循环内找到更优方案则立即停止本邻域的迭代，更新最优解并跳回第一个邻域，若迭代数达到max_iter2仍未找到更好解，则跳到下一个邻域，当v_iter次搜索过全部邻域结构，都没有找到比当前解更好的解即完成搜索。7.根据权利要求6所述的方法，其特征在于，所述的采用变邻域算法基于贪婪算法思想生成初始解，包括：基于贪婪思想以避免缺货为原则构建初始解，采用车辆并行路径构建策略，车辆每次选择客户节点时，均以当前配送网络状态为基础，选择断货时间最小的客户，而配送量则设置为不发生等待的最大值，不断重复上述过程，直到总配送量达到总配送量区间[h-,h
+
]，得到初始解。8.根据权利要求5所述的方法，其特征在于，所述的变邻域算法包括：订单交换、缺货优化、同加油站配送优化和非必要配送优化4个类别共9个邻域结构，其中单回路内订单交换邻域结构、多回路间订单交换邻域结构与单回路缺货优化邻域结构为抖动邻域结构，全部9个邻域结构都为局部搜索邻域结构。

技术总结
本发明提供了一种推式配送模式下加油站连续多次补货的配送优化方法。该方法包括：将每个油罐作为客户，将每个客户的每次成品油配送需求作为一个订单，获取每个调度期中各个客户的订单；构建配送网络和配送路径，基于配送网络和配送路径建立连续多次配送、多行程、带隔舱的车辆路径问题问题的混合整数数学规划模型；采用混合蚁群算法迭代求解混合整数数学规划模型，完成每次迭代后，采用变邻域搜索算法对精英蚂蚁生成的解进行优化，输出迭代完成后的最优解，得到各个客户的订单的配送方案。本发明方法同时考虑了推式配送模式、多隔舱、多行程、罐容约束、多次连续配送等复杂场景，更具实用价值，以实现有效地对成品油进行物流配送。送。送。


技术研发人员：刘志硕
受保护的技术使用者：北京交通大学
技术研发日：2023.05.19
技术公布日：2023/10/6