三阶段启发式算法在物料准时化配送中的理论研究

宋俊①② SONG Jun；孙小明① SUN Xiao-ming

（①上海交通大学机械与动力工程学院，上海 200240；②赛默飞世尔（苏州）仪器有限公司，苏州 215129）

摘要：为了实现物料的准时化配送，我们需要求出最小的生产周期，满足生产周期的物料配送时间小于生产周期。具体的求解思路为，首先将生产班次分为若干相等的生产周期.然后求出每个生产周期物料配送的最小时间。如果每个生产周期的物料配送时间都小于生产周期，进一步缩短生产周期，然后重新求出每个生产周期的物料配送时间,直至生产周期的最小化。

教育期刊网 http://www.jyqkw.com
关键词 ：准时化；物料配送；三阶段启发式

中图分类号：F259.22 文献标识码：A 文章编号：1006-4311（2015）24-0224-03

作者简介：宋俊（1981-），男，江苏高邮人，高级工程师，研究方向为物流工程。

0 引言

准时化（Just-in-time，JIT）的概念是在需要的时候生产合适数量的所需的产品。这种生产方式可以降低库存，提高生产效率从而降低生产成本。随着市场客户需求的多样化，多品种小批量生产的重要性越来越显得重要，对于多品种小批量的企业，准时化配送物料更有利于这种模式生产。准时化生产其核心就是消除流程和作业过程中的浪费来提升企业的作业水平，使每个运作流程更有效率的运行。

很多国内外学者对生产物料配送进行了大量的研究。其中蒋丽[1]等提出的以工位为中心进行存储和配送。中心思想是将每个工位所需的物料进行集中存放，而不是按物料类别进行仓库集中存储，这种配送方式能减少物料到使用工位的配送时间。李晋航[2]等提出在不确定条件下，对物料配送系统的研究。包括不确定的工位物料需求量、不确定的车辆配送时间以及不确定的工位预约时间。设计多模糊约束条件的数学模型，运用改善的遗传算法来求解。程卓[3]对总装车间物料配送研究。重点解决装配线边库存的补充问题和优化车辆调度的问题。通过二阶段法来解决上述二个子问题，最终完成线边库存补充计划和车辆配送计划。

1 背景介绍

TFS公司装配线线边库存堆积、缺料、原材料或零部件不合格时无法及时的更换或退给仓库。装配线的高效率与低效率混乱的物料配送之间的矛盾，极大影响了生产效率。只有保证物流准确、及时、合理的方式达到生产节点，才能保证企业的生产物流流畅，进而提高企业生产线的效率，因此必须确保物料的准时配送。

2 准时化物料配送方法的基本思路

问题的数学描述为：①根据生产计划的产品型号和数量，以及产品本身固定的物料清单可以确定每生产班次所需要的物料种类和数量；又由于每个生产线的工位是确定的，所以可知道每个班次每个工位所需要的物料种类和数量。②为了简化配送和数量统计，我们标准化存储的容器，把每个班次的每个工位的物料需求量以标准容器为单位进行换算。③生产组装工位所需要的物料都是由TFS仓库派车进行配送，而且把配送车辆的容量以标准存储容器为单位计量。

假设：a.工厂生产装配有q个工位；b.设定每个班次的生产时间为T；c.一个工位每个生产周期需要的物料数量是sij；d.每个工位所需要的物料数量为Pi个标准化容器；e.有M辆相同容量的配送车；f.每辆车有W个标准容器装载容量。

准时化配送目标设定为：每个生产班次划分为n个相等的生产周期，生产周期所需要的物料必须在每个生产周期开始之前配送到每个工位。需要满足约束条件为：

式（1）表示： n个相同的生产周期组成一个生产班次，每个生产周期为ΔT。

式（2）表示：一个工位一个生产班次所需要的物料分到n个生产周期内进行分别配送。

假设第j个生产周期内车辆m（m=1，2，…M）完成指定工位的物料配送时间为Tjm（包含物料的装卸和行驶时间），在此生产周期内完成所有工位物料配送所需要的时间取车辆中最大配送时间Tjmax=max{Tj1，Tj2，Tj3，…TjM，}。

为了能够实现物料配送准时化的目标，核心问题就是确保每个生产周期的物料配送时间不大于生产周期的时间即ΔT≥Tjmax。

由于线边空间有限，不能放置过多的物料。为了降低线边物料库存量，我们要尽可能降低每个生产周期的物料数量，所以最小化生产周期是我们所希望看到的。为了实现最小化生产周期ΔT，就得在生产周期ΔT下使Tjmax最小化，因此我们要每辆车的物料配送时间最小，要得到最小配送时间，就得合理分配车辆的配送工位，规划好配送车辆的行车路线。

3 配送规则

如何将物料在正确的时间送到装配线，使得装配线不缺料，不堆积料。为了实现物料准时化配送的目标，基于方便问题的研究和求解，我们对现实的问题进行了简化，从而制定了配送的规则。

规则1：提前给生产线和仓库生产计划。规则2：每个班次所需要的物料是分多次进行配送。规则3：配送开始时，配送车辆都从起点仓库出发。规则4：车辆从仓库出发配送到产线，从产线配送结束后再回到仓库表示一个配送循环结束。规则5：在第j-1个生产周期开始时进行配送第j个生产周期内工位所需要的全部物料，到第j-1个生产周期结束前完成配送。在第一个生产周期内，在每天开始前开始配送工位所需要的物料并在生产开始前完成配送。规则6：一辆容量为W的车一次不能配送完第j个生产周期内工位i所需要的物料总量sij，则需要把该工位的物料配送分为整车配送和非整车配送。整车配送就是装满一辆车的物料进行配送，反之就是非整车配送，非整车配送的物料可以和其他工位物料进行配送。规则7：配送车辆以速度v进行匀速行驶。规则8：每单位物料装车时间为t。规则9：每单位卸车时间为t。

4 求解策略

我们需要求出最小的生产周期，满足生产周期的物料配送时间小于生产周期。具体的求解思路为：①将生产班次分为若干相等的生产周期。②求出每个生产周期物料配送的最小时间。③如果每个生产周期的物料配送时间都小于生产周期，返回1步骤，将生产班次分为更小的生产周期，继续计算每个生产周期物料配送时间。

关键是计算出每个生产周期的最小物料配送时间。我们重点研究三阶段启发式算法求解最小物料配送时间。

5 三阶段启发式算法设计以及数学模型

第一阶段车次最少的派车决策。以车次数最小化为目标函数。第二阶段任务是对第一阶段的车次行驶路线进行优化。使每个车次的行驶时间最小化作为第二个阶段的目标函数。第三阶段将配送时间作为输入，主要任务就是把车次指派给配送车辆。本阶段是以最小化每个生产周期车辆的最大物料配送时间（Tjmax）为目标函数，并规划出每辆车所配送的车次。

5.1 第一阶段：车次数最小的派车决策 本阶段任务是计算每个生产周期物料配送需要的最少车次数，具体步骤为：

步骤1：计算每个生产周期每个工位所需要的物料数量

由于生产计划确定，根据产品装配的流程图确定每个工位需要什么物料，再参考物料清单可以确定每个工位所需物料数量。当生产周期确定后，根据生产节拍，计算出每个生产周期每个工位所需要的物料总量sij。

步骤2：计算每个生产周期工位所需要的整车配送次数

如果一辆车的最大容量无法配送完某一个生产周期内某一个工位所需要的物料数量时，我们就需要把工位所需要的物料分成两个部分：整车配送和非整车配送。计算公式为：

式（3）表示右边表示向下取整，其表示为第j个生产周期第i个工位需要的整车配送次数。式（4）表示第j个生产周期所有工位需要的整车配送次数总和。

步骤3：计算每个工位非整车部分配送的物料数量

如果一辆车的容量不能满足该工位物料配送的需求量，我们将该工位的需求量配送分为整车部分的配送和非整车部分的配送。非整车部分配送的物料数量等于每个工位的一个生产周期物料总需求量减去该工位此生产周期内整车配送的物料需求量，公式如下：

步骤4：计算一个生产周期内所有工位非整车部分的物料配送需要的最少车次数。目标函数是最小化工位非整车部分的物料配送车次数。

式（6）表示完成第j个生产周期所有工位的非整车部分的物料配送需要的最小车次数。式（7）表示为第j个生产周期工位i非整车部分的物料只需要一个车次配送。式（8）表示第j个生产周期一个车次配送的非整车部分的物料不大于车的容量。

③模型求解

输出的是完成每个生产周期内所有工位非整车部分的物料配送所需要的最小车次数以及每个车次配送的具体工位。

步骤5：计算一个生产周期的物料配送所需要的最少车次数

一个生产周期的物料配送需要的最小车次数即步骤2和步骤4车次数之和，计算公式为：

Zj=Bj+Qj （j=1，2，…，n）（9）

5.2 第二阶段：车次配送时间的最优化 车次的配送时间包含车辆的行驶时间和物料的装卸时间。

5.2.1 整车配送车次的配送时间 一方面，由于整车配送每车次只服务一个工位，而且车次的行驶时间是从仓库到工位，工位再到仓库往返一次的时间，这个时间是确定的。另一方面，每辆车的装载容量是一定的，所以车次配送的物料量就是等于车容量，结果是物料的装卸时间也是确定的。行驶时间和装卸时间都是确定的，因此整车配送车次的配送时间是确定的，也就不需要进行优化。

5.2.2 非整车配送车次的配送时间 对于非整车配送车次，一个车次需要配送多个工位物料。由第一阶段的输出可确定非整车部分物料配送的每个车次所配送的工位和每个工位非整车部分物料的数量，根据车的容量可以计算出每个车次物料的装卸时间，然后对车次的行驶路线进行优化得到每个车次的最优配送时间，计算出最小的车辆行驶时间，再将装卸时间和车辆行驶时间求和就可知配送非整车部分物料的最优配送时间。

步骤1：整车配送车次的配送时间计算

由上分析建立如下整车配送时间的数学模型：

步骤2：计算车次配送非整车部分物料的配送时间

由第一阶段的输出可确定非整车部分物料配送的每个车次所配送的工位和每个工位非整车部分物料的数量，我们只需要对车次的行车路线进行优化，求出最优行车路线即可知道最小的车辆行驶时间，再结合物料的装卸时间，我们就可以计算出车次最优的配送时间。

如果一个车次要为r个工位配送非整车部分的物料，建立如下数学模型进行车次的配送时间计算：

①符号说明。

式（11）表示一个生产周期一个非整车部分物料配送车次的配送时间；式（12）和（13）表示约束的条件：每个工位非整车部分的物料只需要一个车次配送；式（14）是表示消除支路。

③模型求解。

计算出每个生产周期内每个车次配送物料需要的最小配送时间，并给出每个车次配送工位的顺序。

5.3 第三阶段：车辆车次指派 本阶段主要的任务就是要把车次指派给车辆。在这里我们条件约束为：首先，每个车次只被一辆车配送。其次，车辆的一个车次配送完成是从仓库出发再回到仓库。最后，由于每个生产周期物料的配送都是在生产开始前就配送完成的，所以对同一个生产周期内每辆车辆配送的先后顺序无要求。首先将每辆车完成所配送的车次所需要的配送时间计算出来，然后找出所有车辆配送的最大值时间。目标函数是最小化车辆配送时间的最大值。数学模型如下：

①符号说明。

Zj表示第j个生产周期完成物料配送所需要的总车次数；tλj表示第j个生产周期内第λ个车次所需要的配送时间；M表示配送车辆的数量；Tmj表示第j个生产周期内第m辆车完成所配送的车次需要的配送时间。

算式（15）是目标函数即车辆配送时间的最大值最小化。算式（16）表示每个生产周期一辆车完成一个车次物料的配送。算式（17）表示每个生产周期一辆车配送完指定工位后的总时间。

③模型求解。

我们将得到完成每个生产周期的物料配送需要的最小时间和每辆车所配送的车次先后顺序。

5.4 总结 三阶段启发式算法的原理是首先确定车次数最小派车，其次计算每个车次的最佳行车路线以及车次的最短配送时间，最后将车次指派给车辆以及车辆的配送时间。最大的车辆配送时间要小于生产周期。它核心思想就是从局部最优的角度来求解每个生产周期车辆物料配送时间。

由于线旁空间有限，线旁物料的储存量就会限制，那么就得降低每个生产周期的物料配送量，就要缩短生产周期的长度，重新设置生产周期长度，再运用三阶段启发式算法进行求解。目的是满足每个生产周期车辆的最大配送时间要小于生产周期的情况下，最小化生产周期，从而达到准时化物料配送。

教育期刊网 http://www.jyqkw.com
参考文献：

[1]蒋丽，丁斌，臧晓宁.以工位为中心的生产物流配送优化[J].计算机集成制造系统，2009，15（11）：2154-2159.

[2]李晋航，黄刚，贾艳.多模糊信息条件下的物料配送路径规划问题研究[J].机械工程学报，2011，47（1）：124-131.

[3]程卓.总装物料配送优化算法的研究与系统实现[D].沈阳工业大学，2006.