车间物料配送是一种典型车辆路径问题(Vehicle routing problem, VRP), 近年来许多学者都对该类问题进行过深入研究。Chen等^[1]在车辆路径问题中引入模糊时间窗概念, 对车队规模、平均顾客满意度、运输距离和排队时间等优化目标进行了分析并采用遗传算法求解。Taillard等^[2]对带软时间窗的车辆路径规划问题进行了建模, 采用禁忌搜索算法对问题进行求解。Muller等^[3]求解带时间窗的车辆路径规划问题时, 将多目标优化问题转化成单目标优化问题, 采用启发式算法对模型求解。Banos等^[4]从平衡配送路线长度和车辆负载角度对物料配送问题进行研究, 采用基于平行多目标模拟遗传算法对问题进行求解。Zhou等^[5]从配送总距离和单车配送距离平衡角度对物料配送问题进行研究, 采用遗传算法对问题进行求解。蒋丽等^[6]提出了以工位为中心的物料配送方案, 将物料按照工位需求进行分类存储, 从物料储存和配送角度对物料配送进行优化。李晋航等^[7]针对物料配送环节中的不确定因素提出了模糊信息条件下的机会约束模型, 以最小化物料运输距离为优化目标, 采用改进遗传算法对模型进行求解。严正峰等^[8]考虑生产节拍波动引起的物料需求时间变化, 建立了带模糊软时间窗的物料配送路径优化模型, 结合动态规划-模拟退火算法对模型进行求解。葛茂根^[9]等针对物料准时配送问题, 提出了基于物料运输成本、运输时间、线旁库存的多目标准时配送模型, 并设计了混合粒子群算法对模型求解。凌琳等^[10]针对车间作业环境的不确定性, 提出了计及漂移瓶颈的时变物料配送路径优化方法, 采用瓶颈指数和瓶颈漂移指数表征物料配送优先级, 以最小车辆运输和优先级惩罚成本为优化目标, 建立时变物料配送模型, 采用遗传算法对优化模型求解

上述研究从配送方法、配送模型和算法角度为车间物料配送问题提供了大量求解思路, 但该类研究未能充分考虑真实的车间物料配送环境, 存在以下几点不足:首先, 节点间的物料配送距离用静态直线距离表示, 忽略了实际的配送轨迹, 脱离了实际的车间物料配送通道网络; 其次, 各目标节点间存在多条物料运输路径, 不同的物料运输路径对应不同物料运输参数(配送距离、配送时间等), 忽略了节点间物料配送参数的多样性; 最后, 路径规划中的各类初始信息都是静态信息, 忽略了车间路网通道流通能力的时变性, 不能准确描述不同时段的物料配送时间成本。随着制造物联技术在离散制造车间中的应用, 车间的实时感知能力得到有效增强:如通过射频识别技术(Radio frequency identification, RFID)对物料进行标识, 能够实时、准确掌握工位的物料消耗情况; 通过超宽带(Ultra wideband, UWB)等实时定位技术对车间要素(如配送车辆、人员、大型工装等)进行实时定位, 能够实时获取生产要素在车间中的位置信息、速度以及分布情况, 结合车间通道信息可全面、准确反映车间实时环境。

本文以制造物联技术为支撑, 采用“以工位为中心”的物料配送思想, 将大型离散制造车间工位划分成多个工作中心, 简化物料配送问题规模^[6]。每个工作中心具有多台相同的加工设备, 执行相同的加工任务。以工作中心间物料配送路径多样性和通道流通能力时变性为基础, 将各工作中心间的物料运输路路径的路阻系数引入车间物料配送问题, 结合工作中心对物料到达时间窗的要求, 构建了基于车间实时环境的物料配送问题数学模型。最后采用改进遗传算法对所构建的数学模型进行求解, 通过实验对模型和算法的有效性、可行性进行验证。

1 物料配送路径规划问题建模 1.1 车间环境约束

在离散制造车间物料配送过程中, 经常出外部干扰因素对物料配送时间造成影响, 如通道内车辆会车、人员流动干扰、通道临时占用等因素。因此在物料配送过程中需要考虑以下约束条件:

(1) 车间通道约束。物料配送活动在车间通道路网中进行, 物料配送小车运动路径受车间通道路网约束, 运动轨迹不能脱离实际的车间通道, 物料配送距离为物料配送小车运动轨迹长度。车间通道的通行特性(是否双向通行)、通道宽度以及连通特性也都将对车间物料配送活动产生约束。

(2) 物料配送路径约束。大型离散制造车间空间范围广, 工作中心间存在多条物料配送路径, 不同的物料配送路径对应不同的物料配送距离。当选择不同的物料配送路径时, 物料配送距离将随着当前物料配送路径变化。

(3) 车间通道流通能力约束。大型离散制造车间通道的流通能力具有时变性, 当车间通道出现外部干扰时, 造成通道内小车运动速度发生变化, 导致同一物料配送路径在不同时段的时间成本不再唯一确定。

1.2 时间窗约束

离散制造车间中, 工位的线边库存空间有限, 无法存储大量物料, 所以要求物料配送满足一定的时间区间要求。针对某一个具体的工位, 如果所需的物料早于规定时间到达工作中心线边库存区, 不一定有足够的空间容纳最新到达物料, 增加了车辆的等待成本。当所需物料晚于规定时间到达工作中心线边库存区时, 容易造成工位缺料等待, 影响整个生产线的生产效率。因此, 这些问题使物料的送达时间受到了严格要求。但在实际的生产过程中, 由于受到车辆数量限制和车间环境的影响, 物料配送车辆早于或晚于规定时间到达目标工作中心往往是不可避免的。因此, 合理量化车辆在规定时间窗外到达目标工位额外增加的配送成本十分必要。针对这一情况, 本文通过软时间窗, 建立可接受时间区域之外的时间成本惩罚函数, 从而更加全面地描述目标工位对物料达到时间的评价。对于工作中心i, 当物料在规定时间范围[a_i, b_i]内送达目标工位时, 时间惩罚成本为0;当物料晚于或早于规定时间送达时, 将获得额外的时间惩罚成本, 惩罚系数为k₁, k₂。

${{P}_{i}}\left( t \right)=\left\{ \begin{array}{*{35}{l}} 0 \\ {{k}_{1}}({{a}_{i}}-t) \\ {{k}_{2}}\left( t-{{b}_{i}} \right) \\ \end{array} \right.\begin{matrix} {{a}_{i}}\le t\le {{b}_{i}} \\ t＜{{a}_{i}} \\ t>{{b}_{i}} \\ \end{matrix}$

(1)

1.3 问题描述

离散制造车间有一个物料配送中心, 工作中心由配送中心发出的车辆进行物料配送服务。工作中心间存在多条物料配送路径, 各路径的物料运输速度受车间环境影响, 同一路径在不同时间段对应不同的物料运输时间成本。物料配送受时间窗[a_i, b_i]约束, 若车辆不在[a_i, b_i]内到达, 则建立相应的时间惩罚函数; 求在特定车间环境下使车辆配送费用最小的车辆行驶路径。除此之外, 还需满足以下约束条件。

(1) 配送开始时, 车辆由配送中心出发进行物料配送, 当物料配送至最后一个工作中心时配送任务完成。

(2) 每个目标工作中心只能由一辆车服务。

(3) 每次每个工作中心物料需求为一个标准单位, 配送车辆受配送容量限制, 每次最多配送6个标准单位物料。

(4) 物料配送过程中, 车间通道环境保持不变, 各路径的路阻系数保持不变。

(5) 各工作中心间存在多条物料配送路径, 各路径已提前规划好, 路径长度为确定值。

1.4 符号变量

M为物料配送中心, 编号为0;N为离散制造车间工作中心集合, N={1, 2, …, n}; K为车辆集合, K={1, 2, …, m}; b为工作中心之间的路径数量; d_ijc为工作中心i到工作中心j的第c条路径长度; a_ijc为工作中心i到工作中心j的第c条路径的路阻系数, 用于表征物料配送过程中车间通道环境对物料配送时间的影响; t_i为车辆到达工作中心i的时间, P_i(t_i)为到达时间超出工作中心i的时间窗所对应的时间惩罚成本函数; Q为车辆的容量。

x_ijc=1表示车辆k由工作中心i运动到工作中心j, 且i≠j, 否则x_ijc=0。

y_ik=1表示工作中心i由车辆k服务, 否则y_ik=0。

z_ijc=1表示车辆从第c条路径从工作中心i运动到工作中心j, 且i≠j, 否则z_ijc=0。

1.5 模型建立

本文建立的车间实时环境下的物料配送模型为

$\begin{matrix} \min f=\sum\limits_{i=1}^{n}{{}}\sum\limits_{j=1}^{n}{{}}\sum\limits_{k=1}^{m}{{}}\sum\limits_{c=1}^{b}{{}}{{d}_{ijc}}(1+{{a}_{ijc}}){{x}_{ijk}}{{z}_{ijc}}+ \\ \sum\limits_{i=1}^{n}{{}}\sum\limits_{k=1}^{m}{{}}{{y}_{ik}}{{P}_{i}}({{t}_{i}}) \\ \end{matrix}$

(2)

$\text{s}\text{.t}\text{. }\sum\limits_{k=1}^{m}{{}}{{y}_{ik}}=1\text{ }\quad i=1,\text{ }\ldots ,\text{ }n$

(3)

$\sum\limits_{i=0}^{n}{{}}\sum\limits_{k=1}^{m}{{}}{{x}_{ijk}}=1\quad \text{ }j=0,\text{ }1,\text{ }\ldots ,\text{ }n$

(4)

$\sum\limits_{j=0}^{n}{{}}\sum\limits_{k=1}^{m}{{}}{{x}_{jik}}=1\quad \text{ }i=0,\text{ }1,\text{ }\ldots ,\text{ }n$

(5)

$\sum\limits_{i=1}^{n}{{}}{{y}_{ik}}\le Q\quad \text{ }k=1,\text{ }\ldots ,\text{ }m$

(6)

式(2) 以总的配送成本为目标函数; 式(3) 表示每个目标工作中心都有一辆小车负责配送; 式(4) 和式(5) 表示每个目标工作中心有且仅有一辆小车负责访问一次; 式(6) 为车辆装载容量约束, 限定了每辆小车的装载容量不能超过小车的容量。

2 模型求解

本文研究的问题主要由物料配送序列分配和工作中心间路径选择两个子问题组成, 结合目标工作中心物料配送时间窗要求和车间通道当前环境, 生成带物料配送路线的工作中心序列。遗传算法能够并行搜索, 搜索效率高, 但容易出现早熟, 陷入局部最优解。禁忌搜索算法通过禁忌表防止解的重复搜索, 在搜索过程中可以接受劣解, 从而跳出局部最优解; 加之存在藐视准则, 能够实现最优解的保留; 但搜索过程为串行搜索效率较低, 对初始解的依赖性较强。针对上述情况, 本文拟采用结合禁忌搜索的改进遗传算法对问题进行求解, 整个模型的求解流程如图 1所示, 其中L为大于等于1的整数, g为改进遗传算法的种群当前进化代数。

2.1 染色体编码方式

遗传算法的核心之一是根据求解模型确定染色体并进行编码。结合上述模型特点, 可以将y_ik和z_ijc作为染色体, 因此用染色体表示车辆物料配送方案和物料运输路径方案。最后采用两层编码技术, 用矩阵的形式表达染色体, 将n个工作中心表示成矩阵的形式。例如, 5个工作中心、2辆车的物料配送方案用矩阵F表示

$\mathit{\boldsymbol{F}}=\begin{matrix} x \\ y \\ \end{matrix}\left[ \begin{matrix} 0\quad 1\quad 2\quad 3\quad 0\quad 4\quad 5 \\ 0\quad 1\quad 1\quad 2\quad \rm{ }0\quad \rm{ }1\quad \rm{ }1 \\ \end{matrix} \right]$

(7)

式中:x表示工作中心节点(0表示物料配送中心), y表示工作中心间的路径编号(路径数比工作中心数少一个, 0用于填补首位空缺)。F表示两条物料配送序列, 序列1为0-1-2-3, 序列2为0-4-5, 每辆小车负责一个物料配送序列。各工作中心间存在多条配送路径, 各路径按距离长短依次用序号排列区分。序列1中, 物料配送小车由配送中心出发, 通过配送中心与工作中心1间的第一条路径到达工作中心1, 然后依次根据相应路径运动至目标工作中心, 完成物料配送, 如图 2所示, 图中带箭头实线为工作中心间的物料配送路径。初始化种群时, 改进遗传算法通过精英保留策略构建初始种群, 即每次随机生成多个染色体F_i, 从中选择适应度最好的个体F_best, 放入初始种群中; 如此反复操作直到初始种群规模达到设定值。

2.2 适应度函数

种群中存在多个染色体个体, 需从两个方面对其优劣进行判断。首先, 染色体个体是否满足配送约束条件; 其次, 染色体目标函数值大小, 即对应的物料配送成本大小。根据物料配送约束条件, 本文的编码方式能保证每个目标工作中心都能被服务到并且只能服务一次, 但不能保证每两个工作中心间的运输路线约束和车辆容量约束。因此, 需要对生成的染色体进行筛选, 选择出符合约束条件的染色体个体, 再计算其目标函数值。对于单个染色体F_i, 设其目标函数为f_i, 则该染色体的适应度函数如式(8) 所示, 其中D为很大的正整数。

${{h}_{i}}=\frac{1}{{{f}_{i}}+D}$

(8)

2.3 染色体操作

(1) 选择操作

选择操作为了保证群体中性能较好的个体能保存下来, 尽量保留群体中的优良基因, 从而加快算法的收敛, 寻找最优解。本文采用保留最优个体和锦标赛相结合的方法。假设种群的个体数量为M, 将种群中的每个个体按适应度函数值大小进行排序, 选择出其中适应度函数值最大的个体, 对剩余M-1个个体采用锦标赛选择方法选择出M-1个子代个体。通过这种选择方法, 可以保证父代中最优个体遗传到子代种群, 同时也保证父代种群中适应度较高的个体以较大的机会遗传到子代种群。

(2) 交叉操作

由于染色体编码方式的影响, 传统的交叉操作可能导致生成的染色体中同一工位出现两次或者物料配送中心相邻的情况, 生成大量不可行解, 造成优良基因的流失。本文采用一种改进的交叉策略, 尽可能保留上一代的优良基因。具体操作步骤如下, 首先, 随机选择染色体交叉区域; 其次, 提取父代染色体中交叉区域工作中心基因值, 如果父代染色体中的工作中心基因值相同, 则进行交叉操作, 否则重新选择交叉区域进行以上操作, 具体操作如图 3所示。

(3) 变异操作

在算法执行过程中, 变异操作结合交叉操作, 辅助染色体种群进化, 保证种群的的多样性。随机选择父代基因的两非零点, 保证工位基因值不变, 交换两工位间的运输路线; 即在矩阵中随机选择两非零列, 保持第一行数据不变, 对换第二行的数据, 生成变异染色体。如图 4所示, 父代矩阵N通过变异操作成为N^*。

2.4 禁忌搜索操作

遗传算法通过选择、交叉、变异等操作选择出种群中的优良个体, 当种群当前进化代数为10的整数倍时则进入禁忌搜索, 既保证算法的执行效率, 又防止算法陷入局部最优解。禁忌搜索流程如图 1所示, 具体实现步骤如下:

第1步:选择改进遗传算法当前代中的全部个体, 构建禁忌搜索集合T。

第2步:选择T中个体s_i, 置空禁忌表和最优状态。

第3步:同时根据s_i生成若干邻域解, 并从中确定若干候选解。

第4步:禁忌表处理和藐视操作。若禁忌搜索产生的最优邻域解优于当前最优解s_best, 则执行藐视准则; 用该最优邻域解更新s_best和s_current, 并将其放入禁忌表中, 同时将满足禁忌长度的对象从表中释放; 若不存在上述邻域解, 则从所有邻域解中选择非禁忌的最优解作为s_current, 同时将其放入禁忌表中, 释放禁忌表中满足禁忌长度的对象。

第5步:如果s_i已达到规定的搜索次数, 则结束对s_i的搜索, 转到第6步; 否则转到第3步。

第6步:判断T中所有对象s_i是否都已进行过禁忌搜索; 如果所有对象均完成搜索, 则输出最优结果, 返回改进遗传算法; 否则跳转至第2步。

3 实例验证

某大型机加车间中有1个物料配送中心, 多辆物料配送小车, 8个工作中心。每个工作中心之间存在多条物料配送路径, 分别取其中距离最短的3条路径作为实验参数。某次生产过程中需要将物料配送至目标工作中心, 配送小车由物料配送中心出发, 容量约为6个单位。各工位间的物料运输路线长度、路阻系数如表 1所示, 各工作中心物料配送任务表如表 2所示。求在满足配送约束条件下, 安排物料配送序列和行车路线使物料配送成本最小。

本例在MATLAB上求解, 在同一车间环境中用传统带时间窗的物料配方法和考虑车间实时环境的物料配送方法分别对物料配送问题进行求解。传统带时间窗的物料配送方法中, 各工作中心间有且仅有一条物料配送路径, 在本文中取各工作中心间最短物料配送路径为实验参数, 路径序号为1。具体遗传参数如下:种群规模为150, 最大进化代数100, 交叉概率为0.1, 变异概率为0.1。两种方法的物料配送结果如表 3所示, 最优的物料配送工作中心序列和工作中心间的配送路径如表 4所示。

从表 3可知, 考虑车间实时环境的物料配送方法和传统带时间窗的物料配送方法完成配送任务所需时间分别为18.3, 19.18 min, 两种方法的任务完成时间相差不大, 前者略优于后者。但由于缺少对车间物料配送环境的考虑, 传统带时间窗的物料配送方法在配送路径的选择上缺乏灵活性, 无法根据物料送达时间窗要求调整物料运输路径, 造成了较大的时间惩罚成本, 如表 3所示。两种物料配送方法的时间惩罚成本分别为164.7, 334.8, 考虑车间实时环境的物料配送方法较传统带时间窗的物料配送方法的时间惩罚成本降低了约50%。另一方面, 考虑车间实时环境的物料配送方法与传统带时间窗的物料配送方法相比, 使物料配送成本降低了12.4%。

综上可知, 考虑车间实时环境的物料配送方法在物料配送过程中, 可根据车间实时环境和物料配送时间窗要求, 灵活生成物料配送工作中心序列以及工作中心间的物料配送路径, 有效降低物料配送成本和时间惩罚成本。与传统带时间窗的物料配送方法相比, 基于车间实时环境的物料方法的配送成本降低了12.4%, 时间惩罚成本降低了50%, 有效的提高物料配送效率和准确性。

4 结束语

本文以离散制造车间实时环境下的物料配送路径优化为目标, 采用“以工位为中心”的物料配送思想, 将工位划分成工作中心, 简化物料配送问题规模。在此基础上, 对物料配送环境进行分析, 阐述了工作中心间物料配送参数的多样性, 定义了软时间窗描述实际生产过程中工作中心对物料送达时间的要求, 构建了基于车间实时环境的物料配送模型, 并采用遗传算法对模型进求解, 实现了离散制造车间物料配送序列和工作中心间配送路径的优化, 提高了物料配送的及时性和准确性。