基于改进ALNS 算法的离散制造车间物料配送路径优化研究

何家铮，王家海

（同济大学 机械与能源工程学院，上海 201804）

0 引言

在离散制造领域，为了满足个性化和快速响应市场的需求，多品种、小批量的生产模式变得越来越普遍。这种生产模式的灵活性虽然能够满足市场多变的需求，但同时也大幅增加了车间内物料配送的难度和复杂性。物料配送的效率和准确性直接影响到整个生产流程的顺畅和成本控制[1]，如何在保证物料按时供应的同时，减少配送时间和成本，如何优化配送路径以适应车间内复杂多变的布局和需求，都是亟待解决的问题。

在这样的背景下，研究和开发高效的物料配送路径优化算法变得尤为重要。车辆路径规划问题（VRP）被学者广泛研究，例如唐等[2]利用蚁群算法求解，也有部分学者探索了柔性制造车间的物料配送问题[3]，但通常未能精确结合车间实际情况，采用欧式距离作为节点距离，本文考虑车间通道约束、时间窗、小车容量、线边库容量等因素，通过引入和改进自适应大领域搜索（ALNS）算法解决求解离散制造车间物料配送的路径优化问题。

1 数学模型建立

1.1 问题描述

一个离散型制造车间，车间内有一个中心仓库和N 个物料需求工位点，由配送能力为Q 的AGV 执行物料配送作业，每个由物料需求的工位对物料存在时间窗要求[ETi，LTi]，找到最佳的运输车辆数以及最佳的运输路线。

基本假设如下：

（1）车辆从车间仓库装货后出发，经过各车间工位后最终返回车间仓库。

（2）单个工位的物料需求量不超过AGV 的运输载荷。

（3）一次配送任务中，单个工位的物料由同一辆AGV 小车完成配送，若配送完毕后有新的物料需求，增加新的配送任务由其他AGV 进行配送。

（5）物料需求点时间窗为软时间窗，且AGV 允许部分超载。

1.2 符号说明

在详细阐述具体的模型建立和求解过程之前，对模型中涉及的关键符号及变量进行详细定义，以确保理论推导的严密性和结果解读的一致性，相关符号变量见表1。

表1 数学模型符号说明

1.3 工位物料时间窗模型

针对晚于LTi到达的情况，该工位生产停滞，长时间后会影响相应工序的其他工位生产，对生产系统整体影响较大。针对早于ETi到达的情况，AGV 送抵的物料会超出线边库的最大库存，因此需等待线边库有足够库位后进行服务。即当ATi＜LTi时，令ATi=ETi，同时由于等待会产生等待惩罚。

1.4 车间通道约束下的距离模型

如图1 左所示，在传统车辆路径问题（VRP）中，节点间距离通常通过欧氏距离计算。适用于直线可达的场景。在车间环境中，由于路线限制和复杂布局，工位间不能直接以直线方式行驶，必须沿固定路径，如图1 右所示。采用像Floyd 算法这样的图论方法来计算最短路径以及寻找其路由[4]，比直线距离更能反映车间内的实际行驶条件，为车间VRP 问题提供更准确的解决方案。

图1 传统VRP 路径与车间通道约束下的路径图

1.5 物料配送成本模型

式（4）是以配送成本最小为目标函数，包括路径成本、超载惩罚和时间窗惩罚，每辆小车r成本的具体计算方式为：遍历小车（路径）r下的k个路径节点，计算节点k至节点k+1 的路径距离并累加，计算该路径下k个节点的需求量之和小车载重之差并附加超载惩罚系数，以及通过式（3）计算时间窗惩罚；式（5）确保配送顺序合理，同一条线路中当前节点小车的到达时间需大于等于上一个节点的到达时间、上一个节点的服务时间、两点之间移动时间之和；式（6）表示除了仓库节点0和i的集合完全相等，即每个工位一次只能由一辆配送小车配送，且只能被一辆AGV 配送一次；式（7）表示每辆AGV 的起点和终点都是车间仓库。

再者，这里是具有造船传统的女真人聚居区。远的不说，女真人的先世挹娄人就能造船，元代的女真人已能建造远征日本的大型战船。选择在这里造“巨舡”，不缺人才和技术，能够迅速完成造船任务。据此，明廷把船厂设在今吉林市阿什哈达村。

2 模型求解

基于车间布局、工位和拐点的位置，建立初始距离矩阵，并利用Floyd 算法求解通道约束下的最短距离矩阵，并基于此矩阵利用改进的ALNS 方法进行车间物料配送路径规划问题的求解，如图2 所示。

图2 模型求解流程图

2.1 Floyd 算法预处理

初始化，根据车间布局，基于图论，将同一通道上相邻的工位节点或车间拐点认定为“联通”，并设置最短距离为实际直线距离，对于不同通道上的节点，需要经过车间通道拐点到达，因此距离初始为无穷大，得到一个包含车间拐点的（N+t）×（N+t）初始距离矩阵A0。

迭代更新，对于不直接连通的节点对，利用式（8）找到通过一个或多个中间节点的最短路径，从而更新这些节点对之间的最短距离，每次迭代更新距离矩阵Ant。

当迭代次数nt=N+t时，迭代终止，移除车间拐点即得到N×N的基于车间路径约束的实际节点距离矩阵A′。Floyd 算法的时间复杂度是O（n3），空间复杂度是O（n2），其中，节点距离矩阵A′是后续物料配送的必要环节，其仅需要在车间布局变化时重新运算，否则只需运算一次。

2.2 ALNS 算法求解车间物料配送的VRPTW 问题

自适应大领域搜索算法（ALNS），是一种用于求解复杂优化问题的启发式算法[5]。它通过不断地摧毁和修复当前解的一部分来探索解空间，可以根据历史表现适应性的调整摧毁和修复的使用频率。

改进的ALNS 算法采用外层模拟退火，内层ALNS 的方式减少陷入局部最优的概率。ALNS 的每次迭代后进行成本比较，若新解是最优解则接受，否则以采用Metropolis 准则的方式接受相对劣解。

2.2.1 生成初始解

初始解编码示例如图3 所示。打乱节点数组I，依次分配给小车，当∑Di＞Q时，新增一辆小车，直至所有节点分配完毕。

图3 初始解编码示例

2.2.2 破坏和修复算子

本研究共采用3 个破坏算子和3 个修复算子，根据算子权重选择破坏算子和修复算子。如图4 所示，第一步：破坏，遍历当前解中的所有路径的节点，依据不同破坏规则从节点数组中选取一定数量的节点进行破坏移除，并加入移除节点列表；第二步：修复，根据不同的修复规则，将移除节点列表中插入被破坏的节点列表中。

图4 破坏和修复

（1）相关性破坏算子，也称Shaw 移除算子，目的是通过破坏相似或相关的节点来探索解空间的不同区域，本文基于节点的距离、时间窗和物料需求的相关性进行移除，节点与的相关性表达式为：其中，ω1、ω2、ω3表示的是距离、时间窗和物料需求的权重系数，R（i，j）越大表示节点的相关性越小。

（2）贪心破坏算子，一次移除一个节点，选择移除后成本降低最多的节点。每次移除节点前，计算当前总成本，并与移除每个可能节点后的新成本进行比较。选择使总成本降低最多的节点进行移除。

（3）随机破坏算子，随机选取一定数量的节点，并将这些节点从其所在的路线中删除。

（4）后悔插入算子，评估每个被移除节点插入任何位置的“后悔值”，选择当前具有最大后悔值的节点进行插入，目的是避免过早做出可能限制未来选择的决策，不仅考虑当前的最佳插入位置，还考虑对未来选择的潜在影响。

其中，Va是某节点插入后的成本，Vb是某节点插入前的成本，VI是插入成本，min2VI表示次佳插入成本，minVI表示最佳插入成本，最大后悔值VR是次佳插入成本min2V和最佳插入成本minVI之差。

（5）贪心修复算子，对于每个被移除的节点，考虑所有可能的插入位置，并选择使总成本增加最少的位置进行插入。

（6）随机修复算子，将之前被破坏的节点随机插入回路线中。对于每个被移除的节点，随机选择一条路线和该路线上的位置，并将节点插入到该位置。

3 实验分析

以某离散制造车间为案例，并使用改进的ALNS算法进行求解。该车间有1 个车间仓库、6 台数控车床、3 台数控铣床、1 台数控镗床、4 台钻床、3 个检测台，总计1 个车场和17 个需求节点，另有路径拐点10 个，如图5 所示。

图5 离散制造车间模型

车间工位位置、需求和时间窗等信息和拐点位置信息见表2，其中节点0 表示车间仓库，t1 -t10 为车间拐点。首先，利用节点坐标、拐点坐标和车间路径图，根据之间联通的节点（拐点）建立初始距离矩阵，并使用Floyd 算法得出个节点之间的最短距离矩阵，见表3。

表2 节点需求信息

表3 节点最短路径矩阵

本实验使用IDEA2021，CPU 为12600 k，利用ALNS 算法结合模拟退火，实验部分参数设置为：温度下降率0.99，最大迭代次数400，超载惩罚系数γ=1000，时间窗提前惩罚系数α=10，时间窗超期惩罚系数β=2，可提供的最大运力车辆为3，破坏算子和修复算子初始权重相等。

从表4 和图6 可知，在相同迭代次数下，ALNS 加入模拟退火后，求解时间略高于ALNS，但总体速度接近，可以满足车间物料配送的决策实时性，在求解时间接近的情况下跳出局部最优，获得成本更低的解。实验结果表明，该方法能够有效规划物料配送路径，减少配送时间和成本，并确保物料按时供应，提高了生产效率。

图6 收敛曲线对比

表4 基于车间路径约束的配送路径序列

4 结语

本研究通过构建离散制造车间物料配送路径优化的数学模型，并基于自适应大领域搜索（ALNS）算法进行了求解，有效地解决了多品种、小批量生产模式下的物料配送问题。实验结果表明，该模型能够有效地规划物料配送路径，减少配送时间，确保物料按时供应，同时降低物料配送成本。此外，通过引入车间路径约束、时间窗和车辆容量限制，模型更贴近实际生产环境，提高了其应用价值。未来的研究可以在此基础上同时取送货的车间道路约束下的车辆路径问题，以及考虑动态车间环境下的物料配送路径优化问题，引入实时数据反馈和机器学习技术。