热门关键词:

基于改进蚁群算法的一类运输能力约束的生产-运输批量问题求解

  • 该文件为pdf格式
  • 文件大小:419.74KB
  • 浏览次数
  • 发布时间:2017-03-24
文件介绍:
本资料包含pdf文件1个,下载需要1积分

An Improved Ant Colony Algorithm for Solving Production-Transp0rtati0n Lot-Sizing ProblemLi Ying-jun,Chen Zhi-xiang(School of Business,Sun Yat-sen University,Guangzhou 510275,China)Abstract:Aiming at the implementation of joint decision of production and transportation,production-transportation lot-sizing problem is discussed,which is a multi-item-and-multi-period capacitated lot-sizingand transportation problem.This problem is then formulated as a 0-1 mixed integer programming problem。

In this model,the transportation cost is decided by the numbers of containers.However,if demands ex-ceed the transportation capacity,it can be outsourced,but with higher freight rate.After analyzing theproperties of the model,an improved ant colony algorithm(ANT)is proposed.By this algorithm,diferentvalue of pheromone and heuristic information is set as 0-state or 1-state.Then,the 0-1 setup matrix,production matrix,and transportation plan can be obtained accordingly.A numerical example shows thatintegrated production and transportation can effectively reduce the procurement cost and further reduce thetotal cost.Comparison with other methods shows that the searching optimization probability of the proposedANT is 100% ,the average evolved generations is 10,the average time is 1 second.The ANT is more sta-ble and better for seeking eficiency than other algorithms。

Key words:dynamic lot sizing;transportation costs;ant colony algorithm企业的生产过程涉及很多的优化和决策过程, 而各个部门又根据自己的目标来分别处理不同的决收稿日期:2011-12-06基金项目:国家自然科学基金资助项 目(70972079)作者简介:李英俊(1983-),男,广东省人,博士研究生,主要研究方向为运筹优化与生产管理120 第 15卷策问题,每个部门的决策问题寻找最优解是非常困难的,将各个部门的问题组合进行综合的最优决策就更加困难了。譬如,运输人员为了降低运输成本,会最大化地使用运输工具,增大每-次运输产品的数量,减少运输中断点;另-方面,生产人员为了降低成本,会减少生产准备的次数,同时为了减少库存而经常要求安排运输 因此如何降低整个供应链上的成本(包括生产,运输,库存等),综合优化生产与运输的联合决策问题,就显得很关键。

目前,关于将运输成本集成到批量问题中进行联合决策的研究成果较多。主要可分为如下几个方面:1)考虑运输工具无运输能力约束情况下的生产批量问题;2)考虑运输工具在有限运输能力下的生产批量问题,其 中运输成本是 运输数量 的函数 引;3)考虑运输工具在有限运输能力下的生产批量问题,但单位运输成本是常数 引;4)考虑运输工具无输能力约束下运输数量折扣的生产批量问题 引。

针对以往文献对运输工具使用费用考虑的不足,鲁奎 构造了考虑运输成本情况下的动态批量模型。此模型中的运输分为两部分,-部分是企业内部有限的运输能力;另-部分是企业外部的第三方运输,即运输任务外包。运输任务外包只在企业内部运输能力不足的情况下才会发生,外包的数量不限,但是每单位的运输成本要 比企业内部的要高。

最后设计了基于拉格朗日松弛的启发式算法对模型进行求解。马慧民等 改进了该模型,考虑生产能力的多资源约束和不同产品问体积的差异,并使用粒子群算法进行求解。本文主要在作者求解成组批量生产计划问题的改进蚁群算法的基础上进行改进 ,使其能有效地解决考虑运输成本的单级多资源约束的生产批量问题。

蚁群算法的基本模型是 1991年 Marco Dorigo最先提出的-种通过模拟蚂蚁的觅食行为的仿生智能进化算法 。每只蚂蚁知识的积累来自于与其他蚂蚁的通信媒介--信息素,每只独立的蚂蚁在可行解内随机搜索的时候,通过同伴留下的信息素影响转移概率来决定下-条路径,并在所选择的路径释放自身的信息素来增加该路径的信息素累积量,这样较优的路径就会累积越来越多的信息素,当所有的蚂蚁都确定了自身的路径时,就逐步形成-条最优的路径。通过这种随机决策和相互协调的能力,蚁群算法在求解离散优化问题(如 TSP、VRP、整数规划等)和连续优化问题都得到了大量的应用。

虽然蚁群算法在这些领域取得了不少应用成果,但是国内外对蚁群算法应用在批量生产问题的研究并不多,如Pitakasol 等使用蚁群算法和改进的Wag-ner.Whitin算法来求解无能力约束的两层批量生产问题;Almeder 13j使用蚁群算法和 LP/MIP求解器(如 CPLEX)相结合的方法来求解 能力约束的两层批量生产问题;李英俊等 。。在其基础上对蚁群算法进行改进,通过构造二元的信息素和启发信息来求解批量生产问题中0-1变量和将能力约束变为惩罚因子的方法,将蚁群算法成功应用于成组批量生产计划问题。而国内目前尚没有将蚁群算法应用在生产 -运输批量优化的报道,本文的研究具有-定的理论先进性与应用价值。

1 问题模型在单机多资源约束下多产品多周期的生产批量计划问题的基础上,考虑运输成本进行建模。工厂会根据客户每个周期的各种产品的需求进行生产批量计划的安排,并在每个周期末将生产的产品通过- 种运输工具运送给客户,即不考虑运输中产品间的体积差异。运输可以由企业内部有限的运输能力完成,但是当企业内部的运力不足时,可以将运输任务外包。这里假设外包情况下单位运输工具使用成本比企业内部单位运输工具使用成本高,且认为外包使用费用时变,可构造运输成本函数如下 :(t))f ok1( ) (t), (t)≤K; lkok1(t)Kk2(t)( (t)-K), >K。

其中,k。为与运输数量无关的固定成本;k。(t)和 k:(t)分别为 t周期企业内部运输和外包运输的单位运输工具的成本;K为企业内可使用的运输工具的数量; 为 t周期企业的运输需求;t1,,; 为计划范围长度。

不失-般f生假定:1)每个周期生产的产品在该周期末就运送给客户,且假设运输过程不耗费时间;2)每个产品的初始库存和结束库存为零,即IioIi 0,1≤

因此,考虑运输成本能力约束的生产 -运输批量问题优化模型为- Ⅳmin f∑∑(p , )∑( 、 i 1 t: I t l、k (t) 。(t)k2(t) 2(t))l。 (2)第 6期 李英俊,陈志祥 :基于改进蚁群算法的-类运输能力约束的生产 -运输批量问题求解 121L, . . , 、 2 改进蚁群算法I. - 1 ☆i d,i1,,N,t1,, ;(3) 、~ 、 。 。。-∑( Ynbo )≤ √1,,R,t1,, ;1(4)≤ i1,,N,t1,, ; (5)Ⅳ∑Vi n≤ ( l(t) 2(t)),t1,, ;(6)l l0≤ l(t)≤ ,t1,,71; (7)1(t)≤G(J ,t1,, ; (8)Y ∈0,1,i1,,N,t1,, ; (9)(cJ ∈0,1,t1,, ; (10)>t0,Ii >10,i1,,N,t1,, ; (11)l( ), 2(t)∈N,t1,, 。 (12)其中,Ⅳ为生产项目的数量;R为可用资源数;d为产品 在第 t期的外部需求;P 为产品 i在第 周期的单位生产成本;s 为产品在第周期的调整成本;为产品在第 t周期的单位存储成本;k。为与运输数量无关的固定成本;k (t)为企业内部运输工具的单位使用成本;k:(t)为外包情况下运输工具的单位使用成本; i为产品的体积;V为单位运输工具可以运输的最大产品数量;K为单个生产周期内企业内部运输工具的数量;。 为生产单位产品 i所需资源的准备工时系数 b为生产单位产品i所需资源的加工工时系数 ;C 为资源 在周期 的可用总工时; 和 G都为-个足够大的数。

决策变量如下: 为产品 在第 t周期的生产量;, 为产品 i在第 t周期末的库存量;y 为产品 i在第 t周期如果安排生产,则Y 1,否则 Y 0; (t)为 t周期企业内部使用的运输工具的数量; (t)为t周期外包使用的运输工具的数量;∞ 为 t周期运输的启动变量,如果 t周期有进行运输,则 1,否则090。

目标函数(2)考虑了生产 -存储 -运输三者的总成本最校约束(3)是库存平衡公式;约束(4)表示生产工时能力限制;约束(5)表示只有生产发生时才产生调整成本;约束(6)表示每个周期的运输能力满足产品运输的需求;约束(7)表示每个周期内企业内部的运输工具可使用数量不大于K;约束(8)表示运输发生时才产生运输启动成本;约束(9)表示Y是0-1变量;约束(10)表示 (cJ 是 0-1变量;约束(1 1)表示每个生产周期的生产数量和库存量为非负数;约束(12)表示 。、 :为 自然数。

2.1 解的结构考虑到上述运输成本的生产批量优化模型是-个混合整数规划问题,因此求解的思想是先确定整数变量 Y 然后确定连续变量 和 。

借鉴求解单级多资源约束的批量计划问题的相关文献 ,-旦整数变量 y 确定(i∈[1,N],t∈[1,]),则此问题解中连续变量 和 ,l 也可以通过 Y而唯-确定。即X ir0, if Y 0; t, (13) do,if y 1,: y咖1。

Ii cl n-d (14)当得到 后可确定运输启动变量,即,09 : i 1 (15) , )J1,。therwise;Vt。

令 I( )/V I再由式(6)和式(7)可得到(17)2.2 改进蚁群算法鉴于决策变量是 0-1变量,而在蚁群算法中,Y 的取值是 由信息素和启发信息 2个元素来决定的,因此需要分别设置Y 1和Y 0时2种情况下所对应的信息素和启发信息,具体操作如下。

在信息素的设置中,令 (z)[ (z)] ,为蚂蚁 k在 Z次迭代中所对应进行生产(即Y 1情况下)的信息素矩阵,其中矩阵元素f (z)为蚂蚁k在Z次迭代中所对应的产品 在周期 t进行生产的信息素。同理,令 。 (Z)[ k 。 (Z)] 为蚂蚁 在z次迭代中所对应不安排生产(即 Y 0情况下)的信息素矩阵,其元素f (f)为蚂蚁 k在 z次迭代中所对应的产品i在周期 t不安排生产的信息素。信息素f ”(f)秕 (2)在z:0时的初始值都是在区间[0.01,1]中随机产生,具体如下:r ”(z) i rand(0,1)· 。 (18)其中设定信息素的最小值r i 0.01和最大值r 1,rand(O,1)为生成区间[0,1]间随机数的函数。

工 业 工 程 第 15卷在蚁群算法中,启发信息为蚂蚁对路径的可见度,而在本文中,启发信息是选择生产或不安排生产的偏好。因此启发信息只与产品 i在周期 t的调整成本有关,而与迭代数和蚂蚁的数量无关。

显然如果生产调整成本系数越大,则其可见性也应该越小,因此令 H [叼 ] 为进行生产(即Y 1情况下)的启发信息矩阵,启发信息矩阵中元素叼 ”为产品i在 t时间段进行生产的启发信息,由下式进行确定:7 cO/s (19)其 中,C 为 给 定 的 常 数。同理 令 H [卵 ] 为不安排生产的启发信息矩阵,其元素叼 为产品 i在 t时间段不安排生产的启发信息,显然,有 7 1-叼 。

当得到算法中的信息素和启发信息后就可以计算转移概率。令 (f)[Y (z)] 为蚂蚁 k在 f次迭代中的调整变量矩阵,其中元素Y (z)为蚂蚁 k在f次迭代中所对应的产品i在周期t是否进行生产的调整变量,如果进行生产,则 Y (z)1,否则 Y (f)0。则算法中的转移概率可通过下式进行计算 :、 k”(f) 叼:”]八 -[f (f)] [叼 ] k (f)] [卵 (20)其中,p:(z)为蚂蚁k在f次迭代中所对应的产品i在周期 t进行生产的概率,本文中设定如下的转移规则:yikt(1): 。。5; (21)to,otlaerwlse。

蚂蚁k在 Z次迭代选择产品i在周期 t进行生产的转移概率比不安排生产的转移概率大,则令调整变量Y (f):1,否则令 Y (z)0。

在智能算法的求解过程中,对所求得的初始解进行局部搜索算法能有效地提高解的求解质量和算法的收敛速度1 ,因此为了得到更高质量的解,本文对调整变量进行局部搜索的操作,通过改变调整变量Y:(z)的值来得到新的调整变量。具体的操作为,新生成的调整变量将作为蚂蚁在下-次迭代中的新寻优方向,这样的局部搜索有利于蚂蚁能寻找到更优的解,求解更迅速。

2.3 算法流程求解考虑运输能力受限且允许能力外包的生产批量优化模型的改进蚁群算法流程如下。

1)初始化确定总迭代的次数 ,蚂蚁的数量 K,参数 c。,学习因子 C。,C ,信息素的重要性 Ot,启发信息的重要性,变异概率 6。根据式(18)生成信息素矩阵初始值;根据式(19)生成启发信息矩阵初始值。

2)主循环For Z1:LFor k1:KFor i1:NFor t1-T根据式(20)计算转移概率,根据式(21)确定0-1变量矩阵 (z)。

End forEnd forFor il:NFor t1:T由式(13)得到生产量 (f),通过式(14)可进-步得到库存量Iikt(z)。

End forEnd forFor t1-T由式(16)和(17)得到 (t), (t)End for计算适应值 ∑∑(p sitY )∑( 。

其中 为蚂蚁 k在 z次迭代的适应值。寻找第z次迭代最优蚂蚁得到的适应值(z)min ,其对应的决策矩阵为 l,j (z)End for更新全局最优适应值厂0 lmin厂0 (Z),其对应的0-l决策矩阵为 l, 。

信息素增量用如下方法计算:当前迭代寻得最优解的蚂蚁的信息素增量为A 0 /1(1) ,for yiht。。 ∈Yitr(2),寻得当前全局最优解的蚂蚁的信息素增量为△ (2) C2,for Y 0/1∈Yo (z),opt此次迭代总的信息素增量为 △Jr A 0 /(1)A o /(2)。

则下-次迭代的信息素值为(z1)max[r i rain(r ,P r (f)△f )]。

第6期 李英俊,陈志祥:基于改进蚁群算法的-类运输能力约束的生产-运输批量问题求解End ±or3 仿真实验以文献[15]中的问题为例,使用 7.0为上文提出的算法编写程序。该例考虑的是 5个周期,5个产品以及2个资源的批量计划问题,原始数据见表 1和表 2,考虑的运输成本的参数见表 3。本文的改进蚁群算法的参数如下:C。C 180,蚁群的规模为30,每次运行的进化代数最大为20。此算法程序在主频为2GHZ,操作系统为 windows 7的笔记本上独立运行50次,其中运行50次和运行 1次的结果及其 目标函数收敛曲线如图1所示,平均每次运行耗时不到 1S,经LINGO软件验算,本文算法50次的运行结果都达到了最优值,平均进化代数大约为1O代。

表 1 模型原始参数Tab.1 Parameters of simulation Test为了说明算法的有效性,本文将改进蚁群算法的计算结果与文献 [15]和文献[16]中的结果进行对比,比较的结果见表4。从表4可以看出,单从生产方面来看,本文的批量生产计划比文献[15]中的方案成本要大,但是当考虑到运输费用时,本文的批量计划的总成本(生产成本 运输成本)大幅减少,因此可以认为本文的改进蚁群算法比其他算法更有效表3 与运输有关的相关参数Tab.3 Parameters related to transportation表4 计算结果比较Tab.4 Comparison of computational results124 工 业 工 程 第 15卷镫2 6502 6002 5502 50024502 4004 结束语2 5802 5602 5402 520将 2 5002 4802 4602 4402 4202 400 0迭代次数 迭代次数(a)运行5O次的收剑图 (b)运行-次的收剑图图1 仿真实例的程序运行 5O次和运行 1次收敛曲线Fig.1 Convergent curves of 50 runs and 1 run by proposed algorithmOL].(2011-11-20).htp://www.1ehigh.edu/~sdwl/er-蚁群算法是-种有效的群智能算法,已经广泛应用在不同的组合优化问题中。生产批量问题是-类经典的生产管理问题,国内外对生产批量问题的研究已经有不少文献,但是考虑把生产成本与运输成本集成起来进行优化的研究还比较缺乏。本文在相关的研究基础上,对考虑运输能力束的生产 -运输批量优化模型进行分析,并为该模型设计了改进蚁群算法。通过仿真实验表明,本文所提出的改进蚁群算法对于求解该模型在求解速度和质量上都优于文献[14-l5]的结果,显示本文提出的算法对于求解这-类运输能力约束的生产 -运输批量计划模型具有很好的应用价值。对于生产 -运输批量优化的研究还可以做进-步的拓展,如考虑运输折扣或订货折扣,而在假设上可以考虑运行缺货的情况,而在求解算法上,可以进-步考虑使用混合算法求解此类问题

正在加载...请等待或刷新页面...
发表评论
验证码 验证码加载失败