同时取送货车辆路径与三维货物平衡装载的耦合优化方法

1.本发明涉及物流路径优化技术领域，具体涉及一种同时取送货车辆路径与三维货物平衡装载的耦合优化方法。


背景技术：

2.作为现代物流体系中的重要组成部分，物流运输服务承担着支撑国民经济和社会发展的重要作用，同时也面临着降本增效、提高运输安全性的巨大压力。
3.车辆路径规划与货物装载布局作为物流配送过程的重要组成部分，是解决运输降本增效提高安全性的有效举措。特别是带三维尺寸货物装载的同时取送货车辆路径问题，其作为一种复杂配送模式的抽象，更具实际应用的代表性。现有技术(“考虑动态平衡装卸的点对点取送货车辆路径优化”，张英贵等，《计算机应用研究》，第1700-1704页，2022年6月)公开了一种考虑动态平衡装卸的点对点取送货车辆路径优化方法，该方法针对点对点取送货车辆路径优化问题，引入动态平衡、后进先出、三维装载等约束，以总路径最短为优化目标，构建多车多客户应用场景下的动态平衡装卸点对点取送货车辆路径优化模型，该现有技术是对中，货物点对点取送，即从一个节点取得货物送往另一节点全部卸载，对于装载布局的要求较低，其并不适用于考虑货物三维尺寸、客户取货和送货需求分开、且对车辆运输过程安全性要求较高的场景。因此，亟需一种同时取送货车辆路径与三维货物平衡装载的耦合优化方法，以保证电器家具、建筑材料及零担货物运输等领域的运输安全。


技术实现要素：

4.本发明的目的在于提供一种同时取送货车辆路径与三维货物平衡装载的耦合优化方法，考虑同时取送货车辆路径和货物平衡装载布局两个层面的约束条件，构建更加符合实际应用的优化模型，将三维平衡装载的可行性判断集成到路径优化过程中，最终实现同时取送货车辆路径与三维货物平衡装载的耦合优化方案的生成，以实现物流配送的降本增效，提高货物运输的安全稳定性。
5.为实现上述目的，本发明提供了一种同时取送货车辆路径与三维货物平衡装载的耦合优化方法，该方法包括以下步骤：
6.s1、以同时取送货车辆里程最短为优化目标构建同时取送货车辆路径与三维货物平衡装载的耦合优化模型；
7.s2、将配送信息输入所述耦合优化模型，运用节约里程法初始化取送货车辆路径，构建初始路径方案；根据配送中心的运输能力和配送中心到各个节点以及各个节点之间的距离来制定使总的车辆运输的公里数最小的配送方案；
8.s3、将客户货物信息输入所述耦合优化模型进行货物装载布局优化；
9.s4、在所述步骤s2得到的初始路径方案的基础上，基于禁忌搜索框架，将货物装载检算算法纳入路径优化过程，输出同时取送货车辆路径与三维货物平衡装载的车辆里程最短的耦合优化方案。
10.进一步的，所述s1进一步包括：
11.s1.1、选择最小化车辆路径作为目标函数；所述最小化车辆路径的计算方法为：
[0012][0013]
其中，n为客户节点集合，r为车辆集合，c
ij
表示(i,j)之间的距离，x
ijr
表示决策变量，其值为1，表示第r辆车从节点i到j，否则其值为0；
[0014]
s1.2、从同时取送货车辆路径以及三维货物平衡装载两个层面对最小化车辆路径进行约束，约束条件包括：
[0015][0016][0017][0018][0019][0020][0021][0022][0023][0024][0025][0026][0027][0028][0029]
[0030][0031][0032][0033][0034][0035][0036][0037][0038][0039][0040]
其中，客户节点i的取货需求量为pi(i＝1,2,...,n)，送货需求量为di(i＝1,2,...,n)；设y
ij
和z
ij
分别表示货车经过路径(i,j)时的取货量和送货量；c0表示空车重量；c表示额定载重；c1表示前轴最大承载重量；c2表示后轴最大承载重量；g表示前后轴距离；β表示允许重心横向偏移量；l、w、h表示货车有效装载空间的长、宽、高；nr表示货车r访问的节点集合；表示客户i的货物集合，mi＝{1，2,...,mi}；b
ik
表示客户i的第k件货物i
ik
的重量；a
ik
表示客户i的第k件货物i
ik
的底面积；z
ik
表示客户i的第k件货物i
ik
的z轴坐标；
△aik
表示客户i的第k件货物i
ik
的重叠面积；a
ik
表示客户i的第k件货物i
ik
的支撑面面积；f
ik
表示客户i的第k件货物i
ik
的易碎性，易碎货物用f
ik
＝0表示，非易碎货物用f
ik
＝1表示；f
ik'
表示客户i的第k'件货物i
ik'
的易碎性；l
ik
、w
ik
、h
ik
表示客户i的第k件货物i
ik
的长、宽、高；y
ik
表示客户i的第k件货物i
ik
的y轴坐标；u
ri
表示节点i被货车r访问的顺序；q
ri
表示货车r在节点i装卸前后货物重量的变化程度；q
ri
表示货车r离开节点i时的实际载货总重量，x
ijr
为决策变量，x
ijr
＝1表示第r辆货车依次访问节点i及其相邻的节点j，否则x
ijr
＝0；s表示车辆最大行驶里程；y
ij
和z
ij
分别表示货车经过路径(i,j)时的取货量和送货量；(x
rik
,y
rik
,z
rik
)表示货物i
ik
在货车r的实际装载位置；(x
rik'
,y
rik'
,z
rik'
)分别表示货物i
ik'
在货车r的实际装载位置。
[0041]
进一步的，所述步骤s2进一步包括：
[0042]
1)、调用一辆货车由配送中心出发，选择第一个客户节点ni进行访问，选取原则为min(d
oi
+d
i0
)，确定所选客户节点的货物可装载性，形成第一条配送路径(n0,ni,n0)；
[0043]
2)、在已有货物运输路径(n
0,
n1,n2,...,nk,n
k+1
,...,n0)基础上插入客户节点nj，选取原则为max(d
kj
+d
j(k+1)-d
k(k+1)
)，对客户节点nj处的货物可装载性进行检验，若满足要求，则将该客户节点nj插入，货物运输路径更新为(n0,n1,n2,...,nk,nj,n
k+1
,...,n0)，若此时不存在可选节点，则重新启用一部货车，直至完成所有节点的分配，输出初始路径方案s0。
[0044]
进一步的，所述s3进一步包括：
[0045]
1)、确定货物装载定位规则；货物的装载定位包括三个部分即装载空间的划分、装载空间更新、装载空间选择和货物摆放位置的选择；
[0046]
2)、确定货物装载定序规则；通过贪心算法的思想，以每个客户的货物的四重指标作为判断依据，设计货物装载定序规则。
[0047]
进一步的，所述步骤1)中具体包括：
[0048]
运用最大空间法对装载空间进行划分：将货物装载后，采用最大长方体来表示剩余空间；在可用装载空间运用占角策略放置货物后，用不与已装载货物相交且最大程度覆盖可用装载空间的长方体表示剩余空间；
[0049]
装载空间更新：运用最大空间法对空间集合f进行更新，先删除被侵占的装载空间，后删除空间集合f中的重复空间；
[0050]
装载空间选择：运用覆盖面积法进行可装载空间选择，覆盖面积是指货物摆放后，与其他货物或者车厢壁之间的接触面积；
[0051]
货物摆放方式选择：运用最小外接长方体法选择货物摆放方式。
[0052]
进一步的，所述步骤2)中的四重指标具体为：第一重指标为每个客户的货物按照重量由大到小排序，第二重指标为每个客户的货物按照体积由大到小排序，第三重指标为每个客户的货物按照底面积由大到小排序，第四重指标为优先装载非易碎性货物即优先装载易碎程度较小的货物。
[0053]
进一步的，所述步骤4进一步包括：
[0054]
1)、设计四种独立并行的邻域算子：路径内节点交换算子、路径内节点重新定位算子、路径间节点交换算子和路径间节点重新定位算子，以此进行邻域方案构造；
[0055]
2)、设置禁忌对象：将所述步骤1)中的四种不同的邻域构造方式作为禁忌对象；
[0056]
3)、在路径寻优时，将目标函数即运输车辆总走行路径的长短作为解的评价准则，对搜索过程中的解进行优劣对比；当搜索到一个邻域可行解后，按照目标函数公式计算其总走行路径的长短来评价该解；
[0057]
4)、设置禁忌表长度：在禁忌搜索过程中，运用评价准则对邻域解进行优劣对比，挑选最佳邻域解，并将其对应的禁忌对象放于禁忌表中；
[0058]
5)、通过总结问题特点和实验计算结果，设置禁忌搜索算法的最大迭代次数，以此作为终止准则；
[0059]
6)、基于上述设置，以禁忌搜索为框架内嵌货物平衡装载算法的耦合优化算法进行搜索寻优。
[0060]
进一步的，所述耦合优化方法还包括位于所述步骤1之前的：
[0061]
s01、提取配送信息：根据配送网络获取待服务客户点的配送信息，包括节点位置、客户距离、货物三维尺寸和重量以及车厢规模和容积载重信息。
[0062]
相比于现有技术，本发明具有以下有益效果：
[0063]
(1)、本发明的同时取送货车辆路径与三维货物平衡装载的耦合优化方法，同时考虑了车辆路径和货物装载布局层面的多重约束条件，构建货物三维平衡装载和同时取送货车辆路径组合优化模型；采用以禁忌搜索为框架内嵌货物平衡装载检验的混合算法对组合优化模型进行求解，运用两阶段货物装载算法对客户节点的货物进行装载，确定货物的装载顺序和车厢内的装载位置；基于节约里程法构造初始路径，在此基础上运用四种独立并行的邻域结构进行禁忌优化搜索，同时调用装载算法检验优化路径的装载可行性，通过不断地搜索迭代优化，最终得到优秀的路径规划和装载布局方案，满足货物配送的不同需求，支撑物流运输企业进行方案优选；取送货车辆路径优化和三维货物平衡装载布局优化是物流配送优化过程的重要环节，二者的偶合编制优化有利于物流配送过程的降本增效，增强货物运输的安全稳定性具有重要意义，提高货运企业竞争力。
[0064]
(2)、本发明的同时取送货车辆路径与三维货物平衡装载的耦合优化方法，针对现实货物配送过程，提出三维货物平衡装载和同时取送货车辆路径组合优化，充分考虑货物的三维尺寸与车厢的载重、容积限制，特别的引入平衡装载，通过货物布局保持重心平衡；该优化方法可广泛应用于考虑货物三维尺寸、客户取货和送货需求分开、且对车辆运输过程安全性要求较高的场景，因此，本发明对三维货物平衡装载和同时取送货车辆路径的耦合进行优化，在保证运输安全的同时，有利于提升物流配送的时效性，控制物流成本，在实际的物流配送过程中具有现实意义。
[0065]
除了上面所描述的目的、特征和优点之外，本发明还有其它的目的、特征和优点。下面将参照图，对本发明作进一步详细的说明。
附图说明
[0066]
附图是用来提供对本发明实施例的进一步理解，并且构成说明书的一部分，与下面的具体实施方式一起用于解释本发明实施例，但并不构成对本发明实施例的限制。在附图中：
[0067]
图1是本发明实施例的带三维货物装载的同时取送货车辆路径配送网络示意图；
[0068]
图2是本发明实施例的平衡装载约束示意图；
[0069]
图3是本发明实施例的同时取送货车辆路径优化算法流程图；
[0070]
图4是本发明运用最大空间法对装载空间进行划分的结构示意图；
[0071]
图5是本发明货物从低面嵌入装载空间的四种重叠方式。
具体实施方式
[0072]
以下结合附图对本发明的实施例进行详细说明，但是本发明可以根据权利要求限定和覆盖的多种不同方式实施。
[0073]
请参见图1至图3，图1的0表示配送中心，1,2,4,5,6,7,8,9分别表示客户节点1-9，车辆1的路径为：0
→1→2→3→4→
0，车辆2的路径为0
→5→6→7→
0，车辆3的路径为0
→8→9→
0，p
11
表示客户节点1的第一件取货需求货物，d
11
表示客户节点1的第一件送货需求货
物，其余以此类推；图2中，(a)是车厢纵向受力分析图；(b)是货物重心横向偏移范围示意图。本实施例提供一种同时取送货车辆路径与三维货物平衡装载的耦合优化方法，该方法包括以下步骤：
[0074]
步骤1、提取配送信息：根据配送网络，获取待服务客户节点的配送信息，包括节点位置、客户距离、货物三维尺寸、重量以及车厢规模、容积载重等信息。
[0075]
步骤2、以同时取送货车辆里程最短为优化目标构建同时取送货车辆路径与三维货物平衡装载的耦合优化模型；
[0076]
构建耦合优化模型的假设条件包括：假设配送网络仅有一个配送中心；运输车辆为相同规格的厢式货车；运输车辆是由后门装卸货物的尾部装卸式货车；每辆运输车仅服务一条路径的客户节点；每个客户仅被运输车辆访问一次；已知每个客户的位置信息；已知每个客户节点待服务的货物信息；空载货车能满足单个客户需求；车厢长、宽、高分别平行于坐标系的轴；货物具备均质、长方体外形特征；货物重心位于几何中心；货物在运输途中不可移动。步骤2进一步包括：
[0077]
步骤2.1)、选择最小化车辆路径作为目标函数；最小化车辆路径的计算方法为：
[0078][0079]
其中，n为客户节点集合，r为车辆集合，c
ij
表示(i,j)之间的距离，x
ijr
表示决策变量，其值为1，表示第r辆车从节点i到j，否则其值为0；
[0080]
步骤2.2)、从同时取送货车辆路径以及三维货物平衡装载两个层面对最小化车辆路径进行约束；取送货车辆路径层面的约束条件包括：
[0081][0082][0083][0084][0085][0086][0087][0088][0089]
其中，式(2)和(3)表示每个客户节点只能被访问一次，式(4)表示每条路径上的客户节点只能由同一辆车访问，式(5)～(7)表示货车路径的起止点均为配送中心，式(8)表示货车运行里程限制，式(9)表示避免货车走行子回路约束。
[0090]
三维货物平衡装载层面的约束条件包括：
[0091][0092][0093][0094][0095][0096][0097][0098][0099][0100][0101][0102][0103][0104][0105][0106]
[0107][0108]
式(10)表示车辆的载重限制，式(11)和式(12)表示取货和送货的流量守恒约束，式(13)表示每个客户的取货量和送货量非负，式(14)和式(15)分别表示每辆货车额定载重和有效装载体积限制，式(16)和式(17)表示货物装载位置限制，式(18)表示装载空间限制，式(19)和式(20)表示后进先出的约束，式(21)和式(22)表示支撑面约束，式(23)表示脆弱性约束，式(24)和式(25)表示货车纵向轴重约束，式(26)表示货物横向重心偏移约束。
[0109]
上述式(2)～式(26)中，客户节点i的取货需求量为pi(i＝1,2,...,n)，送货需求量为di(i＝1,2,...,n)；设y
ij
和z
ij
分别表示货车经过路径(i,j)时的取货量和送货量；c0表示空车重量；c表示额定载重；c1表示前轴最大承载重量；c2表示后轴最大承载重量；g表示前后轴距离；β表示允许重心横向偏移量；l、w、h表示货车有效装载空间的长、宽、高；nr表示货车r访问的节点集合；表示客户i的货物集合，mi＝{1，2,...,mi}；b
ik
表示客户i的第k件货物i
ik
的重量；a
ik
表示客户i的第k件货物i
ik
的底面积；z
ik
表示客户i的第k件货物i
ik
的z轴坐标；
△aik
表示客户i的第k件货物i
ik
的重叠面积；a
ik
表示客户i的第k件货物i
ik
的支撑面面积；f
ik
表示客户i的第k件货物i
ik
的易碎性，易碎货物用f
ik
＝0表示，非易碎货物用f
ik
＝1表示；f
ik'
表示客户i的第k'件货物i
ik'
的易碎性；l
ik
、w
ik
、h
ik
表示客户i的第k件货物i
ik
的长、宽、高；y
ik
表示客户i的第k件货物i
ik
的y轴坐标；u
ri
表示节点i被货车r访问的顺序；q
ri
表示货车r在节点i装卸前后货物重量的变化程度；q
ri
表示货车r离开节点i时的实际载货总重量，x
ijr
为决策变量，x
ijr
＝1表示第r辆货车依次访问节点i及其相邻的节点j，否则x
ijr
＝0；s表示车辆最大行驶里程；y
ij
和z
ij
分别表示货车经过路径(i,j)时的取货量和送货量；(x
rik
,y
rik
,z
rik
)表示货物i
ik
在货车r的实际装载位置；(x
rik'
,y
rik'
,z
rik'
)分别表示货物i
ik'
在货车r的实际装载位置。
[0110]
步骤3、将配送信息输入耦合优化模型，运用节约里程法初始化取送货车辆路径，构建初始路径方案；步骤3进一步包括：
[0111]
步骤3.1)、调用一辆货车由配送中心出发，选择第一个客户节点ni进行访问，选取原则为min(d
oi
+d
i0
)，确定所选客户节点的货物可装载性，形成第一条配送路径(n0,ni,n0)；
[0112]
步骤3.2)、在已有货物运输路径(n0,n1,n2,...,nk,n
k+1
,...,n0)基础上插入客户节点nj，选取原则为max(d
kj
+d
j(k+1)-d
k(k+1)
)，对客户节点nj处的货物可装载性进行检验，若满足要求，则将该客户节点nj插入，货物运输路径更新为(n0,n1,n2,...,nk,nj,n
k+1
,...,n0)，若此时不存在可选节点，则重新启用一部货车，直至完成所有节点的分配，输出初始路径方案s0。
[0113]
步骤4、将客户货物信息输入耦合优化模型进行货物装载布局优化；步骤4进一步包括：
[0114]
步骤4.1)、确定货物装载定位规则：货物的装载定位包括三个部分即装载空间的划分、装载空间更新、装载空间选择和货物摆放位置的选择。具体地：
[0115]
①
运用最大空间法对装载空间进行划分：将货物装载后，采用最大长方体来表示剩余空间。在可用装载空间运用占角策略放置货物后，用不与已装载货物相交且最大程度覆盖可用装载空间的长方体表示剩余空间，参见图4所示；其中，图4(a)～(c)分别表示利用
最大空间划分方法，用极大长方体表示剩余空间的三种表示方式。
[0116]
②
装载空间更新：用空间集合f来表示装载空间集合，即剩余空间；未进行装载时，集合f中只有车厢空间。在装载一个货物后，会产生三个新的装载空间，货物有可能与剩余空间中的原有装载空间重叠，这是因为最大空间法产生的装载空间存在交集空间，货物在装入其中一个空间时，同样有可能装入交集空间，这时必然会占据另一装载空间，另一装载空间也要随之更新。更新方式是，最大空间法对空间集合f进行更新，删除另一被侵占空间，最后删除集合f中的重复空间。货物与空间有多种重叠方式，图5中展示了货物从低面嵌入空间的情形，此外还有左右、上下贯穿空间等；其中，图5(a)表示货物装入装载空间f示意图；图5(b)～(d)表示利用最大空间法，产生新的空间f1、f2、f3的示意图。
[0117]
货物从空间f的底面嵌入空间f，根据调整后的最大空间法，产生新的空间f1、f2、f3，如图所示。接下来删去原空间f，并将空间f1、f2、f3添加进集合f，新生成的空间加入集合后，空间集合f按照空间坐标x最小、z最小、y最小依次排序，遍历空间集合f，如果存在某空间的长宽高小于未装载货物的最小长度尺寸，则该空间视为不可装载空间。
[0118]
③
基于覆盖面积法进行可装载空间选择：在可装载空间的选择上，运用覆盖面积方法。覆盖面积是指货物摆放后，与其他货物或者车厢壁之间的接触面积，用适应度函数sc(h,s)表示，适应度是指货物与空间的匹配，h表示待装货物，s表示可用空间。
[0119]
具体地，货物h进行装载时，对空间集合s进行遍历得到不同的sc(h,s)值，组成的数组x。数组x中最大的值对应的组合即为最合适的可装载空间。
[0120]
在计算适应度函数sc(h,s)时，需要考虑以下几个方面：
[0121]
(a)、后接触面积值(back contact area vae,bcav)：表示货物装载后与其后部产生表面接触的货物或车厢壁的接触面积。
[0122]
(b)、底部支撑面积值(support contact area vaue,scav)：表示货物装载后与其底部产生表面接触的货物或车厢壁的接触面积。
[0123]
(c)、左接触面积值(left contact area value,lcav)：表示货物装载后与其左方产生表面接触的货物或车厢壁的接触面积。
[0124]
(d)、右接触面积值(right contact area value,rcav)：表示货物装载后与其右方产生表面接触的货物或车厢壁的接触面积。
[0125]
则适应度函数sc(h,s)＝bcav+scav+lcav+rcav。
[0126]
④
货物摆放方式的选择
[0127]
在计算适应度时，每个待装载货物与可装载空间即为一个组合。由于货物可在水平平面进行90
°
旋转，也就是说货物在装载时，有两种摆放的方式，有可能存在两种组合值。一种为正常装载的组合，另一种为旋转后的组合。不同的组合的选择将会对后续的货物布局产生影响。针对上述的两种可装载空间的选择算法，货物摆放方式的选择也有所不同。
[0128]
运用最小外接长方体法选择摆放方式。最小外接长方体是给定的三维物体在空间中占据的最大体积，即以给定三维物体各个顶点在三个轴上的最大值与最小值定下边界的长方体。
[0129]
对两种摆放方式分别进行顺序装载算法尝试，形成两种不同的组合。假设货物按照这两种组合装载，分别算出装载后与车厢中其他货物形成的最小外接长方体体积。两个体积中较小者对应的组合则为最优组合。
[0130]
在本发明一种具体的实施方式中：步骤4.1)货物装载定位的具体步骤为：
[0131]
a)、输入货物信息，车厢的体积v＝l
×w×
h；初始空间集合f，初始令车辆r服务的客户i＝1，客户i的货物集为ii＝1；
[0132]
b)、使用最大面积覆盖法，若适应度函数sc(h,s)≠-∞，按较大的适应度值对应的货物方向放入相应装载空间最后右下角，更新空间集合f，若sc(h,s)＝-∞，卸载已装客户i的货物，跳转至步骤e)；
[0133]
c)、对集合f进行排序，ii＝ii+1；重复步骤b)，直至ii＝mi+1；
[0134]
d)、对客户i的货物进行平衡性检测，若检测通过，继续进行下一步骤，否则输出已装体积；
[0135]
e)、i＝i+1，重复步骤b)-d)，直至i＝nr+1；输出已装载货物的总体积。
[0136]
步骤4.2)、确定货物装载定序规则：通过贪心算法的思想，改变客户内部货物的顺序，形成不同的装载顺序。采用四重指标：第一重指标为每个客户的货物按照重量由大到小排序，第二重指标为每个客户的货物按照体积由大到小排序，第三重指标为每个客户的货物按照底面积由大到小排序，第四重指标为优先装载非易碎性货物即优先装载易碎程度较小的货物。
[0137]
在本发明一种具体的实施方式中：步骤4.2)确定货物装载定序规则的具体步骤为：
[0138]
a)、输入货物原始的装载序列i，nolmproved＝0，i＝1，totalvolume是货物总体积，max_iter是最大迭代次数；
[0139]
b)、调用装载定位算法，得装载的货物体积packvolume；若packvolume＝totalvolume，输出装载成功，否则下一步；
[0140]
c)、按照随机四种定序策略(即四重指标)中的一种排序方式对货物进行排列，形成新的序列i'；调用装载定位算法，新的装载体积packvolume'；
[0141]
d)、若packedvolume'》packedvolume,packedvolume＝packedvolume'，序列i由i'代替；若packedvolume＝totalvolume，输出装载成功，否则跳转到步骤e)；
[0142]
e)、改变客户货物的内部顺序产生新序列1'；再次调用装载定位算法，得装载体积packedvolume'；
[0143]
f)、若packedvolume'》packedvolume,packedvolume＝packedvolume'，i由i'代替，重置nolmproved＝0；若packedvolume＝totalvolume，输出装载成功，否则noimproved＝noimproved+1；
[0144]
g)、返回步骤e)，直到noimproved＝max_iter；
[0145]
h)、i＝i+1，重复步骤b)-g)，直到i＝5；若没有输出装载成功，则输出装载失败。
[0146]
步骤5、在步骤3得到的初始路径方案的基础上，基于禁忌搜索框架，并将货物装载检算算法纳入路径优化过程，最终输出同时取送货车辆路径与三维货物平衡装载的车辆里程最短的耦合优化方案。具体包括：
[0147]
步骤5.1)、设计四种独立并行的邻域算子：路径内节点交换算子、路径内节点重新定位算子、路径间节点交换算子和路径间节点重新定位算子，以此进行邻域方案构造；其中：
[0148]
①
、路径内节点交换算子：选择一条运输路径route1，随机选择该条路径中的顾客
节点i和j，交换节点i和j的位置。
[0149]
②
、路径内节点重新定位算子：选择一条运输路径route1，确定该路径中m个连续的客户节点。若m＝1，则随机选择客户节点重新定位，当m＝2，则将两个连续节点重新定位。
[0150]
③
、路径间节点交换算子：选择两条运输路径route1和route2，在两条路径中各选择一个客户节点，将其插入另一条路径。
[0151]
④
、路径间节点重新定位算子：选择两条运输路径route1和route2，从路径route1中选择节点i转移到路径route2的j和j+1之间。
[0152]
步骤5.2)、针对四种不同的邻域构造方式来设置禁忌对象，禁忌对象设置如下：
[0153]
①
、在运用路径内节点交换算子进行邻域构造时，将客户节点i和客户节点j进行交换的操作设置为禁忌对象。
[0154]
②
在运用路径内节点重新定位算子进行邻域构造时，将客户节点j和j+1重新定位至客户节点i和i+1之间的操作设置为禁忌对象。
[0155]
③
、在运用路径间节点交换算子进行邻域构造时，将路径route1中的客户节点i与路径route2中的客户节点j进行节点交换的操作设置为禁忌对象。
[0156]
④
、在运用路径间节点重新定位算子进行邻域构造时，将route1中的客户节点i重新定位到route2中的客户节点j和j+1之间的操作设置为禁忌对象。
[0157]
步骤5.3)、在路径寻优时，将目标函数即运输车辆总走行路径的长短作为解的评价准则，对搜索过程中的解进行优劣对比；当搜索到一个邻域可行解后，按照目标函数公式计算其总走行路径的长短来评价该解。评价准则为：
[0158]
步骤5.4)、通过总结问题特点和实验计算结果，设置初始禁忌长度len＝50。
[0159]
步骤5.5)、设置禁忌搜索算法的最大迭代次数，以此作为终止准则；最大迭代次数t
max
＝800，两个参数是通过多轮对比实验综合分析决定结果。
[0160]
步骤5.6)、基于上述设置，以禁忌搜索为框架内嵌货物平衡装载算法的耦合优化算法进行搜索寻优；具体包括以下步骤：
[0161]
(a)、基于初始方案，运用独立并行的邻域算子，生成路径邻域方案集sn；
[0162]
(b)、运用三维货物装载算法对邻域方案中路径节点的服务需求进行装载定位定序操作，从而完成货物装载，得到车厢内部货物装载布局，形成同时取送货车辆路径和三维货物装载耦合优化邻域方案，即完成了路径方案的货物装载检验。若未能完成装载检验，则重新进行邻域变换。
[0163]
(c)、对通过检验而形成的同时取送货车辆路径和三维货物装载耦合优化邻域方案，运用评价准则即最小化车辆运输路径对邻域解进行优劣对比，挑选最佳邻域解，并将其对应的禁忌对象放于禁忌表中，更新禁忌表、最优解、迭代次数递增。
[0164]
(d)、判断是否满足迭代次数终止规则，若t》t
max
，则算法终止，输出当前最优组合方案。
[0165]
以上所述仅为本发明的优选实施例而已，并不用于限制本发明，对于本领域的技术人员来说，本发明可以有各种更改和变化。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

技术特征：
1.一种同时取送货车辆路径与三维货物平衡装载的耦合优化方法，其特征在于，该方法包括以下步骤：s1、以同时取送货车辆里程最短为优化目标构建同时取送货车辆路径与三维货物平衡装载的耦合优化模型；s2、将配送信息输入所述耦合优化模型，运用节约里程法初始化取送货车辆路径，构建初始路径方案；s3、将客户货物信息输入所述耦合优化模型进行货物装载布局优化；s4、在所述步骤s2得到的初始路径方案的基础上，基于禁忌搜索框架，将货物装载检算算法纳入路径优化过程，输出同时取送货车辆路径与三维货物平衡装载的车辆里程最短的最优组合方案。2.根据权利要求1所述的耦合优化方法，其特征在于，所述s1进一步包括：s1.1、选择最小化车辆路径作为目标函数；所述最小化车辆路径的计算方法为：其中，n为客户节点集合，r为车辆集合，c
ij
表示(i,j)之间的距离，x
ijr
表示决策变量，其值为1，表示第r辆车从节点i到j，否则其值为0；s1.2、从同时取送货车辆路径以及三维货物平衡装载两个层面对最小化车辆路径进行约束，约束条件包括：约束，约束条件包括：约束，约束条件包括：约束，约束条件包括：约束，约束条件包括：约束，约束条件包括：约束，约束条件包括：约束，约束条件包括：约束，约束条件包括：约束，约束条件包括：约束，约束条件包括：
其中，客户节点i的取货需求量为p
i
(i＝1,2,...,n)，送货需求量为d
i
(i＝1,2,...,n)；设y
ij
和z
ij
分别表示货车经过路径(i,j)时的取货量和送货量；c0表示空车重量；c表示额定载重；c1表示前轴最大承载重量；c2表示后轴最大承载重量；g表示前后轴距离；β表示允许重心横向偏移量；l、w、h表示货车有效装载空间的长、宽、高；n
r
表示货车r访问的节点集合；表示客户i的货物集合，m
i
＝{1，2,...,m
i
}；b
ik
表示客户i的第k件货物i
ik
的重量；a
ik
表示客户i的第k件货物i
ik
的底面积；z
ik
表示客户i的第k件货物i
ik
的z轴坐标；
△
a
ik
表示客户i的第k件货物i
ik
的重叠面积；a
ik
表示客户i的第k件货物i
ik
的支撑面面积；f
ik
表示客户i的第k件货物i
ik
的易碎性，易碎货物用f
ik
＝0表示，非易碎货物用f
ik
＝1表示；f
ik'
表示客户i的第k'件货物i
ik'
的易碎性；l
ik
、w
ik
、h
ik
表示客户i的第k件货物i
ik
的长、宽、高；y
ik
表示客户i的第k件货物i
ik
的y轴坐标；u
ri
表示节点i被货车r访问的顺序；q
ri
表示货车r在节点i装卸前后货物重量的变化程度；q
ri
表示货车r离开节点i时的实际载货总重量，x
ijr
为决策变量，x
ijr
＝1表示第r辆货车依次访问节点i及其相邻的节点j，否则x
ijr
＝0；s表示车辆最大行驶里程；y
ij
和z
ij
分别表示货车经过路径(i,j)时的取货量和送货量；(x
rik
,y
rik
,z
rik
)表示货物i
ik
在货车r的实际装载位置；(x
rik'
,y
rik'
,z
rik'
)分别表示货物i
ik'
在货车r的实际装载位置。3.根据权利要求1所述的耦合优化方法，其特征在于，所述步骤s2进一步包括：s2.1、调用一辆货车由配送中心出发，选择第一个客户节点n
i
进行访问，选取原则为min(d
oi
+d
i0
)，确定所选客户节点的货物可装载性，形成第一条配送路径(n0,n
i
,n0)；s2.2、在已有货物运输路径(n0,n1,n2,...,n
k
,n
k+1
,...,n0)基础上插入客户节点n
j
，选取原则为max(d
kj
+d
j(k+1)-d
k(k+1)
)，对客户节点n
j
处的货物可装载性进行检验，若满足要求，则将该客户节点n
j
插入，货物运输路径更新为(n0,n1,n2,...,n
k
,n
j
,n
k+1
,...,n0)，若此时不存在可选节点，则重新启用一部货车，直至完成所有节点的分配，输出初始路径方案s0。4.根据权利要求1所述的耦合优化方法，其特征在于，所述步骤s3进一步包括：s3.1、确定货物装载定位规则；货物的装载定位包括装载空间的划分、装载空间更新以及装载空间选择与货物摆放方式选择三个部分；s3.2、确定货物装载定序规则；通过贪心算法的思想，以每个客户的货物的四重指标作为判断依据，设计货物装载定序规则。5.根据权利要求4所述的耦合优化方法，其特征在于，所述步骤s3.1中具体包括：运用最大空间法对装载空间进行划分：将货物装载后，采用最大长方体来表示剩余空间；在可用装载空间运用占角策略放置货物后，用不与已装载货物相交且最大程度覆盖可用装载空间的长方体表示剩余空间；装载空间更新：运用最大空间法对空间集合f进行更新，先删除被侵占的装载空间，后删除空间集合f中的重复空间；装载空间选择：运用覆盖面积法进行可装载空间选择，覆盖面积是指货物摆放后，与其他货物或者车厢壁之间的接触面积；货物摆放方式选择：运用最小外接长方体法选择货物摆放方式。6.根据权利要求4所述的耦合优化方法，其特征在于，所述步骤s3.2中的四重指标具体为：第一重指标为每个客户的货物按照重量由大到小排序，第二重指标为每个客户的货物按照体积由大到小排序，第三重指标为每个客户的货物按照底面积由大到小排序，第四重指标为优先装载非易碎性货物即优先装载易碎程度较小的货物。7.根据权利要求1所述的耦合优化方法，其特征在于，所述步骤s4进一步包括：s4.1、设计四种独立并行的邻域算子：路径内节点交换算子、路径内节点重新定位算子、路径间节点交换算子和路径间节点重新定位算子，以此进行邻域方案构造；s4.2、设置禁忌对象：将所述步骤s4.1中的四种不同的邻域构造方式作为禁忌对象；
s4.3、在路径寻优时，将目标函数即运输车辆总走行路径的长短作为解的评价准则，对搜索过程中的解进行优劣对比；当搜索到一个邻域可行解后，按照目标函数公式计算其总走行路径的长短来评价该解；s4.4、设置禁忌表长度：在禁忌搜索过程中，运用评价准则对邻域解进行优劣对比，挑选最佳邻域解，并将其对应的禁忌对象放于禁忌表中；s4.5、通过总结问题特点和实验计算结果，设置禁忌搜索算法的最大迭代次数，以此作为终止准则；s4.6、基于上述设置，以禁忌搜索为框架内嵌货物平衡装载算法的耦合优化算法进行搜索寻优。8.根据权利要求1-7中任一项所述的耦合优化方法，其特征在于，所述耦合优化方法还包括位于所述步骤s1之前的：s01、提取配送信息：根据配送网络获取待服务客户点的配送信息，包括节点位置、客户距离、货物三维尺寸和重量以及车厢规模和容积载重信息。

技术总结
本发明涉及物流配送优化领域，尤其涉及一种同时取送货车辆路径与三维货物平衡装载的耦合优化方法，以同时取送货车辆里程最短为优化目标构建货物三维平衡装载和同时取送货车辆路径组合优化模型，根据模型特点，设计混合启发式算法进行耦合优化，外层采用禁忌搜索框架完成同时取送货车辆路径优化，内嵌三维货物平衡装载算法，算法完成客户节点货物装载布局的同时对路径优化方案进行装载检验，将三维平衡装载的可行性判断集成到路径优化过程中，最终实现同时取送货车辆路径与三维货物平衡装载的耦合优化方案的生成。本发明的耦合优化方法，在保证运输安全的同时，有利于提升物流配送的时效性，控制物流成本，在实际的物流配送过程中具有现实意义。过程中具有现实意义。过程中具有现实意义。


技术研发人员：盛丽宁 张英贵
受保护的技术使用者：中南大学
技术研发日：2023.04.07
技术公布日：2023/8/21