分支定价方法求解带二维装箱约束的车辆路径问题

面向家具、电器等货物的物流配送场景,研究带二维装箱约束的车辆路径问题(2L–CVRP),构建了2L–CVRP的混合整数线性规划模型.为求解大规模2L–CVRP,构建了该问题集合划分模型,提出基于分支定价的方法.针对分支节点的松弛模型,基于列生成策略将其分解为线性规划主问题、带资源和二维装箱约束的最短路径子问题,并提出基于ng-route松弛策略的标签算法和基于禁忌搜索的装箱算法有效求解复杂子问题.仿真结果表明,提出的方法可高效求解大规模2L–CVRP,其中ng-route松弛策略能有效提升算法求解效率,研究成果为装箱约束下大规模车辆路径问题的高效求解提供了有效途径.

基于混合蚂蚁算法的二维装箱问题求解

二维装箱问题是一个NP -Hard组合优化问题。根据蚂蚁优化算法和二维装箱问题的特点 ,本文提出了改进的BL算法与蚂蚁算法相结合的混合算法来解决二维装箱问题 ,实验结果表明 ,该算法是行之有效的 ,并具有一定的通用性。

二维装箱问题非线性规划模型和算法

二维装箱问题是具有广泛应用背景的一类组合优化问题,这类问题是NP难问题,很难得到精确解.将二维装箱问题表示为一个非线性规划模型,用变分分析中切锥的概念建立了这一优化问题的一阶最优性条件.给出了求解这一优化问题的增广Lagrange方法,并求解了具体问题.数值实验表明增广Lagrange方法适合求解该问题,对于不超过10个物品的装箱问题可以求得精确解.

带二维装箱约束的客货滚装船配载决策

客货滚装船长期处于人工配载状态,其独特性导致其无法直接采用已有滚装船配载方法.为提高客货滚装港口配载的决策水平,针对配载过程的两阶段和二维装箱特性,以船舱面积利用率最大为目标,构建客货滚装船配载决策模型.为实现大规模求解,设计偏随机密钥混合遗传算法求解,算法由多阶段启发式嵌入偏随机密钥遗传算法构成.多阶段启发式首先通过首层配载、主体配载和补充配载三段启发式完成初始解构造,其次采用横纵倾优化策略调整船舶稳性.算例研究表明,偏随机密钥混合遗传算法表现良好,且在大规模应用实验中鲁棒性较好,可实现客货滚装船的有效配载.

一种改进的二维装箱问题的混合遗传算法

改进了FFA算法,提出了区间合并和最小浪费面积的概念,并阐述了实现的方法.最后,采用基于改进的FFA算法的混合遗传算法得到了较好的结果,并对结果进行了分析.

用自适应遗传算法解二维装箱问题

二维装箱问题是一个NP难问题,用遗传算法来求解任意形状的二维装箱问题。算法模拟生物在面对恶劣环境时的行为,使得交叉率和变异率具有自适应性,克服了人工设定交叉率和变异率的不足;针对个体间适值差相对较小,新产生的好的染色体易丢失的特点,改进了随机选择个体的方法;算法还改进了适值函数,使得收敛速度有了较大的提高。此外,该算法与箱子的具体形状及物体的具体形状无关,当物体的数量增加和箱子与物体形状的复杂程度提高时,收敛速度仍然较快。

一种带剪切约束的启发式二维装箱算法

提出一种满足剪切约束的启发式二维装箱算法,通过价值修正策略提高箱的空间利用率,进而减少箱的使用数量。该启发式算法将较难装箱的物品赋予较高的价值及装箱优先权;并通过延展或融合剩余零散空间,将未用的空间合并到剩余相邻空间,以改进空间利用率。基于标杆测试数据集的仿真实验证明了该算法的有效性和相较于其他二维装箱算法的优越性。

二维装箱问题的一种实现方法

遗传算法 (GA)是基于自然淘汰地遗传机制的搜索算法 ,近年来利用遗传算法解决组合优化问题的研究十分普遍。二维装箱问题是典型的组合优化问题 ,也是时间复杂度非常高的 NP问题之一 ,如何实现有效的算法流程一直是该类问题的难点 ,本文在 BL算法的基础上 ,提出一种改进的算法结构和流程 ,并分析了用 GA实现过程中编码的健全性和完备性以及多样性评价问题。

带二维装箱约束的团队定向问题模型及优化算法

研究了在车辆服务资源有限、货物有特殊装载要求和其他因素影响下,为了能获得最大效益而采取特殊物流配送的问题——带二维装箱约束的团队定向问题。在对该问题进行明确定义基础上,建立了相应的数学模型;针对模型特点,设计了以遗传算法为框架,利用基于BLF的算法确保二维装箱约束的模型启发式算法。数值算例验证了算法的有效性。

考虑货物冲突关系的二维装箱问题研究

货物冲突及其处理方式直接影响货箱消耗量和货物装载成效,通过构建冲突矩阵和“冲突货物不能放置同一货箱内”处理方式,同时考虑负载安全因素,建立了考虑货物冲突关系的二维装箱优化模型.设计了改进的模拟退火算法,其运用贪心算法对货物冲突预处理,确保初始装箱序列为可行解;提出了兼顾当前温度和适应度影响的动态随机扰动率e方程,增强了邻域解的搜索能力,改善了算法整体性能.算例分析表明模型和算法有效.120种货物冲突稀疏度[0.1,0.9]情景下,货箱面积利用率均值为[0.342,0.732],降低了装载单元使用数量,提高了资源利用率.不同样本量情景下,改进算法的求解质量和运行效率表现良好.

二维装箱法在服装排料上的应用分析

文中运用模型与数值换算方法将数值结果和矩形裁片排列图进行对应,通过实例演示论证此方法的可行性,从而将服装排料问题转换成二维装箱问题,解决服装排料中存在的不能紧密套排的弊端。

精细建筑物碎片化纹理优化的二维装箱方法

为了解决精细建筑物模型大量碎片化纹理造成模型加载时间长和实时渲染效率低的问题,提出一种精细建筑物碎片化纹理优化的二维装箱方法.计算共用纹理并集区域,优化冗余纹理内容,并同时顾及超出常规坐标[0,1.0]范围的异常纹理;使用二维装箱算法对优化后的离散纹理进行封装,降低纹理数量;利用纹理映射和纹理集技术将优化后的纹理重映射到建筑物表面,然后对建筑群进行实验.研究结果表明:使用本文方法,纹理数据量减少了71.20%,纹理文件数量减少了99.37%,模型载入耗时减少了98.86%,图像处理器耗时减少了63.06%,并可有效避免因异常纹理坐标导致的纹理错误映射问题,同时也提高了数据格式的兼容性.

二维装箱问题的遗传算法求解

通过分析人工排列的思考过程和实际经验,提出一种解决二维规则物体排列问题的算法。通过计算可放置点和可放置空间,高效解决物块的排列问题。应用遗传算法,求得最优的排列方案。实际应用证明了该算法的有效性。

求解二维装箱问题的强化学习启发式算法

二维带形装箱问题是一个经典的NP-hard的组合优化问题,该问题在实际的生活和工业生产中有着广泛的应用.研究该问题,对企业节约成本、节约资源以及提高生产效率有着重要的意义.提出了一个强化学习求解算法.新颖地使用强化学习为启发式算法提供一个初始的装箱序列,有效地改善启发式冷启动的问题.该强化学习模型能进行自我驱动学习,仅使用启发式计算的解决方案的目标值作为奖励信号来优化网络,使网络能学习到更好的装箱序列.使用简化版的指针网络来解码输出装箱序列,该模型由嵌入层、解码器和注意力机制组成.使用Actor-Critic算法对模型进行训练,提高了模型的效率.在714个标准问题实例和随机生成的400个问题实例上测试提出的算法,实验结果显示:提出的算法能有效地改善启发式冷启动的问题,性能超过当前最优秀的启发式求解算法.

平面二维装箱问题“5块法”规划解法

平面二维装箱优化程度直接影响三维立体装箱优化程度。现有"4块法"数学规划解法虽然大幅度提高优化程度,但因数学模型存在一定缺欠:一是约束条件过多,缩小了可行域范围,影响求解优化程度;二是没考虑第5块摆放数量,优化程度低。为了解决这些问题,本文提出"5块法"规划解法,该方法既解决了约束条件过多弊端,又提高了优化程度;借助Excel规划求解,方法简单、易于掌握。

一刀切约束下的二维装箱问题高效求解算法

目的为实现大规模物料的快速剪裁切割,对考虑一刀切约束的二维装箱问题进行研究,并构建相应的改进优先度算法IPH(Improved Priority Algorithm,IPH)。方法IPH能够在不需要任何迭代搜索下,直接进行剩余空间分割与填充。为此,发展PH算法中的优先度放置规则,并以最大化生成大空间面积和最小化生成小空间面积为基础,设计改进砌砖式空间分割策略。结果针对标准数据集的对比实验表明,IPH能够在较短时间内完成大规模算例的高效求解,并首次获得了多个算例的最优填装效果。结论基于概率较优的启发式求解方法,能够实现无迭代优选下的一刀切二维装箱问题直接求解,且运算效果令人满意。

摆放约束的二维装箱研究

如何实现装载率更高的装载方式、提高容器装载空间的利用率,从而提高服务水平、降低运营成本,对于企业提高竞争力具有十分重要的意义。二维装箱有一种"最左最低对齐"的经典解法,其基本原理是将物品按宽度进行降序排列,再把物品装载至目前能容纳其体积的尽量低、尽量左的位置,但实际操作中,为便于查看货物信息,摆放货物时需要货物至少一面朝外。考虑上述摆放约束,在"最左最低对齐"算法的基础上,提出一种二维装箱问题优化解法,并结合实际算例进行分析。

基于“5块”法的二种货物二维装箱优化模型构建与实例

二种货物二维装箱问题是更为复杂的装箱问题,虽然有一些解法,但优化程度、求解效率和装箱效率不够理想,需要改进与完善。为了解决这一问题,本文提出一种新的解法,即把单一货物二维装箱问题中的“5块法”运用到求解二种货物二维装箱问题中。新方法借助Excel规划求解,方法简单、易于掌握、优化程度较高。

关于二维装箱问题的一种新算法

本文在分析了二维装箱问题的五种算法之后,提出了一种更加节省、简便的新算法。该算法已在IBM-5550微型机上用PASCAL语言实现了程序设计。

基于二维装箱问题的TTE调度表生成算法

为简化时间触发以太网调度表生成的复杂度并增强灵活性,对调度表生成算法进行研究。所提算法支持通讯任务的动态添加,特别是将链路时间资源抽象为“空箱子”,并将时间触发通讯任务抽象为“二维物品”,这种抽象利用无重叠二维装箱问题的特性来满足数据帧无冲突传输,利用二维装箱算法得出调度表。仿真结果表明,当网络中同时存在较多通讯任务时,改进算法可以有效降低链路的时间资源占用率。