一种基于混合整数规划的多目标散件组托优化方法与流程
本发明属于智能物流与仓储,具体涉及一种基于混合整数规划的多目标散件组托优化方法,特别是一种通过建立混合整数规划模型并结合分支定界算法求解最优装载方案的自动化规划技术。
背景技术:
1、在现代物流体系中,散件物资的托盘装载规划是影响仓储与运输效率的核心环节之一。传统散件组托作业主要依赖人工经验进行,操作人员根据个人经验判断物资的摆放位置与堆叠方式。这种方式存在明显不足:首先,人工规划效率低下,难以满足现代物流大批量、高节拍的作业需求;其次,空间利用率往往无法达到最优,造成运输资源浪费;再者,稳定性评估缺乏科学依据,运输过程中易发生物资倾覆;此外,人工规划难以系统化处理尺寸、重量、稳定性等多重约束条件。
2、为改进传统方法的不足,现有研究提出了多种优化方法,包括启发式算法、遗传算法、模拟退火算法等。这些方法在一定程度上提升了装载规划的效果,但仍存在各自的局限性:启发式算法容易陷入局部最优,难以保证全局最优性;遗传算法参数调节复杂,收敛性能不稳定;模拟退火算法计算效率较低,难以满足实时应用需求。
3、混合整数规划作为一种成熟的数学优化方法,在处理组合优化问题方面具有独特优势。该方法能够同时处理离散和连续变量,并通过分支定界算法保证找到全局最优解或在指定时间内获得最优性保证的近似解。与传统的启发式方法相比,混合整数规划结合分支定界法的核心优势在于其数学上保证全局最优解的能力,能够完备处理复杂约束条件,且具有技术成熟度高、工程应用案例丰富等特点。
4、然而,将混合整数规划应用于散件组托规划仍面临诸多挑战:如何建立既能准确描述物理约束又便于求解的数学模型;如何有效处理多目标之间的权衡关系;如何设计高效的求解算法以应对实际工程问题的规模要求等。
5、因此,物流行业迫切需要一种能够保证全局最优性、高效处理多重约束条件且具有良好实用性的自动化散件组托规划方法。本发明正是在这一背景下提出的,通过建立系统的混合整数规划模型,结合改进的分支定界算法,为散件组托规划提供了一种科学、高效、可靠的解决方案。
技术实现思路
1、本发明的目的是提出一种基于混合整数规划的多目标散件组托优化方法,以得到当前散件的最优组托方案,从而有效优化散件在托盘上的空间布局,最大化装载数量,同时保证装载方案的稳定性和可行性。
2、为了解决上述技术问题,本发明采用以下技术方案:
3、一种基于混合整数规划的多目标散件组托优化方法,包括:
4、对托盘和散件进行三维数字化建模;以托盘底面中心为三维坐标系原点,以散件的几何中心表示散件在三维坐标系中的位置,对各散件的摆放朝向和位置进行系统化描述;
5、以装载数量最大化原则构建目标函数,用于计算装载数量指标;
6、以空间利用率原则建立目标函数,用于计算空间利用率指标;
7、以装载稳定性原则建立目标函数,用于计算稳定性指标;
8、以重量约束原则建立目标函数,用于计算重量利用率指标;
9、基于所述装载数量指标、空间利用率指标、稳定性指标以及重量利用率指标,构建多目标散件组托优化函数,并将多目标散件组托优化函数转化为单目标优化问题;
10、利用混合整数规划结合改进的分支定界算法求解所述单目标优化问题,得到最优的散件装载方案。
11、进一步地,设定托盘的三维尺寸为长度、宽度、高度,最大成托高度,最小成托高度,托盘重量为,最大成托重量;散件的三维尺寸为长度、宽度、高度,重量为;散件有个不同的摆放朝向,每个朝向对应不同的尺寸组合;
12、以托盘底面中心为坐标系原点,建立右手坐标系,其中:
13、●轴沿托盘长度方向,范围;
14、●轴沿托盘宽度方向,范围;
15、●轴沿托盘高度方向,范围。
16、第个散件的几何中心在托盘坐标系中的三维坐标为,所有散件在组托之前首先会被分配一个初始摆放位置和朝向。
17、3.进一步地,所述以托盘装载数量指标最大化原则构建目标函数,用于计算装载数量指标,包括:
18、、、方向上的最大可能装卸数量计算如下:
19、
20、式中:、、分别表示在、、方向上的散件最大可能摆放数量。
21、装载数量指标()最大化建模如下
22、
23、
24、式中:、、分别表示在、、方向上的散件摆放数量;表示正整数;、、表示特定朝向下的散件有效尺寸,由下式决定:
25、
26、式中:、、分别表示对应二进制决策变量朝向下散件的长、宽、高;表示朝向选择:
27、
28、
29、式中:表示所有可能的朝向选择数。
30、4.进一步地,所述以托盘空间利用率原则建立目标函数,用于计算空间利用率指标,包括:
31、体积利用率()建模如下:
32、
33、平面利用率()建模如下:
34、
35、高度利用率()建模如下:
36、
37、综合空间利用率指标()最大化建模如下:
38、
39、
40、式中:、、分别为体积利用率、平面利用率和高度利用率的权重系数。
41、进一步地,所述以装载稳定性原则建立目标函数,用于计算稳定性指标,包括:
42、1、整体装载体重心位置计算:
43、假设散件在托盘上紧密、均匀排列,形成一个规则的长方体载体。其重心坐标(,,)为:
44、
45、2、重心在各个方向上的偏移量计算:
46、将重心坐标归一化至托盘尺寸范围,并计算其偏离几何中心(0.5)的绝对值:
47、
48、3、各方向稳定性安全系数计算
49、利用预设的稳定性容差参数,计算各个方向安全系数,即容差与实际偏移量的比值:
50、
51、指标()最大化建模如下:
52、
53、
54、进一步地,所述以重量约束原则建立目标函数,用于计算重量利用率指标,包括:
55、重量利用率指标()最大化建模如下:
56、
57、
58、进一步地,所述基于装载数量指标、空间利用率指标、稳定性指标以及重量利用率指标,构建多目标散件组托优化函数,并将多目标散件组托优化函数转化为单目标优化问题,包括:
59、多目标散件组托优化函数表示如下:
60、
61、
62、转换成单目标优化问题:
63、
64、
65、式中:、、、表示多目标优化权重参数,根据实际应用场景调整各权重值以体现不同目标的相对重要性。
66、进一步地,所述利用改进的分支定界算法求解所述单目标优化问题,得到最优的散件组托方案,包括:
67、1、算法参数初始化;
68、设置分支定界算法参数:最大迭代次数、最优性容忍度、最大计算时间;初始化当前最优值,当前最优解,活跃节点集合,其中为原始混合整数规划问题;
69、2、预处理与问题简化;
70、对混合整数规划模型进行预处理,包括变量边界紧缩、冗余约束识别和对称性破缺;通过约束传播技术收紧决策变量的上下界:
71、
72、
73、式中:和分别为决策变量的下界和上界;和分别表示基于约束推导的下界和上界;
74、3、节点选择与线性松弛求解;
75、从活跃节点集合中选择上界最大的节点:
76、
77、式中:表示线性松弛解的目标函数;节点的线性松弛问题求解如下:
78、
79、4、定界与剪枝操作;
80、如果线性松弛问题无可行解,则剪枝当前节点;如果松弛解值满足,则剪枝当前节点;如果松弛解满足所有整数约束,则更新当前最优解,,并剪枝所有上界不超过的节点。
81、5、分支变量选择;
82、选择分支变量,采用基于伪代价的分支策略:
83、
84、式中,为分支候选变量索引集合,包含当前分数解的整数变量索引;伪代价的计算为:
85、
86、式中,表示中索引为的分支变量,表示分支变量在当前节点线性松弛解中的值;和分别表示分支变量向下和向上分支的伪代价;和分别表示向上、向下取整运算符;
87、6、子节点生成;
88、对选定的分支变量,创建两个子节点:
89、● 左子节点:添加约束;
90、● 右子节点:添加约束;
91、将新生成的子节点加入活跃节点集合;
92、7、割平面生成与添加;
93、为加速算法收敛,采用割平面法加强当前节点的线性规划松弛问题,该割平面会“割去”当前的分数最优解,但不会“割去”任何可行的整数解,从而迫使后续求解趋向整数解。
94、7.1生成gomory割平面:
95、生成gomory割平面以收紧线性松弛:
96、
97、式中,表示约束矩阵的第行第列系数;表示约束右端项;表示非基变量索引集合;
98、7.2,生成覆盖不等式:
99、对于覆盖集,满足,则生成覆盖不等式:
100、
101、式中:表示变量索引子集,表示集合的元素个数;和分别为对应约束的系数和右端常数。
102、8、可行性启发式搜索;
103、采用可行性泵启发式寻找整数可行解:
104、8.1,求解线性松弛得到分数解;
105、8.2,四舍五入得到整数解;
106、8.3,当不可行时,寻找最接近的可行整数解,更新为的线性投影,重新四舍五入得到新的;
107、9、收敛性检查与终止判断;
108、计算当前最优性间隙:
109、
110、当满足或达到最大迭代次数或计算时间超过时,算法终止,输出当前最优解作为散件组托规划方案;
111、10、结果验证与方案输出
112、对求得的最优解进行物理可行性验证,包括尺寸约束、重量约束的满足情况。
113、● 检查尺寸约束:,,。
114、● 检查重量约束:
115、求解算法采用改进的分支定界算法。分支策略设计基于敏感度的变量选择策略,优先分支对目标函数影响最大的变量。节点处理采用最佳优先搜索策略,为每个节点计算上界值,优先处理上界值最大的节点。剪枝规则设计基于线性松弛的剪枝规则,当节点的线性松弛解小于当前最优整数解时,对该节点进行剪枝。同时引入多种预处理技术加速求解过程,包括变量界紧缩、冗余约束识别和对称性破缺。
116、与现有技术相比,本发明具有以下有益效果:
117、本发明方法在托盘三维空间建模的基础上,综合考虑物资装载数量最大化原则、托盘空间利用率原则、装载稳定性原则、重量约束原则多个目标数学模型,并借助混合整数规划与分支定界算法对建立的数学模型进行求解,保证找到全局最优解或在指定时间内找到最优性保证的近似解,以得到当前散件的最优组托方案,能够有效优化散件在托盘上的空间布局,从而极大提升托盘装载的空间利用率和稳定性,降低物流运输成本。
版权声明:本站专利文献数据主要来源于国家知识产权局等公开渠道,由 技术新讯 进行整理汇编。页面设计及数据汇编的著作权归本站所有。全部内容仅供个人学习、科研评估与技术交流参考,严禁用于任何商业用途(包括但不限于直接生产制造、技术转让、倒卖数据等)。
免责条款:专利技术具有时效性,本站不对资料的绝对准确性、完整性和可实施性提供任何明示或暗示的担保。因参考本站内容造成的直接或间接损失,本站不承担相关法律责任。若您认为本站内容有侵权问题,请及时提供权属证明与我们联系,本站将在核实后依法处理。反馈意见:yyfuon@163.com