基于时间窗约束的车间物料配送路径优化方法

朱伏平，曹婷婷

（西南科技大学制造科学与工程学院，四川绵阳 621010）

1 引言

随着制造业的高速发展，混流生产已成为企业满足市场需求的有效手段。混流生产中待配送的零部件种类繁杂、配送频率较高。同时，自动化设备的广泛应用，装配时间偏差、设备故障等不确定因素，增大了物料配送的难度。因此，研究混流装配线物料配送具有重要意义。

传统的物料配送多侧重于算法的设计。文献[1]针对车辆路径问题，提出一种结合萤火虫优化和蚁群系统算法的HAFA 算法。文献[2]在冷链物流路径优化模型中，针对蚁群算法收敛速度慢的问题，将A*算法与蚁群算法相结合。文献[3]提出一种通用的启发式算法，能解决五种车辆路径问题。文献[4]建立了混流车间物料配送路径模型并设计基于栅格环境地形的蚁群算法，并验证了算法的有效性。针对大量不确定因素导致实际需求发生偏差问题，文献[5]用正态模糊数的隶属度表征工位对物料到达时间的满意度。文献[6]用物料到达时间的模糊隶属度函数表征工位对物料到达时间的满意度。文献[7]用三角模糊数来表征工位对物料到达时间的满意度。模糊时间窗在一定程度上提高了物料配送时间的准确性，但未考虑车间实际生产情况。

近年，信息化技术为实时生产驱动物料配送提供了依据。文献[8]采用智能感知网获取工位实时生产数据，利用物料送达时间点与物料消耗速度确定每次配送时间窗，提高物料配送的准确性。但未考虑不确定性因素导致物料消耗速度的波动性。

基于上述分析，这里提出将实时生产数据与正态模糊数相结合的方法来计算时间窗。针对无法在规定时间窗内到达的车辆，建立成本惩罚函数。以配送成本最低为目标建立模型，采用改进遗传算法求解。最后应用实例验证方法的有效性。

2 工位物料需求时间数学模型

根据实时生产数据动态计算时间窗，然后利用正态模糊数来表征工位物料需求，从而提高工位物料需求时间满意度。

以工位不缺料为前提，计算工位服务时间区间长度[9]：

防止物料提前达到而出现等待，设置最早到达时间TEi：

防止因缺料而停线现象，设置物料最晚到达时间TLi，m：

式中：Vi，max—工位i的物料缓存区的最大容量—工位i的物料缓存区的安全库存；ci—单位物料在工位i的装配时间；Ti，m−1—工位i第m−1次物料送达时间；Vi，m−1—工位i第m−1次物料送达时工位i的线边库存；ti，m—工位i第m次配送的服务时间；m>1。

通过实时数据计算得到的工位i第m次配送的物料需求时间为[TEim，TLim]，根据文献［5］建立基于正态模糊数的物料需求时间满意度数学模型：

式中：ui，m—Ti，m的期望值；σi，m—高斯函数的宽度；μ(Ti)，m—Ti，m的隶属度，μ()Ti，m∈[0，1]，用于表示工位的满意度。Ts—期望时间，Ti，m离TS越近，满意度值越大；当Ti，m=Ts时，满意度最大为1。β—物料需求时间的正态模糊数置信度。TEi，m′，TLi，m′—置信度β下，工位i的时间窗下限和上限，如图1所示。

图1 工位i在置信度为β时配送时间窗Fig.1 Time Window of Distribution for Station i when Confidence Level is β

3 物料配送模型构建

3.1 问题描述

装配车间由一个仓库向N个工位提供物料，各工位旁有一个缓存量为Vi，max的物料缓存区，仓库有K辆运载能力为V的配送小车，始终保持匀速行驶。假设通过实时采集数据已知各工位的位置、需求量、物料服务时间和配送时间窗，建立总配送费用最低的路径规划数学模型。每个工位只能由一辆车访问一次，且满足以下主要约束条件：

（1）运载能力约束。任意小车所服务的工位物料需求量总和不超过最大运载能力为V。

（2）持续能力约束。小车从仓库出发，完成任务后回到仓库，总行驶距离不超过最大行驶距离L。

（3）时间窗约束。工位接受物料时间窗为[TEi,m′,TLi,m′]，如小车未在[TEi，m′，TLi，m′]内到达，则建立相应的成本惩罚函数，如下：

3.2 参数定义

根据问题描述，设置参数如下：

3.3 建立模型

构建配送成本最低的目标函数。

式（8）是总配送费用最小的目标函数；式（9）表示配送小车的数量；式（10）表示每个工位只能由一辆小车配送；式（11）表示任意小车运载量不超过小车最大装载容量；式（12）表示小车从仓库出发，完成任务后回到仓库，式（13）表示任意小车行驶距离不超过小车最大行驶距离，式（14）表示置信度为β时，配送时间窗限制；式（15）表示工位i需要物料时间要满足正态模糊数的置信度β；式（16）表示工位i的等待时间。

4 模型求解

遗传算法具有良好的全局搜索能力和鲁棒性，搜索效率高，非常适合处理路径规划等非线性优化问题。但容易出现早熟现象，陷入局部最优解。因此，这里对遗传算法进行改进，引入禁忌搜索算法。当遗传算法的迭代次数为10的整数倍时，执行禁忌搜索，利用禁忌策略限制搜索陷入局部最优。算法流程，如图2所示。

图2 算法执行流程Fig.2 Execution Flow of Algorithm

4.1 编码

这里采取自然数编码方式，设计两层染色体，第一层表示配送工位，第二层表示配送小车。第一辆小车的配送路径为0−7−6−1−0；第二辆小车的配送路径为0−4−5−2−0；第三辆小车的配送路径为0−8−3−0，如图3所示。

图3 编码示意图Fig.3 Coding Diagram

4.2 适应度设计

初始群体按编码生成配送路径方案，编码隐含每个工位仅由一辆车服务一次的约束条件，但不能保证小车配送最大行驶距离和载重量的约束。

为此，对判断每条子路径是否满足约束条件。这里假设个体i所有子路径中不可行（Yi>0）的个数为Yi，模型目标函数为Zi，则自适应度值为：

式中：W—无穷大的数，用于惩罚不可行个体。

4.3 遗传操作

4.3.1 选择策略

为保证适应度高的个体进入下一代，采用最佳个体保留法结合轮盘赌法的方法。

4.3.2 交叉策略

传统的交叉方式可能产生大量不可行解，从而丢失优良解，这里采用一种改进的交叉法[10]进行交叉，其基本流程如下：

（1）根据选择策略选取两条染色体作为父代A、B；

（2）随机选择父代A、B的交叉区域；

（3）提取父代A、B的交叉区域配送工位基因值，如果基因值相同，则交叉区域进行交换，从而得到子代A1、B1，若基因值不相同，则返回（2）；

（4）计算父代A、B，子代A1、B1的适应度值，保留较优的两个作为新个体A2、B2。

图4 交叉操作示意图Fig.4 Schematic Diagram of Cross Operation

4.3.3 变异策略

为维持种群多样性，提高算法的局部搜索能力，本文选择分组单点变异，其基本流程如下所示：

（1）根据选择策略选取两条染色体作为父代C；

（2）随机选择父代C基因中的两个非零点；

图5 变异操作示意图Fig.5 Schematic Diagram of Variation Operation

（3）确保配送工位基因不变，交换两工位间的配送路线，得到子代C1；

（4）计算父代C和子代C1的适应度值，保留较优的一个作为新个体C2。

4.4 禁忌搜索策略

禁忌搜索的基本流程如下：

（1）选择通过遗传操作产生的当前代中所有个体为子集，建立禁忌搜索集合E；

（2）随机选择集合E中的一个个体ei为初始解，并置空禁忌表和最优状态；

（3）根据ei生成若干候选解集；

（4）藐视规则处理。若禁忌搜索产生的解优于当前最优解，则该解作为新的当前最优解和目前为止最优解，并更新禁忌表；若禁忌搜索产生的解劣于当前最优解，则从候选集中选择非禁忌产生的最优解作为当前解，同时更新禁忌表；

（5）重复（3）和（4），直至E中所有对象ei均进行过禁忌搜索；

（6）输出最优结果。

5 实例验证

为验证方法和模型的有效性，本文以某冰箱装配线为例，用MATLAB进行验证。装配线有10个工位，各工位之间的距离及仓库到各工位间的距离，如表1所示。其中0代表仓库，1～10代表工位。

表1 工位间距离（单位：米）Tab.1 Distance Between Stations（unit：m）

配送小车的最大配送量Q=300kg，最大行驶距离为2000m，行驶速度为1m/s。

设单位距离的行驶成本C1=0.02元/米，每辆配送小车的启动成本C2=50 元/辆，每早到1min 的惩罚成本为C3=1 元，每迟到1min的惩罚成本为∞。

各工位的物料需求量qi、物料需求时间窗及各工位的服务时间，如表2所示。

表2 物料需求时间表Tab.2 Material Demand Schedule

设种群大小为85，交叉概率和变异概率分别为0.6、0.05，迭代次数为100。

由文献[7]知，置信度β取0.2时，找到目标函数最优解可能性最大。

因此，这里取β为0.2，对正态模糊时间窗方法和正常时间窗方法进行求解，结果轨迹，如图6所示。

图6 收敛对比图Fig.6 Convergence Contrast Graph

由图6可知，正态模糊时间窗方法和正常时间窗方法分别经过36次、44次迭代收敛得到最优解，正态模糊时间窗方法收敛速度较快比较两种方法得到的最优解，如表3所示。

表3 两种方法结果对比Tab.3 Comparison of Results of Two Methods

由表3可知，正态模糊时间窗方法和正常时间窗方法计算出配送成本分别为190.11元、207.47元。从以上仿真结果及其分析可以看出，与正常时间窗方法相比，正态模糊时间窗方法的收敛速度、配送成本和总行驶距离均更优。

6 结束语

针对混流生产线物料配送难度大的问题，本文提出了将实时生产数据与正态模糊函数相结合的时间窗计算方法。

在此基础上，综合考虑车辆启动费用、行驶费用和等待费用，建立了带时间窗约束的配送路径优化模型，并采用基于禁忌搜索的遗传算法求解。以某冰箱装配线为实例，验证了这里方法的可行性和有效性。