一种基于拉格朗日松弛的工业烟草物流调度方法与流程

本发明属于物流运输调度领域，具体的说是一种基于拉格朗日松弛的工业烟草物流调度方法。

背景技术：

目前，工业类公司的物流相关技术的发展水平，已经开始直接影响该公司的核心竞争力。现如今部分工业烟草物流企业发展水平较低，卷烟运输调度工作主要依赖于调度人员人工凭经验进行订单合并配载，这种最为原始的方式对于目前订单量来说效率是极其低下的，工人在有限的工作时间内仅能凭经验考虑到极小部分的订单配载方案，这种较为落后的调度方式直接导致了工业烟草物流企业服务水平低、运输效率低下且运输成本高的现状。

工业烟草物流运输调度问题属于车辆配送路径优化问题范畴，是国内顶尖物流企业所研究的核心问题之一，在物流运输与资源分配领域中普遍存在的，由运筹学期刊命名为车辆路径问题，即：vrp，vehicleroutingproblem。vrp并不是单独表示一个问题，而是指一类组合优化问题，经典的vrp指调度系统根据客户提出的需求以及现有车辆，制定出相应的运输方案，在满足客户需求的前提下使得总的运输费用最少。

目前，大部分工业烟草物流公司整合现有系统并引入先进技术与新型设备，如何将现有相关领域研究成果与工业烟草物流运输相结合，发明一种操作简单、适用且效果好的方法和系统来优化工业烟草物流运输调度水平，是工业烟草物流公司当前亟待解决的问题之一。

技术实现要素：

本发明是为了解决上述现有技术存在的不足之处，提出一种基于拉格朗日松弛的工业烟草物流调度方法，以期能快速得到工业烟草公司的最优调度方案，从而提高运输效率和运输调度水平并降低运输成本。

为了达到上述发明目的，本发明采用如下技术方案：

本发明一种基于拉格朗日松弛的工业烟草物流调度方法的特点是将处于订单集合中的m个订单按照不同的顺序组合后形成n条路径并构成可行路径集合，在所述可行路径集合中选出k条路径作为调度方案；

令由m个订单构成的订单集合记为i＝{i1,i2,...,ii,...,im}，ii表示第i个订单，1≤i≤m；

令由n条路径构成的可行路径集合记为p＝{p1,p2,...,pp,...,pm}，pp表示第p条路径，1≤p≤n；

令由k条路径构成的最优调度方案记为xb，xb∈p，1≤k≤n；

令第p条路径pp的实际支付价格记为cp、第p条路径pp的基础运费记为第p条路径pp的多点运输所节约的费用记为若第p条路径pp为单点运输路径，则令

令第p条路径pp所服务的订单集合记为i′p，令可服务第i个订单ii的所有路径集合记为pi′；

所述工业烟草物流调度方法包括以下步骤：

步骤1、获取订单数据：

获取当前需运输的订单集合i中的每个订单的信息，包括：订单编号、起点编号、终点编号、卷烟件数、最晚送达时间；

步骤2、枚举可行路径集合p：

步骤2.1、生成集合i中第i个订单ii对应的单点运输路径并分别加入可行路径集合p及集合pi′，计算所有单点运输路径的实际支付价格；

步骤2.2、生成多点运输路径：

步骤2.2.1、对于订单集合i，枚举出所有订单个数在2-a之间的多点运输路径，并计算枚举出的每条多点运输路径的实际支付价格、基础运费、多点运输所节约的费用；a为所设定的订单数量；

步骤2.2.2、若多点运输路径中的第p条路径pp满足如下三个条件，则将第p条路径pp加入可行路径集合p及pi′：

1、第p条路径pp所服务的订单集合ip′中所有订单均能在最晚到货时间之前送达；

2、

3、第p条路径pp的总运量小于等于现有最大车辆的容量；

步骤3、建立集合分割模型，即sp模型：

利用式(1)建立目标函数zsp：

式(1)中，xp表示是否选择第p条路径pp，若xp＝0，则表示将第p条路径pp加入最优调度方案xb，若xp＝1，则表示将第p条路径pp不加入最优调度方案xb；

利用式(2)和式(3)建立约束条件：

步骤4、松弛约束条件：

利用拉格朗日乘子向量λ将式(2)松弛到目标函数中，得到如式(4)和式(5)所构成的松弛后的lrp模型：

xp∈{0,1},p∈p(5)

式(4)中，λi表示订单集合i中第i个订单ii所对应格朗日乘子向量λ中的第i行；

步骤5、初始化拉格朗日方法的参数：

定义当前迭代次数为l，并初始化l＝0，定义最大迭代为次数为lmax，定义步长为θ；

定义第l次迭代的求解上界连续更新失败次数为并初始化

定义第l次迭代的求解上界连续更新失败次数的阈值为并初始化

定义最大连续两次下界相较误差为lbgapmax；定义第l次迭代的连续两次下界相较误差为lbgap^l，并初始化第l次迭代的连续两次下界相较误差lbgap^l＝0；

定义并初始化最优上界为ub＝0，定义第l次迭代的上界为curub^l，并初始化第l次迭代的上界为curub^l＝0；

定义并初始化最优下界为lb＝0，定义第l次迭代的下界为curlb^l，并初始化第l次迭代的下界为curlb^l＝0；

定义第l次迭代的拉格朗日乘子向量为λ^l；

定义并初始化最优解为最优调度方案xb、第l次迭代所得到的调度方案为

第l次迭代的调度方案服务所述订单集合i中每个订单次数的数组记为s^l，为第l次迭代的调度方案服务订单集合i中第i个订单ii的次数；

定义第l次迭代的路径成本为负的路径集合记为

第l次迭代的路径成本为负的路径集合服务所述订单集合i中每个订单次数的数组记为为第l次迭代服务订单集合i中第i个订单ii的次数；

定义为第l次迭代集合中所有能够服务订单集合i中第k个订单ik的路径集合；

步骤6、构建初始可行解，并将初始可行解中所有单点运输路径加入最优调度方案xb，在第p条单点运输路径pp加入最优调度方xb时，将ub cp赋值给ub；

步骤7、更新路径当前成本：

第l次迭代的第p条路径pp的当前成本记为对令

步骤8、更新第l次迭代的下界curlb^l、最优下界lb及第l次迭代的两次下界相较误差lbgap^l：

步骤8.1、若则将第p条路径pp加入路径集合将赋值给curlb^l；

步骤8.2、计算lbgap^l＝|curlb^l-lb|/lb，当curlb^l＞lb时，令lb＝curlb^l；

步骤9、判断是否满足上界更新条件：

若lbgap^l<lbgapmax，则转入步骤10，否则，转入步骤12；

步骤10、更新第l次迭代的调度方案及第l次迭代的上界curub^l；

步骤11、更新最优调度方案xb：

如果curub^l＜ub，则令ub＝curub^l，令令lcon-fail＝0，否则，xb保持不变，将值赋给

步骤12、利用式(6)所示的次梯度方法得到第l 1次迭代的拉格朗日乘子向量λ^{l 1}：

式(6)中，表示第l次迭代中集合中可服务订单集合i中第i个订单ii的路径数与1的差值，且为第l次迭代的第p条路径pp选取次数值，范围为0-1之间；

步骤13、迭代终止条件：

将l 1赋值给l，若l＞lmax或则停止迭代，输出最优调度方案xb，否则返回步骤7顺序执行。

本发明所述的基于拉格朗日松弛的工业烟草物流调度方法的特点也在于，所述步骤10是按如下步骤进行：

步骤10.1、更新第l次迭代的数组

步骤10.1.1、定义变量i＝1；

步骤10.1.2、定义变量j＝1，定义为中第i条路径；

步骤10.1.3、定义为路径所服务的订单集合中第j个订单，定义为订单集合i中的第k个订单ik，将路径加入同时将赋给表示第l次迭代时中可服务订单集合i中第k个订单ik路径和个数；

步骤10.1.4、若j大于路径所服务订单总数，则返回步骤10.1.2，否则将j 1赋值给j，返回步骤10.1.3；

步骤10.1.5、若i大于集合中路径总数，则将i 1赋值给i并转入步骤10.2；

步骤10.2、对于若满足等于1，将集合中唯一路径pp加入第l次迭代的调度方案并令表示第l次迭代时中可服务订单集合i中第i个订单ii的路径集合；

定义第p条单点运输路径pp所服务除订单ii以外所有订单集合为对于令及表示第l次迭代时中可服务订单集合i中第j个订单ij路径和个数，表示第l次迭代时中可服务订单集合i中第j个订单ij路径和个数；

步骤10.3、执行修复操作1：

对于若满足则对集合中所有路径按照评估准则进行评估，选择最优的路径加入后，令及

定义最优路径所服务除订单ii以外所有订单集合为对于令及

所述评估准则为：优先选择所服务订单数最大且值较大的路径；

步骤10.4、若均满足转入步骤11，否则，转入步骤10.4.1执行修复操作2；

步骤10.4.1、定义并初始化未被所服务的订单集合为对于若满足将第i个订单ii加入

步骤10.4.2、枚举出所有多点运输路径，并生成未被所服务的订单枚举出的修补可行路径集合

步骤10.4.3、利用基本贪婪方法从挑选出修复路径集合并加入xcur；

步骤10.5、对于将curub^l cp赋值给curub^l。

所述步骤10.4.3中的基本贪婪方法是按如下步骤进行：

步骤10.4.3.1、定义记录可服务中各个订单的路径集合所构成的集合为

步骤10.4.3.2、定义变量i＝0；

步骤10.4.3.3、定义变量j＝0，为中第i条路径；

步骤10.4.3.4、定义ij为路径所服务的订单集合中第j个订单，ij为订单集合i中的第k个订单ik，将路径加入为记录中可服务订单集合i中的第k个订单ik所有路径集合；

步骤10.4.3.5、若j大于路径所服务订单总数，则返回步骤10.4.3.3，否则，将j 1赋值给j，返回步骤10.4.3.4；

步骤10.4.3.6、若i大于集合中路径总数，则转入步骤10.4.3.7，否则，将i 1赋值给i并返回步骤10.4.3.3；

步骤10.4.3.7、找到中多点运输所节约的费用最大的路径加入后，从删除路径并将所有可服务于路径所服务订单的路径从中删除；

步骤10.4.3.8、终止条件判断：

若路径集合为空集合，则进入步骤10.4.3.9，否则，进入步骤10.4.3.7；

步骤10.4.3.9、对于当满足时，将订单集合i中第i个订单ii对应单点运输路径加入集合

步骤10.4.3.10、令curub^l＝0；将curub^l cp值赋给curub^l。

与已有技术相比，本发明的有益效果体现在：

1、本发明在工业烟草物流日需运输订单数稳定、多点运输路径最大服务订单数少、运输任务外包及支付费用计算规则确定的特点，研究工业烟草物流公司的卷烟运输调度问题，首先针对日需运输订单数稳定、多点运输路径最大服务订单数少的特点枚举得到可行路径集合；随后基于可行路径集合与集合分割模型建立sp模型，再根据拉格朗日松弛方法松弛sp模型中较难处理的约束条件得到lrp模型；最后，在拉格朗日松弛算法的基础上引入贪婪思想，设计出基于集合分割模型的拉格朗日松弛算法，利用下界、上界、拉格朗日乘子、路径当前成本更新规则，来提升下界与降低上界，实现了多次迭代，最终获得最优调度方案，基于集合分割模型的拉格朗日松弛算法在时间有效性和结果的优化程度上，是一种性能更好的优化工业烟草物流运输调度问题的近似算法；该工业烟草物流调度方法解决了工业烟草物流公司卷烟运输调度问题，给出优秀的调度方案，提升了工业烟草物流公司运输效率与服务水平、降低了工业烟草物流公司运输支出。

2、本发明在基于集合分割模型的拉格朗日松弛算法迭代计算过程中，在下界提升到所要求标准时再执行上界更新程序，解决了迭代前期更新上界过于耗时的问题，在保证上界更新效果的同时，极大程度提升了算法的求解速度，从而能快速得到最优调度方案。

3、本发明在基于集合分割模型的拉格朗日松弛算法迭代计算过程中，首先利用基于集合覆盖思想设计的求解办法构建当前解，随后基于贪婪思想对当前解进行修复操作，在保证当前解的质量的同时，极大程度提升了当前解的求解速度，从而能在工业烟草卷烟运输调度时，在短时间内给出一个运费低、效率高的配载方案。

附图说明

图1为本发明工业烟草物流运输调度方法的流程图。

具体实施方式

本实施实例中，一种基于拉格朗日松弛的工业烟草物流调度方法，是用于服务工业烟草物流公司卷烟运输的调度工作，针对工业烟草物流企业和运输任务特点，结合工业烟草物流企业与物流企业发展方向，以车辆路径问题重要研究成果为主要手段，通过分析工业烟草物流现状来建立相应数学模型，并设计制定出适合工业烟草物流企业使用且有明显效果的调度方法，其流程如图1所示，针对工业烟草物流卷烟运输调度问题特性枚举出可行路径集合，基于集合分割模型建模，基于拉格朗日松弛方法松弛模型中较难处理的约束，然后sp-lr算法求解，从而得到一套运输调度方案，仅能快速找到较好的运输调度方案来降低工业烟草物流公司的运费支出以及提升其服务水平，还能降低执行调度方案的第三方物流运输公司的运输成本，达到了双赢的局面。

具体地说，是将处于订单集合的m个订单进行考虑顺序的组合后生成n条路径构成可行路径集合，在可行路径集合中选择出k条路径作为调度方案；

将处于订单集合中的m个订单按照不同的顺序组合后形成n条路径并构成可行路径集合，在可行路径集合中选出k条路径作为调度方案；

令由m个订单构成的订单集合记为i＝{i1,i2,...,ii,...,im}，ii表示第i个订单，1≤i≤m；

令由n条路径构成的可行路径集合记为p＝{p1,p2,...,pp,...,pm}，pp表示第p条路径，1≤p≤n；

令由k条路径构成的最优调度方案记为xb，xb∈p，1≤k≤n；

令第p条路径pp的实际支付价格记为cp、第p条路径pp的基础运费记为第p条路径pp的多点运输所节约的费用记为若第p条路径pp为单点运输路径，则令

令第p条路径pp所服务的订单集合记为i′p，令可服务第i个订单ii的所有路径集合记为pi′；

所述工业烟草物流调度方法包括以下步骤：

步骤1、获取订单数据：

获取当前需运输的订单集合i中的每个订单的信息，包括：订单编号、起点编号、终点编号、卷烟件数、最晚送达时间；

步骤2、枚举可行路径集合p，工业烟草物流调度问题中，每个订单起终点、订单量及最晚送达时间是已知的，可接受的配载方式也是已知的且多点运输时最大点数较少，在当前日均业务量下，能够在较短时间内枚举出所有可行的单点运输路径和多点运输路径，通常枚举100个订单的可行路径集合所花费时间不超过1秒；

步骤2.1、首先生成所有单点运输路径，生成集合i中第i个订单ii对应的单点运输路径并分别加入可行路径集合p及集合pi′，计算所有单点运输路径的实际支付价格；

步骤2.2、生成多点运输路径：

步骤2.2.1、对于订单集合i，枚举出所有订单个数在2-a之间的多点运输路径，并计算枚举出的每条多点运输路径的实际支付价格、基础运费、多点运输所节约的费用；a为所设定的订单数量；

步骤2.2.2、若多点运输路径中的第p条路径pp满足如下三个条件，则将第p条路径pp加入可行路径集合p及pi′：

4、第p条路径pp所服务的订单集合ip′中所有订单均能在最晚到货时间之前送达；

5、多点运输能够节约运费才有意义；

6、第p条路径pp的总运量小于等于现有最大车辆的容量；

步骤3、建立集合分割模型，步骤2得到可行路径集合p之后，在其中挑选出一部分路径生成调度方案，调度方案的目标是最小化的运费，需要满足每个订单必须且只能被调度方案中的一条路径服务一次，综上目标函数和约束条件是属于集合分割问题范畴，即sp模型：

利用式(1)建立目标函数zsp：

式(1)中，xp表示最优调度方案中是否选择第p条路径pp，若xp＝0，则表示将第p条路径pp加入最优调度方案xb，若xp＝1，则表示将第p条路径pp不加入最优调度方案xb；

利用式(2)和式(3)建立约束条件：

步骤4、松弛约束条件：

sp模型中约束(2)条件苛刻，极大限制了在求解过程中的效率，拉格朗日松弛方法提供了解决思路，利用拉格朗日乘子向量λ将式(2)松弛到目标函数中，得到如式(4)和式(5)所构成的松弛后的lrp模型：

xp∈{0,1},p∈p(5)

式(4)中，λi表示订单集合i中第i个订单ii所对应格朗日乘子向量λ中的第i行，此时目标函数中的路径成本由支付价格cp变为cp-λ(p)的差值，其中先通过求解lrp模型得到近似可行解，求解过程不需要满足约束条件(2)，再在近似可行解基础上找可行解，能够大幅度降低求解时间，提升求解效率；

步骤5、初始化拉格朗日方法的参数：

定义当前迭代次数为l，并初始化l＝0，定义最大迭代为次数为lmax，定义步长为θ；

定义第l次迭代的求解上界连续更新失败次数为并初始化

定义第l次迭代的求解上界连续更新失败次数的阈值为并初始化若上界出现连续20次不更新情况，表明算法已经很难再取得提升，直接终止；

定义最大连续两次下界相较误差为lbgapmax；定义第l次迭代的连续两次下界相较误差为lbgap^l，并初始化第l次迭代的连续两次下界相较误差lbgap^l＝0；

定义并初始化最优上界为ub＝0，定义第l次迭代的上界为curub^l，并初始化第l次迭代的上界为curub^l＝0；

定义并初始化最优下界为lb＝0，定义第l次迭代的下界为curlb^l，并初始化第l次迭代的下界为curlb^l＝0；

定义第l次迭代的拉格朗日乘子向量为λ^l；

定义并初始化最优解为最优调度方案xb、第l次迭代所得到的调度方案为

第l次迭代的调度方案服务所述订单集合i中每个订单次数的数组记为s^l，为第l次迭代的调度方案服务订单集合i中第i个订单ii的次数；

定义第l次迭代的路径成本为负的路径集合记为

第l次迭代的路径成本为负的路径集合服务所述订单集合i中每个订单次数的数组记为为第l次迭代服务订单集合i中第i个订单ii的次数；

定义为第l次迭代集合中所有能够服务订单集合i中第k个订单ik的路径集合；

步骤6、构建初始可行解，并将初始可行解中所有单点运输路径加入最优调度方案xb，在第p条单点运输路径pp加入最优调度方xb时，同时更新最优上界的值将ub cp赋值给ub；

步骤7、更新路径当前成本：

第l次迭代的第p条路径pp的当前成本记为对令

步骤8、更新第l次迭代的下界curlb^l、最优下界lb及第l次迭代的两次下界相较误差lbgap^l：

步骤8.1、若则将第p条路径pp加入路径集合将赋值给curlb^l；

步骤8.2、计算lbgap^l＝|curlb^l-lb|/lb，当curlb^l＞lb时，令lb＝curlb^l；

步骤9、判断是否满足上界更新条件：

若lbgap^l<lbgapmax，则转入步骤10，否则说明第l次迭代所求得近似最优解较差，所以难以以此为基础找到较好的调度方案，直接转入步骤12；

步骤10、更新第l次迭代的调度方案及第l次迭代的上界curub^l：

步骤10.1、更新第l次迭代的数组先在集合中寻找较优的路径加入调度方案：

步骤10.1.1、定义变量i＝1；

步骤10.1.2、定义变量j＝1，定义为中第i条路径；

步骤10.1.3、定义为路径所服务的订单集合中第j个订单，定义为订单集合i中的第k个订单ik，将路径加入同时将赋给表示第l次迭代时中可服务订单集合i中第k个订单ik路径和个数；

步骤10.1.4、若j大于路径所服务订单总数，则返回步骤10.1.2，否则将j 1赋值给j，返回步骤10.1.3；

步骤10.1.5、若i大于集合中路径总数，则将i 1赋值给i并转入步骤10.2；

步骤10.2、对于若满足等于1，将集合中唯一路径pp加入第l次迭代的调度方案并令表示第l次迭代时中可服务订单集合i中第i个订单ii的路径集合；

定义第p条单点运输路径pp所服务除订单ii以外所有订单集合为对于令及表示第l次迭代时中可服务订单集合i中第j个订单ij路径和个数，表示第l次迭代时中可服务订单集合i中第j个订单ij路径和个数；

步骤10.3、执行修复操作1：

对于若满足则表示中有多条路径能够服务订单ii，需要挑选出最好的路径加入调度方案对集合中所有路径按照评估准则进行评估，选择最优的路径加入后，令及

最优的路径可能服务了多个订单，这些订单都被调度方案服务了一次，定义最优路径所服务除订单ii以外所有订单集合为对于令及

所述评估准则为：优先选择所服务订单数最大且值较大的路径，是贪婪的思想；

步骤10.4、若均满足说明满足了sp模型的所有约束条件，得到了可行调度方案，转入步骤11，否则说明目前的调度方案不可行，需要近一步进行修复，转入步骤10.4.1执行修复操作2；

步骤10.4.1、定义并初始化未被所服务的订单集合为对于若满足将第i个订单ii加入

步骤10.4.2、枚举出所有多点运输路径，并生成未被所服务的订单集合枚举出的修补可行路径集合这种方法相比于其他方式能够以最短是时间得到集合

步骤10.4.3、利用基本贪婪方法从挑选出修复路径集合并加入xcur：

步骤10.4.3.1、定义记录可服务中各个订单的路径集合所构成的集合为

步骤10.4.3.2、定义变量i＝0；

步骤10.4.3.3、定义变量j＝0，为中第i条路径；

步骤10.4.3.4、定义ij为路径所服务的订单集合中第j个订单，ij为订单集合i中的第k个订单ik，将路径加入为记录中可服务订单集合i中的第k个订单ik所有路径集合；

步骤10.4.3.5、若j大于路径所服务订单总数，则返回步骤10.4.3.3，否则，将j 1赋值给j，返回步骤10.4.3.4；

步骤10.4.3.6、若i大于集合中路径总数，则转入步骤10.4.3.7，否则，将i 1赋值给i并返回步骤10.4.3.3；

步骤10.4.3.7、找到中多点运输所节约的费用最大的路径加入后，从删除路径并将所有可服务于路径所服务订单的路径从中删除；

步骤10.4.3.8、终止条件判断：

若路径集合为空集合，则进入步骤10.4.3.9，否则，进入步骤10.4.3.7；

步骤10.4.3.9、对于极少数未被当前调度方案所服务的路径，利用单点运输路径进行修复，当满足时，将订单集合i中第i个订单ii对应单点运输路径加入集合

步骤10.4.3.10、令curub^l＝0；将curub^l cp值赋给curub^l；

步骤10.5、计算调度方案中所有路径的支付价格总和，对于将curub^l cp赋值给curub^l；

步骤11、更新最优调度方案xb：

如果curub^l＜ub，则令ub＝curub^l，令令lcon-fail＝0，否则，xb保持不变，将值赋给

步骤12、利用式(6)所示的次梯度方法得到第l 1次迭代的拉格朗日乘子向量λ^{l 1}：

式(6)中，表示第l次迭代中集合中可服务订单集合i中第i个订单ii的路径数与1的差值，且为第l次迭代的第p条路径pp选取次数值，范围为0-1之间；步骤13、迭代终止条件：

将l 1赋值给l，若l＞lmax或则算法达到了终止条件，停止迭代，输出最优调度方案xb，否则返回步骤7顺序执行。

技术特征：

1.一种基于拉格朗日松弛的工业烟草物流调度方法，其特征是将处于订单集合中的m个订单按照不同的顺序组合后形成n条路径并构成可行路径集合，在所述可行路径集合中选出k条路径作为调度方案；

令由m个订单构成的订单集合记为i＝{i1,i2,...,ii,...,im}，ii表示第i个订单，1≤i≤m；

令由n条路径构成的可行路径集合记为p＝{p1,p2,...,pp,...,pm}，pp表示第p条路径，1≤p≤n；

令由k条路径构成的最优调度方案记为xb，xb∈p，1≤k≤n；

令第p条路径pp的实际支付价格记为cp、第p条路径pp的基础运费记为第p条路径pp的多点运输所节约的费用记为若第p条路径pp为单点运输路径，则令

令第p条路径pp所服务的订单集合记为i′p，令可服务第i个订单ii的所有路径集合记为pi′；

所述工业烟草物流调度方法包括以下步骤：

步骤1、获取订单数据：

获取当前需运输的订单集合i中的每个订单的信息，包括：订单编号、起点编号、终点编号、卷烟件数、最晚送达时间；

步骤2、枚举可行路径集合p：

步骤2.1、生成集合i中第i个订单ii对应的单点运输路径并分别加入可行路径集合p及集合pi′，计算所有单点运输路径的实际支付价格；

步骤2.2、生成多点运输路径：

步骤2.2.1、对于订单集合i，枚举出所有订单个数在2-a之间的多点运输路径，并计算枚举出的每条多点运输路径的实际支付价格、基础运费、多点运输所节约的费用；a为所设定的订单数量；

步骤2.2.2、若多点运输路径中的第p条路径pp满足如下三个条件，则将第p条路径pp加入可行路径集合p及pi′：

1、第p条路径pp所服务的订单集合i′p中所有订单均能在最晚到货时间之前送达；

2、

3、第p条路径pp的总运量小于等于现有最大车辆的容量；

步骤3、建立集合分割模型，即sp模型：

利用式(1)建立目标函数zsp：

式(1)中，xp表示是否选择第p条路径pp，若xp＝0，则表示将第p条路径pp加入最优调度方案xb，若xp＝1，则表示将第p条路径pp不加入最优调度方案xb；

利用式(2)和式(3)建立约束条件：

步骤4、松弛约束条件：

利用拉格朗日乘子向量λ将式(2)松弛到目标函数中，得到如式(4)和式(5)所构成的松弛后的lrp模型：

xp∈{0,1},p∈p(5)

式(4)中，λi表示订单集合i中第i个订单ii所对应格朗日乘子向量λ中的第i行；

步骤5、初始化拉格朗日方法的参数：

定义当前迭代次数为l，并初始化l＝0，定义最大迭代为次数为lmax，定义步长为θ；

定义第l次迭代的求解上界连续更新失败次数为并初始化

定义第l次迭代的求解上界连续更新失败次数的阈值为并初始化

定义最大连续两次下界相较误差为lbgapmax；定义第l次迭代的连续两次下界相较误差为lbgap^l，并初始化第l次迭代的连续两次下界相较误差lbgap^l＝0；

定义并初始化最优上界为ub＝0，定义第l次迭代的上界为curub^l，并初始化第l次迭代的上界为curub^l＝0；

定义并初始化最优下界为lb＝0，定义第l次迭代的下界为curlb^l，并初始化第l次迭代的下界为curlb^l＝0；

定义第l次迭代的拉格朗日乘子向量为λ^l；

定义并初始化最优解为最优调度方案xb、第l次迭代所得到的调度方案为

第l次迭代的调度方案服务所述订单集合i中每个订单次数的数组记为s^l，为第l次迭代的调度方案服务订单集合i中第i个订单ii的次数；

定义第l次迭代的路径成本为负的路径集合记为

第l次迭代的路径成本为负的路径集合服务所述订单集合i中每个订单次数的数组记为为第l次迭代服务订单集合i中第i个订单ii的次数；

定义为第l次迭代集合中所有能够服务订单集合i中第k个订单ik的路径集合；

步骤6、构建初始可行解，并将初始可行解中所有单点运输路径加入最优调度方案xb，在第p条单点运输路径pp加入最优调度方xb时，将ub cp赋值给ub；

步骤7、更新路径当前成本：

第l次迭代的第p条路径pp的当前成本记为对令

步骤8、更新第l次迭代的下界curlb^l、最优下界lb及第l次迭代的两次下界相较误差lbgap^l：

步骤8.1、若则将第p条路径pp加入路径集合将赋值给curlb^l；

步骤8.2、计算lbgap^l＝|curlb^l-lb|/lb，当curlb^l＞lb时，令lb＝curlb^l；

步骤9、判断是否满足上界更新条件：

若lbgap^l<lbgapmax，则转入步骤10，否则，转入步骤12；

步骤10、更新第l次迭代的调度方案及第l次迭代的上界curub^l；

步骤11、更新最优调度方案xb：

如果curub^l＜ub，则令ub＝curub^l，令令lcon-fail＝0，否则，xb保持不变，将值赋给

步骤12、利用式(6)所示的次梯度方法得到第l 1次迭代的拉格朗日乘子向量λ^{l 1}：

式(6)中，表示第l次迭代中集合中可服务订单集合i中第i个订单ii的路径数与1的差值，且为第l次迭代的第p条路径pp选取次数值，范围为0-1之间；

步骤13、迭代终止条件：

将l 1赋值给l，若l＞lmax或则停止迭代，输出最优调度方案xb，否则返回步骤7顺序执行。

2.根据权利要求1所述的基于拉格朗日松弛的工业烟草物流调度方法，其特征是，所述步骤10是按如下步骤进行：

步骤10.1、更新第l次迭代的数组

步骤10.1.1、定义变量i＝1；

步骤10.1.2、定义变量j＝1，定义为中第i条路径；

步骤10.1.3、定义为路径所服务的订单集合中第j个订单，定义为订单集合i中的第k个订单ik，将路径加入同时将赋给表示第l次迭代时中可服务订单集合i中第k个订单ik路径和个数；

步骤10.1.4、若j大于路径所服务订单总数，则返回步骤10.1.2，否则将j 1赋值给j，返回步骤10.1.3；

步骤10.1.5、若i大于集合中路径总数，则将i 1赋值给i并转入步骤10.2；

步骤10.2、对于若满足等于1，将集合中唯一路径pp加入第l次迭代的调度方案并令表示第l次迭代时中可服务订单集合i中第i个订单ii的路径集合；

定义第p条单点运输路径pp所服务除订单ii以外所有订单集合为对于令及表示第l次迭代时中可服务订单集合i中第j个订单ij路径和个数，表示第l次迭代时中可服务订单集合i中第j个订单ij路径和个数；

步骤10.3、执行修复操作1：

对于若满足则对集合中所有路径按照评估准则进行评估，选择最优的路径加入后，令及

定义最优路径所服务除订单ii以外所有订单集合为对于令及

所述评估准则为：优先选择所服务订单数最大且值较大的路径；

步骤10.4、若均满足转入步骤11，否则，转入步骤10.4.1执行修复操作2；

步骤10.4.1、定义并初始化未被所服务的订单集合为对于若满足将第i个订单ii加入

步骤10.4.2、枚举出所有多点运输路径，并生成未被所服务的订单枚举出的修补可行路径集合

步骤10.4.3、利用基本贪婪方法从挑选出修复路径集合并加入xcur；

步骤10.5、对于将curub^l cp赋值给curub^l。

3.根据权利要求2所述的基于拉格朗日松弛的工业烟草物流调度方法，其特征是，所述步骤10.4.3中的基本贪婪方法是按如下步骤进行：

步骤10.4.3.1、定义记录可服务中各个订单的路径集合所构成的集合为

步骤10.4.3.2、定义变量i＝0；

步骤10.4.3.3、定义变量j＝0，为中第i条路径；

步骤10.4.3.4、定义ij为路径所服务的订单集合中第j个订单，ij为订单集合i中的第k个订单ik，将路径加入为记录中可服务订单集合i中的第k个订单ik所有路径集合；

步骤10.4.3.5、若j大于路径所服务订单总数，则返回步骤10.4.3.3，否则，将j 1赋值给j，返回步骤10.4.3.4；

步骤10.4.3.6、若i大于集合中路径总数，则转入步骤10.4.3.7，否则，将i 1赋值给i并返回步骤10.4.3.3；

步骤10.4.3.7、找到中多点运输所节约的费用最大的路径加入后，从删除路径并将所有可服务于路径所服务订单的路径从中删除；

步骤10.4.3.8、终止条件判断：

若路径集合pu^l为空集合，则进入步骤10.4.3.9，否则，进入步骤10.4.3.7；

步骤10.4.3.9、对于当满足时，将订单集合i中第i个订单ii对应单点运输路径加入集合

步骤10.4.3.10、令curub^l＝0；将curub^l cp值赋给curub^l。

技术总结
本发明公开了一种基于拉格朗日松弛的工业烟草物流调度方法，包括：1、获取订单数据；2、枚举可行路径集合；3、建立集合分割模型；4、松弛模型；5、初始化参数；6、生成初始可行解并更新上界及最优解；7、更新路径当前成本；8、更新下界；9、判断是否满足更新上界条件，若满足则进入步骤10，否则进入步骤12；10、更新当前可行解；11、更新最优解和拉格朗日乘子；12、判断算法执行的终止条件是否满足，若满足则输出算法的最优解，否则返回步骤7。本发明不仅能快速找到较好的运输调度方案来降低工业烟草物流公司的运费支出以及提升其服务水平，还能降低执行调度方案的第三方物流运输公司的运输成本，达到双赢的局面。

技术研发人员：龙建成;高正鹏;丁建勋;徐小明;石琴
受保护的技术使用者：合肥工业大学
技术研发日：2020.11.30
技术公布日：2021.03.12