论文部分内容阅读
摘要：汽车制造有四大关键工艺——冲压、焊接、涂装和总装，其中总装车间的占地面积最大、工人数量最多，迫切需要技术帮助降本增效。本文构建了以所有车辆服务工位间的距离总和与仓库间的距离总和为目标的优化模型，并设计了遗传算法进行求解，最终得到了适应度值为2.1785543113589823e-05的分配方案。
关键词：工位分组;配送物料优化;遗传算法
中图分类号：F407.474 文献标识码：A 文章编号：1674-957X（2021）16-0153-02
1 问题分析
物料配送的全周期主要包含两个步骤：①取料：前往目标物料的存储位，将物料装载至拖车;②配送：将物料运送至目标工位和卸载。这就意味着，要想在承包制模式下提高整个汽车组装车间的配送效率，就需要尽可能让车辆从距离较近的几个仓库取到装配工位较近的物料。即本文认为，让所有车辆节省取货时的行驶成本与送货时的行驶成本可以提升整个车间的效率。[1]基于此想法，本文构建了的模型，并且设计了算法进行求解，详细的思路、模型及算法详见后文。
2 符号说明
D：仓库的集合;
N：工位的集合;
K：车辆的集合;
dij：位置i与位置j之间的行驶距离;
tij：位置i与位置j之间的行驶时间;
L：车辆装/卸零件耗时;
S：车辆的行驶速度;
M：最大可装载任务数;
Tn：工位n的需求时间;
tkn：车辆k到达工位n的时间;
ω1：车辆晚于需求时间带来的惩罚成本;
■;
■。
3 建模与求解
3.1 建模
结合前述对模型的分析，我们认为在承包制模式下是对工位进行划分时，需要考虑车辆从III区装货过程产生的行驶成本，所以在形成分配方案时要将装货过程的影响考虑进来，不能只是按照工位的分布特点来划分承包区。据此，提出了模型的优化目标如公式（1）所示。
（1）
式（1）中共有两部分构成，其中■表示所有车辆服务工位间的距离总和，■表示仓库间的距离总和，该目标值越小则说明车辆的行驶距离越短，车间效率越高。
3.2 求解模型
3.2.1 距离数据的获取
基于求解模型的思想，我们需要计算出工位与工位之间的距离[2]，仓库与仓库之间的距离，此外，对于后文的研究会利用到工位与仓库之间的距离，故在此将计算这三部分距离数据：
①工位与工位之间的距离;
②仓库与仓库之间的距离;
③工位与仓库之间的距离。
由于汽车装配车间的结构复杂，工位分布呈流水线形式，道路的排布也十分有特点，直接导致了获取不同位置间的距离需要进行归类然后对每一类进行计算。本文根据车间构造的特点在对任意两个位置间的距离进行计算时，设计了如图1所示的框架。
通过上述计算距离的框架可以计算出任意两个位置间的距离，本文利用Python编程进行计算，部分距离结果见表1。
3.2.2 遗传算法设计
在计算得到距离数据后，本文设计了遗传算法对承包区的划分进行了求解。算法的具体流程如下所示：
①编码与解码。将I区与II区的48个工位以列表的数据结构随机排序，在排序后将整个列表划分为10个部分，并使每个部分不得超过5个工位，其中每个部分就是一个承包区。
②适应度函数。适应度函数用来评价个体的优劣，本文选取目标函数的倒数作为适应度函数，即适应度函数fitness=■。
③选择操作。本文采取了轮盘赌选择法[3]，该方法又称比例选择方法，基本思想是：各个个体被选中的概率与其适应度大小成正比。具体操作可以表示为：1）计算出群体中每个个体的适应度;2）计算出每个个体被遗传到下一代群体中的概率;3）计算出每个个体的累积概率;4）在[0，1]区间内产生一个均匀分布的伪随机数r;5）若r<q[1]，则选择个体1，否則，选择个体k，使得：q[k-1]<r≤q[k]成立;6）重复4）和5）直到选择出整个种群。
④交叉操作。随机选择两条染色体，然后随机选择两个基因位，两个基因位间的部分作为交叉部分，分别将两条染色体的交叉部分放置到彼此的前段，然后从前向后排查，将染色体中重复的基因删除，这样可以获得子代染色体。
⑤变异操作。随机算计一条染色体并随机选择两个位置，将两个基因进行互换。
⑥终止规则。本文采取设置最大迭代次数的方式作为改进遗传算法的终止条件。
3.2.3 求解结果
设置种群数量为100，最大迭代次数为100代，交叉概率为0.9，变异概率为0.1，利用上述遗传算法的求解，最终计算得到适应度函数为2.1785543113589823e-05的优化方案，具体分组结果如表2所示的结果，算法收敛曲线图如图2所示。
4 总结
本文成功对汽车组装车间背景下物料配送的相关问题进行了数学建模，并设计了以遗传算法对模型进行求解。对于模型的求解本文设计了高效的遗传算法用以求解模型，在交叉操作的设计上，成功规避了个体基因的重复，同时对于软硬约束的处理通过“罚值”得到了有效的控制，使得模型的有效性和健壮性得到了极大的增强。
参考文献：
[1]吴亮亮，蔡红霞，朱政.汽车零件制造企业物料配送模式优化[J].工业控制计算机，2020，33（02）：124-125.
[2]李晋航.混流制造车间物料配送调度优化研究[D].华中科技大学，2012.
[3]李永林，叶春明，刘长平.轮盘赌选择自适应和声搜索算法[J].计算机应用研究，2014，31（06）：1665-1668.
关键词：工位分组;配送物料优化;遗传算法
中图分类号：F407.474 文献标识码：A 文章编号：1674-957X（2021）16-0153-02
1 问题分析
物料配送的全周期主要包含两个步骤：①取料：前往目标物料的存储位，将物料装载至拖车;②配送：将物料运送至目标工位和卸载。这就意味着，要想在承包制模式下提高整个汽车组装车间的配送效率，就需要尽可能让车辆从距离较近的几个仓库取到装配工位较近的物料。即本文认为，让所有车辆节省取货时的行驶成本与送货时的行驶成本可以提升整个车间的效率。[1]基于此想法，本文构建了的模型，并且设计了算法进行求解，详细的思路、模型及算法详见后文。
2 符号说明
D：仓库的集合;
N：工位的集合;
K：车辆的集合;
dij：位置i与位置j之间的行驶距离;
tij：位置i与位置j之间的行驶时间;
L：车辆装/卸零件耗时;
S：车辆的行驶速度;
M：最大可装载任务数;
Tn：工位n的需求时间;
tkn：车辆k到达工位n的时间;
ω1：车辆晚于需求时间带来的惩罚成本;
■;
■。
3 建模与求解
3.1 建模
结合前述对模型的分析，我们认为在承包制模式下是对工位进行划分时，需要考虑车辆从III区装货过程产生的行驶成本，所以在形成分配方案时要将装货过程的影响考虑进来，不能只是按照工位的分布特点来划分承包区。据此，提出了模型的优化目标如公式（1）所示。
（1）
式（1）中共有两部分构成，其中■表示所有车辆服务工位间的距离总和，■表示仓库间的距离总和，该目标值越小则说明车辆的行驶距离越短，车间效率越高。
3.2 求解模型
3.2.1 距离数据的获取
基于求解模型的思想，我们需要计算出工位与工位之间的距离[2]，仓库与仓库之间的距离，此外，对于后文的研究会利用到工位与仓库之间的距离，故在此将计算这三部分距离数据：
①工位与工位之间的距离;
②仓库与仓库之间的距离;
③工位与仓库之间的距离。
由于汽车装配车间的结构复杂，工位分布呈流水线形式，道路的排布也十分有特点，直接导致了获取不同位置间的距离需要进行归类然后对每一类进行计算。本文根据车间构造的特点在对任意两个位置间的距离进行计算时，设计了如图1所示的框架。
通过上述计算距离的框架可以计算出任意两个位置间的距离，本文利用Python编程进行计算，部分距离结果见表1。
3.2.2 遗传算法设计
在计算得到距离数据后，本文设计了遗传算法对承包区的划分进行了求解。算法的具体流程如下所示：
①编码与解码。将I区与II区的48个工位以列表的数据结构随机排序，在排序后将整个列表划分为10个部分，并使每个部分不得超过5个工位，其中每个部分就是一个承包区。
②适应度函数。适应度函数用来评价个体的优劣，本文选取目标函数的倒数作为适应度函数，即适应度函数fitness=■。
③选择操作。本文采取了轮盘赌选择法[3]，该方法又称比例选择方法，基本思想是：各个个体被选中的概率与其适应度大小成正比。具体操作可以表示为：1）计算出群体中每个个体的适应度;2）计算出每个个体被遗传到下一代群体中的概率;3）计算出每个个体的累积概率;4）在[0，1]区间内产生一个均匀分布的伪随机数r;5）若r<q[1]，则选择个体1，否則，选择个体k，使得：q[k-1]<r≤q[k]成立;6）重复4）和5）直到选择出整个种群。
④交叉操作。随机选择两条染色体，然后随机选择两个基因位，两个基因位间的部分作为交叉部分，分别将两条染色体的交叉部分放置到彼此的前段，然后从前向后排查，将染色体中重复的基因删除，这样可以获得子代染色体。
⑤变异操作。随机算计一条染色体并随机选择两个位置，将两个基因进行互换。
⑥终止规则。本文采取设置最大迭代次数的方式作为改进遗传算法的终止条件。
3.2.3 求解结果
设置种群数量为100，最大迭代次数为100代，交叉概率为0.9，变异概率为0.1，利用上述遗传算法的求解，最终计算得到适应度函数为2.1785543113589823e-05的优化方案，具体分组结果如表2所示的结果，算法收敛曲线图如图2所示。
4 总结
本文成功对汽车组装车间背景下物料配送的相关问题进行了数学建模，并设计了以遗传算法对模型进行求解。对于模型的求解本文设计了高效的遗传算法用以求解模型，在交叉操作的设计上，成功规避了个体基因的重复，同时对于软硬约束的处理通过“罚值”得到了有效的控制，使得模型的有效性和健壮性得到了极大的增强。
参考文献：
[1]吴亮亮，蔡红霞，朱政.汽车零件制造企业物料配送模式优化[J].工业控制计算机，2020，33（02）：124-125.
[2]李晋航.混流制造车间物料配送调度优化研究[D].华中科技大学，2012.
[3]李永林，叶春明，刘长平.轮盘赌选择自适应和声搜索算法[J].计算机应用研究，2014，31（06）：1665-1668.