﻿ 物料配送与线边存储集成决策模型与算法
 文章快速检索 高级检索
 浙江大学学报(工学版)  2018, Vol. 52 Issue (7): 1354-1363  DOI:10.3785/j.issn.1008-973X.2018.07.016 0

### 引用本文 [复制中英文]

dx.doi.org/10.3785/j.issn.1008-973X.2018.07.016
[复制中文]
LU Zhi-qiang, HU Xin-ming, DU Xin. Integrated modeling and algorithm of material delivery and line-side storage problem[J]. Journal of Zhejiang University(Engineering Science), 2018, 52(7): 1354-1363.
dx.doi.org/10.3785/j.issn.1008-973X.2018.07.016
[复制英文]

### 文章历史

Integrated modeling and algorithm of material delivery and line-side storage problem
LU Zhi-qiang , HU Xin-ming , DU Xin
School of Mechanical Engineering, Tongji University, Shanghai 201804, China
Abstract: The material supply process was abstracted as an integrated optimization problem of material delivery and line-side storage by taking the material supply for aircraft moving assembly line as the application background. Joint decisions were made for two sub-problems of material delivery and line-side storage in the conditions where the line-side space is shareable and reusable. An integrated optimization mathematical model was established to minimize the number of deliveries. A hybrid heuristic based on ant colony optimization (HACO) was proposed to solve the model. The core mechanism of HACO was to seek the optimized composition of material batches by the global searching capability of ant colony optimization algorithm. A batch-based solution generating algorithm was adopted to jointly make decisions on delivery time and storage positions at the line-side space for each material. A repairing algorithm was embedded in the decoding process to re-optimize the storage scheme of materials in order to further enhance the quality and the success rate of solutions. The effectiveness of the model and algorithm was verified through numerical experiments.
Key words: material delivery    line-side storage    integrated decision-making    solution generating algorithm    repairing algorithm

1 问题描述及数学模型 1.1 问题描述及问题假设

 图 1 飞机移动装配线物料供给示意图 Fig. 1 Schematic diagram of material supply mode for aircraft moving assembly lines

1) 物料相关假设.

a) 飞机装配过程中所需的物料可以分为4类：通用标准件、大型结构件、装配件和自制件.通用标准件(如螺栓等)一般采用定期补货的方式供给；大型结构件(如发动机、机翼等)由于体积较大且形状不规则, 通常使用行车、叉车和机械臂等其他方式直接配送.本文研究问题中的物料主要指体积中等、种类复杂的装配件和自制件.

b) 任一作业所需物料通过齐套(kitting)方式提前装入一个(或多个)标准料箱中, 等待后续装载和配送.假设仓库的备件能力充足.

2) 配送相关假设.

a) 料箱通过多载量小车进行配送, 单辆小车一次可以配送多个作业所需物料.为了防止配送过程中出现物料混乱, 任一作业所需的全部物料由一辆小车一次配送完成.

b) 小车配送时间主要包括小车从仓库到装配线边的时间和物料的装卸时间, 小车在工位旁物料通道的移动时间可以忽略不计.

3) 线边空间相关假设.

a) 装配线边的存储区域用于存放提前送达和正在使用的物料.整个线边区域被划分为若干个规则的线边存储单元, 假设每个存储单元的空间容量是标准料箱大小的整数倍.

b) 物料送达线边时只能存放在作业装配工位附近的存储单元内.如图 1所示, 定义作业i装配点的绝对位置liM所对应的线边单元为物料中心存储单元.为了作业人员取料的方便, 要求作业i所需物料只能存放在该中心存储单元及左右各一个单元的范围内, 如图 1的阴影区域所示.为了使得线边存储整齐有序, 任一装配作业的所有料箱必须连续地摆放在同一个存储单元内, 不可跨单元摆放, 也不可离散摆放.

1.2 数学模型 1.2.1 符号定义

κ={k|k=1, 2, …, K}：多载量小车集合.装配车间内的小车数量为K.

$\Re$={r|r=1, 2, …, R}：每辆小车配送次数序号集合.每辆小车最多出行R次.

J={i|i=1, 2, …, N}：装配作业集合, 共有N项装配作业.

Δ={d|d=1, 2, …, D}：离散的时间点编号集合.

Λ={l|l=1, 2, …, L}：线边空间存储单元集合, 最大编号为L.

Γl={c|c=1, 2, …, Cl}：线边存储单元l中的存储位置集合, 最大编号为Cl.

(ai, bi), ∀iJ：装配作业i开始时间为ai, 结束时间为bi, ai, bi∈Δ.

mi, ∀iJ：装配作业i所需的物料量(下称物料i), 以料箱的数量为计数单位.

v：飞机在装配线上的移动速度, 其值等于单位时间内飞机移动过的线边存储单元数.

Q：多载量小车的运载能力上限.

(k, r), ∀kκ, r$\Re$：表示小车kr次配送.

T：小车从仓库到装配线边的单程耗时.

lirela, ∀iJ：装配作业i在飞机上相对于机尾的装配位置.

liMΛ, ∀iJ：作业i装配过程的中间时刻装配点在移动装配线上所处的绝对位置, 即对应物料i在线边空间的中心存储单元.

1.2.2 决策变量和辅助变量

xikr∈{0, 1}, ∀iJ, kκ, r$\Re$：若物料i由小车k在第r次配送, xikr=1, 否则xikr=0.

skrΔ, ∀kκ, r$\Re$：小车kr次配送的出行时刻.若该次不配送任何物料, 则skr无意义.

(di0, li0, ci0), ∀iJ：分别表示物料i送达线边的时刻、被安排存储的线边单元编号和在线边单元内存储的最小位置编号.

λkr∈{0, 1}, ∀kκ, r$\Re$：小车k的第r次配送是否发车.若此次配送小车没有被分配任何作业的物料, 则小车此次不发车, λkr=0；否则λkr=1.

siΔ, ∀iJ：物料i的配送时刻.

1.2.3 目标函数和约束条件

 $\min \sum\limits_{k \in \kappa } {\sum\limits_{r \in \Re } {{\lambda _{kr}}} } .$ (1.1)

1) 辅助约束.若小车k的第r次配送决策没有配送任何物料, 小车不发车；否则小车发车：

 ${\lambda _{kr}} = \left\{ \begin{array}{l} 1,\;\;\;\;\;\sum\limits_{i \in J} {x_i^{kr}} \ge 1;\\ 0,\;\;\;\;\;\sum\limits_{i \in J} {x_i^{kr}} = 0. \end{array} \right.$ (1.2)

 ${s_i} = {s_{kr}};\;\;\;\;{\rm{s}}.\;{\rm{t}}.\;\;x_i^{kr} = 1.$ (1.3)

 $d_i^0 = {s_i} + T;\;\;\;\;i \in J.$ (1.4)

2) 配送问题相关约束.任一装配作业所需的物料必须由一辆小车一次配送完成：

 $\sum\limits_{k \in \kappa } {\sum\limits_{r \in \Re } {x_i^{kr}} } = 1;\;\;\;i \in J.$ (1.5)

 $\sum\limits_{i \in J} {x_i^{kr}{m_i}} \le Q;\;\;\;k \in \kappa ,r \in \Re .$ (1.6)

 $\left. \begin{array}{l} {s_{k,r + 1}} - {s_{k,r}} \ge 2T + {T^{{\rm{Load}}}};\\ {\rm{s}}.\;{\rm{t}}.\;\;{\lambda _{kr}} = 1,k \in \kappa ,r \in \Re \backslash \left\{ R \right\}. \end{array} \right\}$ (1.7)

 ${s_i} + T \le {a_i};\;\;\;i \in J.$ (1.8)

3) 物料存储问题相关约束.计算各装配作业相应物料的中心存储单元编号：

 $l_i^{\rm{M}} = l_i^{{\rm{rela}}} + \frac{{{a_i} + {b_i}}}{2}v;\;\;\;\;i \in J.$ (1.9)

 $\left| {l_i^0 - l_i^{\rm{M}}} \right| \le 1;\;\;\;\;i \in J.$ (1.10)

 $c_i^0 + {m_i} - 1 \le {C_i};\;\;\;i \in J.$ (1.11)

 $\begin{array}{*{20}{c}} {{b_i} < d_j^0 \vee {b_j} < d_i^0 \vee l_i^0 \ne l_j^0 \vee \left( {c_i^0 + {m_i} - 1} \right) < }\\ {c_j^0 \vee \left( {c_j^0 + {m_j} - 1} \right) < c_i^0;{\rm{s}}.\;{\rm{t}}.\;i,j \in J,i \ne j.} \end{array}$ (1.12)
2 算法设计

2.1 蚁群算法框架

 图 2 物料组批方式编码示意图 Fig. 2 Coding schematic diagram of material batching

 图 3 蚁群算法框架 Fig. 3 Ant colony algorithm framework
2.2 基于物料批次划分的解生成算法 2.2.1 批次配送顺序和配送时间决策(算法Ⅰ)

1) 为已组批完成的物料确定配送顺序, 将各个批次的物料按照最晚送达时刻升序排列：

 $\left. \begin{array}{l} {\rm{Batch}} = \left\{ {\left( {{B_1},a_1^{\rm{B}}} \right),\left( {{B_2},a_2^{\rm{B}}} \right), \cdots ,\left( {{B_F},a_F^{\rm{B}}} \right)} \right\};\\ a_f^{\rm{B}} = \min \left\{ {{a_i}\left| {i \in f} \right.} \right\}. \end{array} \right\}$

2) 初始化各小车最晚可用时刻TkLA, ∀kκ, 初始化f=F.

3) 更新最晚小车可用时刻

 $T_\kappa ^{{\rm{LA}}} = \max \left\{ {T_k^{{\rm{LA}}}\left| {\forall k \in \kappa } \right.} \right\}.$

4) 计算批次f物料的配送时刻Tf=min {TkLA, afB}, 记批次f物料的配送时刻与车次为Tf, k.

5) 更新小车k最晚可用时刻

 $T_k^{{\rm{LA}}} = {T_{f,k}} - 2T - {T^{{\rm{Load}}}}.$

6) 若f>1, 则f=f-1并返回4)；否则输出各批次物料配送时刻序列Tf=1, 2, …, F, 算法结束.

 $T_f^{{\rm{LA}}} = \min \left\{ {\max \left\{ {T_{f,k}^{{\rm{LA}}}\left| {\forall k} \right.} \right\},a_f^{\rm{B}}} \right\},$ (2.1)
 $T_{f,k}^{{\rm{LPA}}} = \min \left\{ {T_{f,k}^{{\rm{LA}}},a_{f + 1}^{\rm{A}}} \right\},$ (2.2)
 $a_f^{\rm{A}} \le T_{f,k}^{{\rm{LPA}}}.$ (2.3)

2.2.2 线边空间摆放位置决策(算法Ⅱ)

 图 4 线边物料存储示意图 Fig. 4 Schematic diagram of line-side material storage

1) 输入各物料配送时刻序列, 初始化无法存放的物料集合Ω=∅.

2) 依次按下列子优先级从高到底对物料进行优先级排序.a)按物料送达线边的时间di0从小到大排序；b)按作业装配点对应的中心存储单元编号liM从小到大排序；c)按物料体积mi(bi-di0+1)从小到大排序.

3) 若|U|=0, 则转6)；否则转4).

4) 选择U中优先级最高的物料i, 将物料i按以下规则放入线边空间中.a)线边单元编号尽量小；b)占据的位置尽可能低(ci0尽可能小).

5) 若物料在中心存储单元liM及左右一格范围内无法找到不发生空间冲突的摆放位置, 则Ω=Ω+i.更新集合UI, 返回3).

6) 若|Ω|=0, 则存在可行解, 否则不存在可行解.

7) 输出物料在线边的存储方案I, 算法结束.

2.3 物料存储修复算法(算法Ⅲ)

 图 5 物料存储修复算法优化机理 Fig. 5 Optimization mechanism of material storagerepairing algorithm

1) 从无法存放的物料集合Ω中随机选出一个物料i, 初始化当前迭代次数为0.

2) 在物料i允许存放的线边单元{liM-1, liM, liM+1}中随机选出一个, 设其为li0.

3) 从方向集合{ascending, descending}中随机选出一个方向, 依据该方向在bi时刻的线边单元li0内寻找第一个空置的料箱位置ci.

a) 当方向为“ascending”时, 物料占用线边单元内的最小位置编号为ci0=min{ci, Cli0-mi+1}；若无法找到足够的空间存储, 令ci=1.

b) 当方向为“descending”时, 物料占用线边单元内的最小位置编号为ci0=max{ci-mi+1, 1}；若无法找到足够的空间存储, 则令ci=Cli0-mi+1.

4) 将物料i放入线边单元li0中, 摆放在[ci0, ci0+mi-1]料箱位置, 检查是否与原摆放方案中的物料发生空间冲突；将发生冲突的物料集合Ω′取出, 并入Ω中.

5) 设新摆放方案为I′, 更新后的冲突集合为Ω=(Ω\{i})∪Ω′.

6) 若|Ω|=0, 则转8)；若|Ω|≠0且迭代次数达到上限, 则转7);否则转1).

7) 修复算法失败, 不存在可行解.

8) 输出物料在线边的存储方案I′或不可行解, 算法结束.

3 数值实验 3.1 算例集的构建

 ${\rho _l} = \frac{{\sum\limits_{i \in {\mathit{\Pi }_l}} {{m_i}} }}{{3{C_l}}}.$ (3.1)

 ${\rm{LAD}} = \sum\limits_{l \in \mathit{\Lambda }} {\rho _l^2} /L.$ (3.2)

3.2 与CPLEX求解性能对比

 图 6 HACO与CPLEX求解结果对比 Fig. 6 Comparison results of HACO and CPLEX
 ${G_{\rm{L}}} = \frac{{{R_{{\rm{HACO}}}} - R_{{\rm{CPLEX}}}^{\rm{L}}}}{{R_{{\rm{CPLEX}}}^{\rm{L}}}} \times 100\% ,$
 ${G_{\rm{U}}} = \frac{{R_{{\rm{CPLEX}}}^{\rm{U}} - {R_{{\rm{HACO}}}}}}{{{R_{{\rm{HACO}}}}}} \times 100\% .$

3.3 与其他算法的对比

 图 7 全算例集下不同算法结果对比 Fig. 7 Comparison of experimental results of example set between different algorithms

4 结论

(1) 以飞机移动装配线为应用背景, 对物料配送问题和线边存储问题进行集成优化, 建立集成决策的数学模型, 为物料配送问题在诸如飞机这类大型工业品装配的应用上拓宽了思路.

(2) 设计基于蚁群算法的混合启发式算法求解模型.该算法将物料配送时刻与线边存储位置决策统一到一个联合决策框架下, 可以有效地利用线边空间的存储能力, 减少小车配送次数.

(3) 基于蚁群算法的混合启发式算法在求解小规模问题时优势不明显, 但在诸如飞机这类作业规模较大的大型工业品装配物料供给问题的应用上具有较高的求解效率和较好的求解性能.该算法具有较好的通用性, 适用于工业中其他享有类似IMDLSP问题特性的物料供给问题.

(4) 今后的研究将针对当前算法在物料组批决策中的性质进行分析, 进一步提高算法的求解性能.此外, 为了进一步适应生产实际的需求, 后续将分析飞机移动装配中存在的不确定性因素, 建立动态决策框架, 为IMDLSP问题提供更有效的决策.

 [1] CAI H X, MING Y D, TAO Yu. Material coding for aircraft manufacturing industry[J]. Journal of Aerospace Technology and Management, 2014, 6(2): 183-191. DOI:10.5028/jatm.v6i2.315 [2] MEI Z, LIU Y, YOUNUS M. Material delivery system for aircraft composite component manufacturing workshop[C]//Proceedings of the International Multi-Conference of Engineers and Computer Scientists. Hongkong: Springer, 2011: 1097-1102. http://www.oalib.com/paper/2162253 [3] DONG J, ZHANG L, XIAO T. Part supply method for mixed-model assembly lines with decentralized supermarkets[J]. Tsinghua Science and Technology, 2016, 21(4): 426-434. DOI:10.1109/TST.2016.7536720 [4] CHEN C, XIA B, ZHOU B H, et al. A reinforcement learning based approach for a multiple-load carrier scheduling problem[J]. Journal of Intelligent Manufacturing, 2015, 26(6): 1233-1245. DOI:10.1007/s10845-013-0852-9 [5] 周炳海, 彭涛. 混流装配生产线准时化物料补给调度方法[J]. 控制与决策, 2017, 32(6): 976-982. ZHOU Bing-hai, PENG Tao. Scheduling methods of just-in-time material replenishment inmixed-model assembly lines[J]. Control and Decision, 2017, 32(6): 976-982. [6] EMDE S. Scheduling the replenishment of just-in-time supermarkets in assembly plants[J]. Or Spectrum, 2017, 39(1): 321-345. DOI:10.1007/s00291-016-0455-x [7] LIU M, ZHANG F, MA Y, et al. Evacuation path optimization based on quantum ant colony algorithm[J]. Advanced Engineering Informatics, 2016, 30(3): 259-267. DOI:10.1016/j.aei.2016.04.005 [8] SUN Y, DONG W, CHEN Y. An Improved routing algorithm based on ant colony optimization in wireless sensor networks[J]. IEEE Communications Letters, 2017, 21(6): 1317-1320. DOI:10.1109/LCOMM.2017.2672959 [9] SPERANSKII D V. Ant colony optimization algorithms for digital device diagnostics[J]. Automatic Control and Computer Sciences, 2015, 49(2): 82-87. DOI:10.3103/S0146411615020078 [10] LU C, YANG Z. Integrated assembly sequence planning and assembly line balancing with ant colony optimization approach[J]. International Journal of Advanced Manufacturing Technology, 2016, 83(1): 243-256. [11] MARTELLO S, PISINGER D, VIGO D. The three-dimensional bin packing problem[J]. Operations Research, 2000, 48(2): 256-267. DOI:10.1287/opre.48.2.256.12386 [12] TAYLOR G S, CHAN Y, RASOOL G. A three-dimensional bin-packing model:exact multicriteria solution and computational complexity[J]. Annals of Operations Research, 2017, 251(1): 397-427. [13] TOFFOLO T A M, ESPRIT E, WAUTERS T, et al. A two-dimensional heuristic decomposition approach to a three-dimensional multiple container loading problem[J]. European Journal of Operational Research, 2016, 257(2): 526-538. [14] VIEGAS J L, VIEIRA S M, HENRIQUES E M P, et al. Heuristics for three-dimensional steel cutting with usable leftovers considering large time periods[J]. European Journal of Industrial Engineering, 2016, 10(4): 431-454. DOI:10.1504/EJIE.2016.078141 [15] KANG K, MOON I, WANG H. A hybrid genetic algorithm with a new packing strategy for the three-dimensional bin packing problem[J]. Applied Mathematics and Computation, 2012, 219(3): 1287-1299. DOI:10.1016/j.amc.2012.07.036 [16] FENG X, MOON I, SHIN J. Hybrid genetic algorithms for the three-dimensional multiple container packing problem[J]. Flexible Services and Manufacturing Journal, 2013, 27(2): 1-27.