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

An Improved Ant Colony Algorithm for Solving ProductionTransportation Lot-Sizing Problem

作　　者：李英俊[1] 陈志祥[1] 

机构地区：[1]中山大学管理学院,广东广州510275

出　　处：《工业工程》2012年第6期119-125,共7页Industrial Engineering Journal

基　　金：国家自然科学基金资助项目(70972079)

摘　　要：针对生产与运输两个过程的联合决策,通过分析一类生产-运输批量优化问题,建立的混合0-1整数规划模型整合了多产品多阶段能力约束批量生产和产品运输。其中运输成本由运输工具使用数量决定,当企业内部运输能力不能满足运输需求时可将运输外包,但需支付更高的运输成本。根据此问题的特点,构造改进蚁群算法求解,令其信息素和启发信息都存在0和1两种状态下的不同取值,通过转移概率确定0-1生产准备矩阵,进一步得到生产矩阵和运输计划。仿真实验结果表明在生产批量决策的同时考虑运输,可以减少运输成本,令总费用最小,通过将实验结果与其他优化算法比较,所构造的蚁群算法寻优概率是100%,平均进化10代,平均耗时小于1 s,稳定性和求解效率均高于其他算法,是求解这类问题一种有效与适用的算法。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-sizing and 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 exceed the transportation capacity,it can be outsourced,but with higher freight rate.After analyzing the properties of the model,an improved ant colony algorithm（ANT） is proposed.By this algorithm,different value 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 that integrated production and transportation can effectively reduce the procurement cost and further reduce the total cost.Comparison with other methods shows that the searching optimization probability of the proposed ANT is 100%,the average evolved generations is 10,the average time is 1 second.The ANT is more stable and better for seeking efficiency than other algorithms.

关 键 词：生产批量计划 运输成本 蚁群算法 

分 类 号：TH165[机械工程—机械制造及自动化]