基于改进蚁群算法的时间窗车辆配送路径优化研究

吕再生，樊 航，董宝力，贾江鸣

(浙江理工大学 机械与自动控制学院，浙江 杭州 310018)

整车制造企业通常采用传统型多品种、小批量的混流生产模式.其复杂的工艺特性和繁多的零部件种类导致其物流配送要求极为严格，生产物流同步是其追求的终极目标，同时一直是国内外学者关注的重点.

张资渊探讨了看板、配套、顺序等各种补货方法的优势和劣势，通过建立零部件层级成本计算模型，提出了用成本决定最优补货方法的策略[1].洪旭东等提出了基于看板的生产线物料循环配送方式，通过优化看板数量、循环周期等参数提升了配送的及时性和准确性[2].李伟等针对汽车总装线边空箱拉动供料模式下的物料配送问题，以配送路径最短和配送路线需求点配送频次均衡化为目标，建立了空箱拉动模式零件配送路径优化模型[3-4].Banos R等基于平行多目标模拟退火遗传算法解决带时间窗的车辆调度问题时，通过最大限度地减少车辆的行驶距离和线路不合理多目标约束构建了模型[5].张小龙等构建目标联运路径优化模型时，引入了混合时间窗概念，并利用基于Pareto适应度的遗传算法，求解了一个多式联运的算例[6-7].尚文利等提出了基于射频识别技术RFID(Radio Frequency Identification)的车辆追踪和基于条码的无线物料库存管理方法，并设计了装配生产线的物料动态配送调度业务流程[8].党立伟等根据制造BOM(Bill of Material)和装配工艺流程，求出了最优配送周期和每次配送量[9].丁佳祺等以成本最小为目标，考虑线边库存容量和牵引车最大运输量约束，确定了最优循环周期和看板数量[10].

物料配送的相关研究大多集中于传统的纸质看板环境下通过手工输入信息，获取零件看板，且主要通过优化看板数量及配送频次，或者改变配送方式来提升零件配送效率.传统的被动式配送服务存在如下缺陷：①看板卡片容易丢失，线边拉动需求往往无法及时传递至配料区；②容易受配送人员主观因素的影响，导致线边零件短缺或溢库；③内、外部物流信息无法及时有效共享.因此，本文将条码、RFID、信息集成等技术用于汽车总装生产线，通过获取汽车总装生产线的零件电子看板信息，对其内部配送路径进行带时间窗约束的路径规划，实现小批量、多频次的零部件物流供应，使生产线边的库存最小化，达到厂内外物流信息共享，实现生产物流的同步.

1 电子看板环境下的零件同步物流配送系统

电子看板是将信息技术应用于生产可视化的一种工具，它避免了传统实物看板模式下信息在传递过程中产生的丢失、涂改和损坏现象，同时增强了信息传递的及时性和可靠性[11].

电子看板环境下的零件配送过程主要包括零件信息收集、拣配单生成、拣配、配送后回到仓库.其具体业务流程如图1所示.在生产线上，通过RFID技术可识别每个车身的车辆识别号码(Vehicle Identification Number,VIN).当车身经过设定的扫描站点时，零件同步物流配送系统向车体自动识别系统(Automatic Vehicle Identification System,AVI)发送车体到位信号，触发RFID天线进行载码体的读写，将数据传输至制造执行系统(Manufacturing Execution System,MES)的相应模块，MES依据企业资源计划(Enterprise Resouce Planning,ERP)中的BOM信息，计算汽车总装生产线的零件供货指示信息.针对SPS(Set Parts System)零件，可自动生成拣配单，在SPS拣配区域拣配并等待车辆同步上线；供应商根据车辆上线顺序对JIS(Just In Sequence)零件进行排序配送，并按需要的时间配送至厂区；电子看板零件数达到系统设定的包装数量后，生成相应的零件拣配单.配送中心每隔一段时间处理并打印一次拣配单.拣配人员按照拣配单的要求对零件进行拣配并入库.当达到配送时间要求时，配送人员对零件进行配送服务并收取相应的空料箱，将空料箱置于指定区域并集中返回配送中心.

图1 基于电子看板的配送业务流程

2 基于时间窗电子看板零件配送的路径规划

2.1 设定电子看板零件时间窗

带时间窗车辆问题(Vehicle Routing Problem with Time Windows,VRPTW)是在传统的车辆路径问题上加上时间窗的约束.它通常可以分为硬时间窗、软时间窗和混合时间窗.本文研究的是混流装配线，对物料配送要求比较严格，一旦零件配送晚于装配线需求时间，将导致整条汽车总装生产线的停产，故采用硬时间窗类型.这里，零件配送要求最晚到达时间为：

LTims=ETims+TSi

(1)

式中：ETims为看板零件达到包装量后系统显示的最早需求时间；T为生产线节拍；Si为扫描站点与工位i之间的待装配车辆数量.

2.2 建立配送路径规划数学模型

本文在零件配送时间窗要求下，以配送总成本为目标函数，对配送路径进行具体优化，并给出如下假设：①配送小车从配送中心出发，最后返回配送中心；②配送小车的总配送量不允许超过其最大载荷，否则将受到额外惩罚；③允许配送小车提前对零件进行配送，但将产生提前配送成本；④每个工位所需零件只允许一辆配送小车为其服务.

基于时间窗约束的配送路径优化模型包括目标函数和约束条件两部分.其中目标函数由三部分组成.第一部分为小车的启动成本f1.

minf1=c1V

(2)

式中：c1为启动每辆配送小车的固定成本；V为配送周期内所需配送小车的数量.

第二部分为指定批次零件配送所需小车服务费用f2.

(3)

第三部分为零件ms在配送过程中提前配送至工位而产生的额外等待成本f3.

(4)

因此，目标函数为：

(5)

约束条件为：

(6)

(7)

配送小车均从物料超市出发，即：

(8)

配送小车完成物料配送后最终返回物料超市，即：

(9)

工位j所需零件ms来自工位i,即：

(10)

配送小车到达工位i的时间不能晚于工位i要求的最迟到达时间，即：

ms=1,2,…,M)

(11)

在零件ms配送过程中，每次配送量不能超过配送小车所能承受的最大载荷，即：

(12)

式中：Jims为零件ms每次配送至工位i的量；Q为配送小车所能承受的最大载荷.

3 改进蚁群算法的实现

蚁群算法是一种用来优化路径的概率型算法，属于启发式全局优化算法，适用于求解复杂的组合优化问题[12].在该算法中，蚂蚁通过判断信息素浓度来选择下一节点.信息素浓度越大，选择该节点的概率就越大，导致该条路径的信息素进一步增强，容易产生早熟、停滞现象.因此，本文对选择策略进行如下改进：当搜索陷入局部最优时，增大随机选择的概率，从而避免蚁群进入早熟、停滞现象.

2-opt(2-optimization)算法是基于“交换”的启发式思想，将一条路径转换为另一条路径，在给定可行路径中，只要能降低目标函数值，算法就会在选定集合内进行反复操作，直到产生局部最优路径为止.其原理是用(i，j)，(i+1，j+1)来替换(i，i+1),(j，j+1).如此变换后，路线中的路径(i+1，…，j)被反向处理，且交换后路径权值减小，即满足如下条件：

Ci j+Ci+1,j+1

(13)

2-opt交换算法如图2所示.

图2 2-opt交换算法

改进蚁群算法的实现步骤如下：

步骤1：初始化参数并设置计数器NC=0，把M只蚂蚁放置于配送中心，同时建立禁忌表，设定每条路径的初始信息素浓度τi j(0)，并找出全局初始解Lgb.

(14)

步骤3：确定节点i与节点j上总货物量sum_g并与小车所能承受的最大载荷Q进行比较.如果sum_g小于Q，则继续选择下一节点；否则将节点j加入禁忌表中，并跳转至步骤5.

步骤4：计算到达时间Tj.如果Tj满足节点的时间要求，就计算节点i到节点j的路径长度和费用，转至步骤2；否则进入下一步骤.

步骤5：计算配送小车的数量并判断allow表.若该表为空，则进入下一步骤；否则从该表中得到未经过的节点，并从各节点中选择开始时间最早的点，转入步骤2.在每只蚂蚁确定配送路径后进行局部搜索，并对部分更优的路径采用2-opt方法进行可行解的领域搜索.

步骤6：对每只蚂蚁所经过的路径进行局部信息素更新和信息素增量更新.当蚂蚁决定按照转移概率访问下一节点时，路径(i，j)上蚂蚁留下的信息素被更新为：

τi j(t+n)=(1-ρ)τi j(t)+Δτi j(t)

(15)

步骤7：求出M只蚂蚁搜索的最短路径和费用，并更新信息素.如果M只蚂蚁已全部走过一遍，那么更新蚂蚁搜索过节点的信息素；不然则更新本次循环的最好路径.

步骤8：记录本次路径长度Lopt与对应的路径表.本次最优路径Llocal与全局最优解Lgb进行比较，记录两者间最优解并更新最优路径表.

步骤9：判断计数器的值是否达到最大迭代次数.如果已经达到最大迭代次数，那么流程结束；否则，清空禁忌表，返回步骤2并重复操作.

4 实例验证

某总装生产线有20个工位需要进行零件配送.图3所示为其各需求点的分布状况.其各工位基本需求信息如表1所示.单元之间的标准配送时间如表2所示.假设配送小车的固定消耗成本为80元/辆，小车的最大容量为6 m3，单位距离运输成本为0.5元/m.蚁群的种群规模为50只，最大迭代次数为250，α=1.5，β=2，γ=0.9，小车超载的惩罚因子为10 000元，提前送至工位产生的单位时间等待成本为30元/min，延迟送至线边的成本为+∝.可采用Matlab软件求得最优方案.

图3 总装生产线各需求点的分布状况

序号零件名称包装量/个配送总容量/m3最早配送时间要求最晚配送时间要求卸货/装空架时间/min000102030405060708091011121314151617181920/前围内减震垫后保险杠左侧尾灯前地毯总成后挡风玻璃总成转向节带制动器真空助力器总成前顶灯总成油箱固定带仪表板横梁转向管柱中间轴总成散热器总成前门密封条总成动力转向器总成增压器输气软管天窗总成前副车架总成右前门锁总成左后轮眉总成后悬置支架总成右前脚踏垫/301015241830241218402850251271024401510/1.290.590.602.000.790.500.581.461.150.691.091.410.670.870.670.930.551.140.571.20016:00:1916:01:5416:02:3516:02:2316:02:0416:00:0116:02:3516:02:1816:03:1816:01:3316:02:0416:01:4916:03:4616:02:3516:00:1616:00:0016:03:1716:01:1416:01:3616:01:0416:15:0016:08:1916:09:5416:10:3516:10:2316:10:0416:08:0116:10:3516:10:1816:11:1816:09:3316:10:0416:09:4916:11:4616:10:3516:08:1616:08:0016:11:1716:09:1416:09:3616:09:0400.420.450.170.340.410.350.350.490.590.530.540.480.230.580.130.160.230.480.420.45

表2 单元之间的标准配送时间 min

用传统蚁群算法和改进蚁群算法对目标函数进行求解，可得图4所示的种群迭代进化图.对于此次求解过程，改进蚁群算法在迭代次数为95时曲线趋向收敛，比传统蚁群算法收敛得更快，得出的值更优.

针对配送路径问题，采用改进蚁群算法求解时路径信息如表3所示.改进蚁群算法与传统蚁群算法的路径优化结果如表4所示.

图4 蚁群算法的种群迭代进化图

配送路径配送子路径配送容量/m3路径行驶时间/min路径配送成本/元配送小车有效装载率/%路径10,12,20,11,18,14,05.71210.938 2294.495.2路径20,16,15,2,4,7,10,19,05.20311.669 9395.686.7路径30,1,6,9,5,3,8,05.79113.287 2265.396.5路径40,17,13,01.2217.228 893.920.3

表4 路径优化结果对比效果 元

从表4可知，针对每批次零件配送任务，改进蚁群算法比传统蚁群算法节省1辆配送小车，配送总成本降低了(1 525.930 8元-1 369.285 4元)，约156.6元.

5 结束语

本文主要研究了汽车总装车间的零件配送优化问题，分析了基于电子看板的汽车总装生产线的零件配送流程，建立了一种定时定量的配送方式.在此配送模式下，针对汽车总装生产线的零件配送时间窗，以配送总成本为目标函数进行配送路径优化，采用改进蚁群算法求解并进行了实例仿真，得出了能够满足现有条件的最佳配送路径，提升了生产线的整体配送效率.