考虑时间窗和装载约束的装配线集成物流调度

吴倩云，谢乃明，邵雨婷

(南京航空航天大学 经济与管理学院，江苏 南京 211106)

0 引言

在设备自动化、生产智能化、需求个性化的趋势下，运用科学合理的技术手段，制定一种集成的车间物流调度方案，保证配送及时性和成本优化双重目标的要求，显得尤为必要。电动工具装配这类生产节奏快的流水线，开展集成物流调度需要重点考虑两方面：①对生产连续性至关重要的配送时间，流水线装配最关注的是在既定的时间物料能否送达，因而开展物流路线优化应当具有时间窗的特征；②配送效率，在规定的时间窗范围内，利用最少的配送车辆将物料送达显然提升效率，这便要考虑物料在配送车辆中的装载形式，以最大化利用车辆的装载能力。面向流水线物料需求，如何综合运用上述重要指标，制定完善的装配流水线物流调度方案从而降低车间物流配送成本是亟待解决的核心问题。

目前，在指定时间配送方面，学者们一般考虑在车辆路径问题中加入时间窗的约束[1]，且关于车间内部服务需求的物料配送研究主要面向汽车制造行业，针对此类中小型设备装配的研究较少。Yang等[2]研究了关于动态需求订单的改变和时间窗的车辆路径问题，并用多蚁群算法求解。严正峰等[3]对复杂机械装配车间的配送路径优化考虑了模糊软时间窗，因生产节拍变动会引起物料需求时间变化，构造了物料到达时间的模糊隶属度函数。王楠等[4]根据汽车总装线的特点，采用混合型时间窗规划车辆路径，并提出改进遗传算法求解且验证了其有效性。而最大化利用车辆的装载能力的问题可归结为对车辆的多容器装箱问题，以尽量减少发送的车辆数量[5]。这类问题学者们从三维装载约束和算法角度做了详细的研究。如Paquay[6]考虑了物品的稳定性，脆弱性，重量分布以及方向旋转，提出了混合整数线性程序求解。Mahvash等[7]基于列生成技术的启发式来解决二维、三维装箱问题。Paquay等[8]针对三维多箱装箱问题，将原始问题划分为更简单的子问题从而寻求好的可行解决方案。那日萨等[9]利用空间切割法对目标进行划分，在水平方向和竖直方向搜索能放入的最佳货物，使箱体空间利用率最大化。崔会芬[10]通过改进遗传算法解决了集装箱装箱问题。

以往的物流配送研究中，通常是将上述两类问题独立考虑的，本文研究的装配流水线集成物流调度问题，需同时考虑配送时间和配送效率两个因素，应当将上述装箱问题与路径优化问题两方面的研究相结合。目前,也有不少学者研究装箱和车辆路径的联合问题，但都着重于对此类联合问题的求解和算法开发，对于该联合问题的实际运用并未有过多阐述。王征等[11]在研究车辆路径问题的基础上，考虑了货物在车厢中不能重复放置、要有序装箱等约束，提出的文化基因算法能有效提高求解结果的质量。颜瑞等[12]研究了有多个车场的配送调度，并在解决车辆路径问题的基础上引入一种启发式装箱规则来判断所装物品与运输设备空间的匹配关系，从而提高装货效率。Zachariadis等[13]考虑到若要满足产品交付期和生产顺序约束，在路径规划的每一环节中都需确定可行的装载模式，于是提出一种基于记忆技术模型的优化框架。Dirk等[14]将三维装箱约束与取送货车辆路径问题结合并求解。Leonardo等[15]考虑了一般的装箱约束以及多个与货物垂直稳定性相关的限制，进行车辆路径规划研究。而对于该类联合问题的求解主要分为联合优化方法和多阶段优化[16-18]，前者是对两问题同时优化，后者是将求解过程分为独立的两个阶段。

综上所述，现有文献通常将物流配送划分为装箱和路径优化两个单独问题，忽略了配送路线和装载货物的联动特征，也有少量研究将装载问题与车辆路径两者结合，但主要考虑的是货物不可相互叠放的二维装箱情况，而已有文献中针对三维装箱与车辆路径联合问题的研究更着重于算法的求解，缺少物流配送的现实约束，如时间依赖型的物料配送约束等，无法满足装配线物流配送及时化与效率化的生产需求。因此，本文将物料装载约束与装配车间配送路径规划问题有机融合，结合装配流水线的动态需求时间窗信息，探讨了电动工具装配流水线集成物流调度方案，一是要确定各产线的物料料箱在配送车辆中的装载形式，二是要确定配送的路径和时间，这两个阶段存在先后关系并相互联系，共同影响着配送成本。本文考虑到装载形式的不同意味着车辆行驶的路线会因物料能否装载而改变，遂采用两阶段优化，即先进行装箱优化，再进行车辆路径规划，从而对该集成物流调度方案进行求解。

1 集成物流调度方案

目前电动工具装配车间内的物料配送仍采用传统的人工调度，为保证生产线不缺料而给每条生产线配备专门的配送人员和配送车辆，但实际操作中配送车辆的装载往往并不满载，且配送人员在物料充足的情况下处于闲置状态，造成了极大地浪费。

本文所研究的流水线物流配送不考虑装配车间与其他注塑车间的联动特征，主要从流水线线体本身的物料需求出发进行配送优化。由于线边库存的限制，物料通常采用循环配送，物料需求量相对较少，仍采用传统的每条产线都配备专门的配送人员和车辆的模式，则使得阶段内的需求物料对配送车辆的利用率不高，造成物力和人力的浪费。若将各产线在同一时间段配送的物料合并，将其装载在同一辆配送车上，一辆车装满再启用另一辆车，充分利用车辆的装载能力，则可减少不必要的配送车辆和人力配送，降低车辆的发车成本。且通常装配车间生产线附近设有部分区域作为物料超市，配送车辆需经历从物料超市到各需求产线的整个过程，通过有效的算法实现最优路径的配送可降低配送的运输成本。

因此，本文从配送时间和配送效率出发，提出了电动工具装配流水线集成物流调度方案，如图1所示，该方案的思路分为两层：第一层是三维装箱优化，即根据电动工具装配产线线体物料需求信息，利用配送车辆的装载能力寻找使车厢空间利用率最大的装箱方案，结合启发式思想并运用遗传算法实现装箱过程，生成装箱数量即为配送车辆数；第二层是物流路线规划，即根据电动工具生产的连续性特点，考虑时间窗配送约束，基于第一层最优装载约束的结果进行物料配送路线规划，以保证物料及时准确地送达。只有保证物料能被合理且最大限度放入车厢，再优化配送路径，才能使得规划的路线既合理又能使配送效率更高，从而得到理想的集成物流配送效果。

图2给出了一个简单的集成物流配送可行方案示意图，其中配料人员根据三维装箱模型优化的装载方案将物料装入2辆车，给4条产线配送，箭头方向表示每辆配送车辆访问产线的先后顺序。

1.1 三维装箱模型构建

本文首先利用三维装箱模型，考虑产线所需物料料箱在配送车厢中的装载形式，以便充分利用车辆的装载能力，此为集成物流调度方案的第一层。

1.1.1 三维装箱问题描述

在一个配送时段内，各产线物料需求信息已知，要将所需物料料箱装进容积和载重一定的车厢内等待配送，在一定条件下找出一种最佳装箱方案以装入尽可能多的物料料箱。

物料进行装车时，综合考虑以下条件：

(1)方向性约束(C1) 物料料箱顶部朝上放置，不能倒置和侧放，所有料箱的长、宽、高方向与车厢的3条中轴线平行。

(2)稳定性约束(C2) 料箱必须从底层开始放起，不能悬空。

(3)车厢最大载重量约束(C3) 车厢本身有最大载重量限制，装入车厢的产线所需物料总重不能超过这个限制。

(4)车厢最大容积约束(C4) 车厢本身有最大容积限制，已装载的料箱的总体积不能超过这个限制。

1.1.2 三维装箱问题模型

物料料箱可近似看成一个个尺寸、重量不同的长方体，要将这些长方体装入容积一定的车厢中需考虑物料料箱在配送车辆中的空间摆放形式，即长、宽、高三个维度的可放置区域。因此，建立笛卡尔坐标系用于处理车厢与料箱空间摆放形式，如图3所示，坐标轴X、Y、Z轴分别对应车厢的长、宽和高方向，坐标系的原点位于车厢内侧左后下角顶点，也是首个料箱左后下角摆放的位置顶点。

定义以下符号：

n为物料总数；

g为物料序号；

Rg为物料是否被装入车厢，若装入车厢则Rg=1，否则Rg=0；

vg为物料g的料箱体积；

V为配送车辆的车厢体积；

L，W，H，Q分别为车厢的长宽高及最大载重量；

lg，wg，hg，mg分别为物料g料箱的长、宽、高和重量；

(xg,yg,zg)为物料g的料箱装入车厢后左后下角的位置坐标；

本文以配送车厢的空间利用率最大为目标函数，构建了如下三维装箱模型：

(1)

y∈{0,1,…,W},z∈{0,1,…,H}；

(2)

y∈{0,1,…,W},z∈{0,1,…,H-1}；

(3)

(4)

(5)

zg+Rg·hg≤H,∀g∈{1,2,…,n}；

(6)

∀y∈{0,1,…,W},z∈{0,1,…,H},

g={1,2,…,n}；

(7)

∀x∈{0,1,…,L},z∈{0,1,…,H},

g={1,2,…,n}；

(8)

y∈{0,1,…,W},g={1,2,…,n}；

(9)

(10)

其中：式(1)为目标函数；约束(2)保证了两两料箱不会互相挤压、嵌入；约束(3)说明物料料箱从车厢底部开始摆放，不会悬空；约束(4)～约束(6)表示车厢X轴、Y轴、Z轴装箱长度约束；约束(7)～约束(9)表示料箱装入车厢后各位置方向约束；约束(10)为总重量限制。

1.2 基于装箱约束的电动工具装配流水线物流路线优化模型构建

通过上述三维装箱模型优化，即可确定配送的车辆数、每辆车上装载何种物料、每辆车需访问的产线序号等信息。通过路线优化模型即可确定在规定时间内每辆配送车辆要访问的产线先后顺序，此为集成物流调度的第二层。

1.2.1 电动工具装配流水线物流路线优化问题描述

设有一个配送中心0与n条产线，配送中心拥有完全相同的配送车，在一个配送时段内，根据产线物料需求三维装箱优化后，得到装箱车辆数m，即配送路径数。要求制定一个合适的配送车辆行驶路线方案，使得配送总成本最低。

在规划车辆行驶路径时，需满足以下条件：

(1)每辆车可负责多条产线的运输任务，但同一辆车只能对一条产线配送一次；

(2)每辆车从配送中心出发，完成配送任务后返回配送中心，即为一个配送循环；

(3)配送任务需在规定的产线服务时间内完成，早于或晚于该窗口到达都要接受相应的成本惩罚；

(4)车间留有专门的配送路径通道，车辆在行驶过程中，保持匀速行驶，不会遇到拥堵、故障等情况；

(5)路径规划中使用的配送车辆车型相同，且处于最佳运行状态，所有车辆遵循相同的燃油消耗率。

1.2.2 基于三维装箱约束的电动工具装配流水线物流路线优化模型

由于物料配送对到达产线的时间有严格的要求，若其所需物料过早到达，产线旁的线边库存没有足够的空间容纳新物料，造成等待成本的增加；若所需物料在生产物料消耗完后到达，则流水线生产因缺料中断，需要承担停工的代价。本文将车辆固定发车成本、运输变动成本和未按产线指定时间送达产生的惩罚成本这3项成本之和考虑为配送总成本，对每辆车的行驶路径进行规划。其中车辆固定发车成本只与车辆数有关，一般不受其他因素影响；装配车间的物料运输速度和道路相对平缓，仅考虑载重影响下的燃油消耗为运输变动成本。根据线性油耗模型，设运输的变动成本与运输量的关系为cij=b·(α·qijk+β·xijk)，其中：α为载重油耗系数；β为车辆净重油耗系数；b为油价；qijk为车辆k从产线i经过到产线j时的载重量；xijk为车辆k是否经过产线i到产线j，是0,1决策变量。

定义以下符号：

M为等待配送的运输工具数量，其具体取值由装箱模型生成的方案决定；

FC为单位发车成本；

dij为两条产线间的直线距离；

ce为早于时间窗的单位惩罚成本；

cl为晚于时间窗的单位惩罚成本；

tik为到达产线i的时刻；

[ei,li]为产线i的服务时间窗；

Qk为车辆k装箱后总重量；

Dik为产线i的需求重量。

目标为配送总成本最小，构建车辆路径问题数学模型表示如下：

(11)

k∈{1,2,…,m}。

(12)

(13)

∀i∈{1,2,…，n},k∈{1,2,…,m}。

(14)

tjk=tik+si+tijk,∀i,j∈{1,2,…,n},

k∈{1,2,…,m}。

(15)

(16)

其中：式(11)为目标函数；约束(12)表示能量守恒，每个产线到达和离开的车辆数相同；约束(13)表示每条路线上车辆从配送中心离开，完成任务后必须返回配送中心；约束(14)表示时间窗约束；约束(15)表示前产线和后产线服务时间的约束；约束(16)表示车辆载重平衡约束。

2 求解电动工具装配流水线集成物流配送问题

本文将物流配送集成调度分解为多约束三维装箱和物流路线规划两层，这两个问题均为大规模组合优化问题，可利用鲁棒性较强的全局优化自适应遗传算法，将数学模型转化为迭代算法进行求解。

2.1 算法流程图

本文设计了求解电动工具装配流水线集成物流调度的两阶段遗传算法。第一阶段根据一个配送时段内各产线的需求，通过装箱确定配送所需的装载车辆数、每辆配送车辆上装载的物料序号以及需要访问的产线；第二阶段根据装箱结果优化配送车辆的行驶路径和配送成本。算法流程如图4所示。

2.2 算法设计

第一阶段装箱算法主要策略如下：

(1)染色体编码 将车厢序号、料箱放置参考点以及放置空间的三维尺寸构成编码串，即染色体编码为(rg,xg,yg,zg,dl,dw,dh)，来表示问题的一个解，其中：rg表示物料料箱装入车厢所对应的车厢序号；(xg,yg,zg)表示可放置空间中料箱可以放置的左后下角坐标；dl,dw,dh分别表示料箱在该空间各维度上的尺寸，对于序号为g，三维尺寸分别为lg，wg，hg的箱子，其初始编码的形式为(g,0,0,0,lg,wg,hg)。

(2)初始化种群 因为车厢序号、料箱放置参考点以及放置空间的三维尺寸的编码形式均为自然数，所以种群初始解为随机产生的物料编号序列、可放置空间的坐标序列、放置方向序列，如此反复，直到满足种群数目。

(4)交叉算子 本文的交叉操作选用单点交叉，对物品所装车厢的编码串进行交叉。假设现有10个物品等待装入3个容器中，在染色体P1和P2中，随机选取一个交叉点如位置5，交换6、7、8、9、10号货物对应的容器序号，最后得到子代P1′和P2′，如图5所示。

(4)变异算子 本文采用基本位变异法，对物品所处容器序号进行变异分析。如现有5个箱子可以被选择用于装载，随机选择解中的一行数据，若选中了1号容器中的某货物，则对该货物所处容器序号进行变异操作，若容器数字由1变异成3，则将该货物装入3号箱子，于是就产生了一个新的解。

第二阶段路径优化算法主要策略如下：

(1)染色体构造 本文采用自然整数编码构造行驶路径染色体，单一配送中心非满载车辆路径问题的一条配送路径的染色体可编为(0,ik1,ik2,…,ikn,0)，其中ikn表示第k辆车的第ikn项任务。例如有10条产线，用0表示配送中心，对配送中心和产线依次编号0，1，2，…，10，0。现有一条染色体：0 4 7 9 3 6 10 2 5 8 1 0，为一次配送活动中第k辆车辆的行驶路径，染色体中相邻两个0之间的数字依次为第k辆车辆访问产线的顺序。

(2)种群初始化 现有n条产线，初始群体应尽可能地在所有可能路径中均匀分布，则在算法开始搜索之前，随机生成在1～n之间随机排列的个体，如此反复，直到达到种群规模数。

(3)选择算子 在对种群进行选择时选用轮盘赌法，适应度越高选中的概率越大。而本文是求配送成本最小，适应度函数取目标函数的倒数，使配送成本越小的染色体被选中的概率较大。

(4)交叉算子 本文的交叉算子采用部分匹配交叉方法，假设有10个产线，任意选择两个不完全相同的个体A和B，随机确定两个交叉点，并交换两交叉点之间包含的部分。交叉后，保留不重复的的部分，如果个体中有相同的产线数字则消除冲突，如图6所示。

(5)变异算子 变异运算的实质是染色体上处于相同位置的基因发生了突变，是另一种产生新个体的方法。假如种群中一个为(9 5 1 6 3 8 7 10 4 2)的个体，随机选取两个点7和4，对换其位置，则个体变异成(9 5 1 6 3 8 4 10 7 2)。

3 算例与结果分析

3.1 算法测试

为了验证本文所构建的模型与求解算法的有效性，将遗传算法(Genetic Algorithm, GA)与Gurobi求解器求解的结果进行对比。根据表1的数据物料需求B、料箱数G和配送点数量N，生成s-1～s-5共5个规模不同的算例，每个配送点的时间窗在一次配送时段内随机生成，配送点的物料需求量、料箱规格和数量以及物料重量在总量基础上随机生成，配送车辆采用长、宽、高分别为1.2 m，0.8 m和0.8 m的车厢尺寸，算例具有单一配送中心。算例中设置Gurobi运行时间上限为7 200 s，GA的参数设置为种群规模N=100，交叉概率pc=0.9，变异概率pm=0.05，最大进化次数为genmax=200，早到惩罚系数为10，晚到惩罚系数为100，固定发车成本为50。

运用软件Gurobi和MATLAB对不同规模的算例独立求解10次，取均值作为配送成本目标值。对比表1的结果，可以看出针对前几个规模中小的算例s-1～s-3，用GA算法求解的结果与Gurobi求得的最优解非常接近，其成本差距小于1%，但在求解时间上GA明显优于Gurobi。由于车辆路径与装载问题均为NP-hard问题，当问题规模较大时，如算例s-4和s-5，用Gurobi求解无法在短时间内获得最优值，而GA能较好地满足装配线集成物流配送的需求。因此本文所构建的模型与求解算法是有效的。

表1 不同规模问题下GA与Gurobi计算结果

3.2 实际案例分析

本文以南京D公司电动工具装配车间物料配送实际数据为背景，求解其最优配送方案。该公司电动工具装配车间拥有1个物料超市，10条生产不同产品的装配线需要配送服务，产线用序号1～10表示。配送车辆均为同一型号，可近似看成长、宽、高尺寸分别为1.2 m、0.8 m和0.8 m的箱体，限重为200 kg。选取某次配送活动内车间各产线所需物料标准料箱数据如表2所示，共有30种物料类型，67个料箱，各产线送料点坐标、需求量、时间窗约束、服务时间如表3所示。配送路径数根据装箱数确定，每辆配送车辆从物料超市出发访问各物料送达点最终回到物料超市，物料配送选择总成本最小的行车路线。

表2 各产线所需物料标准料箱数据

表3 装配车间产线需求数据

续表3

采用MATLAB编写代码实现遗传算法，算法参数及成本系数与前文算例设置的参数一致，运算10次后得到该算例的最佳装箱方案和访问顺序安排，即需要5辆配送车，最优配送成本约为879.4元，具体结果如表4所示。从计算结果可以看出，装箱结果与运输结果满足车厢装载约束以及产线的服务时间约束，每个车厢对应一条最优配送路径。由于使用Gurobi求解器计算此实际算例无法在电脑可用内存时间内获得最优值，本文将遗传算法求解的结果与模拟退火算法求解的结果进行比较。模拟退火参数设置如下：初始温度为1 000，终止温度为1，当前温度下的迭代次数为100，降温速率为0.9。经10次运行，两种算法目标函数最优值的求解情况如表5所示，用遗传算法求得的配送成本平均结果约为894.0元，略优于用模拟退火算法求得的配送成本平均结果914.2元，两者差距非常小，但用遗传算法的收敛速度较快，因而利用遗传算法可以有效地求解装配车间物料配送问题。与D公司装配车间原有配送方案相比，车间原配送方案装车数量完全依赖产线数，即每条产线配备固定的配送车辆及配送人员。在使用装车数最小的思想确定车辆路径数后，经过遗传算法优化后的装车数比原方案节省50%，配送成本节约23%，提高了配送效率，具有一定的实际应用价值。

表4 物料配送结果

表5 遗传算法与模拟退火算法求解情况对比

续表5

4 结束语

本文构建了电动工具装配流水线集成物流配送模型，通过对物料装车和配送路径两个层次的集成优化，达到物料配送及时准确的调度效果，实现装配车间物流配送总成本最低的目标。

本文的主要贡献在于：①面向物料装车的多种约束构建了三维装箱模型，面向产线需求的物料配送构建了考虑时间窗的物流路线规划模型，为集成物流调度优化提供了数学模型的支撑；②基于遗传算法设计了求解最优装箱和最优路径的两阶段迭代算法，从而形成集成物流调度方案；③基于Gurobi、GA的算例仿真验证了模型和算法的有效性，通过南京D企业电动工具装配产线实际案例，给出了详细的集成物流配送方案，能有效提高车辆的装载利用率，降低集成物流配送成本。本文提出的集成物流调度方案不仅对电动工具企业有实际应用价值，对其他打印机类、吸尘设备类、五金类制造等诸多行业的车间物流调度亦同样具有借鉴和参考意义。

本文主要考虑了正常生产状态下的物流配送，对于紧急插单等配送情景还可作进一步的探讨。且本文所依托的案例背景主要采用的是企业普遍存在的几十到上百种配送物料规模，对于上千种大规模物料配送的研究有待进一步验证。