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

摘要/Abstract

摘要： 针对生产与运输两个过程的联合决策，通过分析一类生产-运输批量优化问题，建立的混合0-1整数规划模型整合了多产品多阶段能力约束批量生产和产品运输。其中运输成本由运输工具使用数量决定，当企业内部运输能力不能满足运输需求时可将运输外包，但需支付更高的运输成本。根据此问题的特点，构造改进蚁群算法求解，令其信息素和启发信息都存在0和1两种状态下的不同取值，通过转移概率确定0-1生产准备矩阵,进一步得到生产矩阵和运输计划。仿真实验结果表明在生产批量决策的同时考虑运输，可以减少运输成本，令总费用最小，通过将实验结果与其他优化算法比较，所构造的蚁群算法寻优概率是100%，平均进化10代，平均耗时小于1 s，稳定性和求解效率均高于其他算法，是求解这类问题一种有效与适用的算法。

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

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-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.

Key words: dynamic lot sizing, transportation costs, ant colony algorithm

李英俊，陈志祥. 基于改进蚁群算法的一类运输能力约束的生产-运输批量问题求解[J]. 工业工程, 2012, 15(6): 119-125.

Li Ying-jun, Chen Zhi-xiang. An Improved Ant Colony Algorithm for Solving Production-Transportation Lot-Sizing Problem[J]. Industrial Engineering Journal , 2012, 15(6): 119-125.

参考文献

［1］Hwang H, Sohn K I. An optimal policy for the dynamic transportation-inventory model with deteriorating items ［J］. IIE Transactions, 1985, 17(3): 233-241. ［2］Lee C Y.A solution to the multiple set-up problem with dynamic demand ［J］.IIE Transactions,1989,21(3):266-270. ［3］Lee W S, Han J H, Cho S J.A heuristic algorithm for a multi-product dynamic lot-sizing and shipping problem ［J］. International Journal of Production Economics, 2005, 98(2): 204-214. ［4］Ertogral K, Wu S, Burke L. Coordinating production and transportation scheduling in supply chains. Bethelhem ［R/OL］.(2011-11-20). http://www.lehigh.edu/~sdw1/ertogral1.pdf. ［5］Van Norden L, Van de Velde S. Multi-product lot sizing with a transportation capacity reservation contract ［J］. European Journal of Operational Research, 2005, 165(1): 127-138. ［6］Rizk N, Martel A, Ramudhin A. A Lagrangean relaxation algorithm for multi-item lot-sizing problems with joint piecewise linear resource costs ［J］. International Journal of Production Economics, 2006, 102(2): 344-357. ［7］Li C L , Hsu V N, Xiao W Q. Dynamic lot sizing with batch ordering and truckload discounts ［J］. Operations Research, 2004, 52(4): 639-645. ［8］鲁奎.考虑运输成本和多供应商的动态经济批量问题研究［D］. 合肥：中国科学技术大学，2007. Lu Kui. Studies on the dynamic version of the economic lot sizing model with transportation costs and multi-suppliers［D］. Hefei: University of Science and Technology of China, 2007:28-36. ［9］马慧民,叶春明,张爽,等.考虑运输成本的单级多资源约束生产批量问题研究［J］. 制造业自动化,2009, 31(1): 13-16. Ma Hui-min, Ye Chun-ming, Zhang Shuang,et al. Research on incorporating transportation costs into the single level capacitated lot-sizing problem ［J］. Manufacturing Automation, 2009, 32(1): 13-16. ［10］李英俊,陈志祥.成组批量生产计划问题的改进蚁群算法求解［J］.中国企业运筹学,2011(1):14-20.  Li Ying-jun, Chen Zhi-xiang. An improved ant colony algorithm for solving capacitated dynamic lot-sizing problem in group technology cell［J］. China Journal of Enterprise Operations Research, 2011(1):14-20. ［11］Marco Dorigo, Thomas Stutzle. Ant colony optimization ［M］. USA, MA: The MIT Press, 2004: 92-96. ［12］Pitakaso R,Almeder C,Dorner K F, et al. A MAX-MIN ant system for unconstrained multi-level lot sizing problems ［J］. Computers & Operations Research, 2007, 34(9): 2533-2552. ［13］Almeder C. A hybrid optimization approach for multi-level capacitated lot sizing problems ［J］. European Journal of Operational Research, 2010, 200(2): 599-606.［14］唐立新.CIMS下生产批量计划理论及其应用［M］. 北京: 科学出版社, 1998: 40-47, 132-137. ［15］马慧民,柳毅,叶春明.基于改进粒子群算法求解单级多资源约束生产批量计划问题［J］. 工业工程与管理, 2005, 10(6): 66-70. Ma Hui-min, Liu Yi, Ye Chun-ming. Improved particle swarm optimization algorithm for the single level capacitated dynamic lot-sizing problem ［J］. Industrial Engineering and Management, 2005, 10(6): 66-70. ［16］许志兴,丁运亮,熊仲宇,等.基于退火惩罚混合遗传算法求解生产批量计划问题［J］. 南京航空航天大学学报, 2001, 33(1): 91-95. Xu Zhi-xing, Ding Yun-liang, Xiong Zhong-yu, et al. Annealing penalty hybrid genetic algorithm for solving production-scheduling problem ［J］. Journal of Nanjing University of Aeronautics & Astronautics, 2001, 33(1): 91-95.

[1]	闫军, 常乐, 王璐璐, 赵彤. 带时间窗的同时取送货车辆路径问题求解算法[J]. 工业工程, 2021, 24(5): 72-76.
[2]	刘电霆, 胡浩平, 吴丹玲. 社会化产品开发众包设计任务间加权网络建模与模块划分[J]. 工业工程, 2021, 24(5): 95-100.
[3]	周晓晔, 马小云, 崔瑶, 王思聪. 单线超市车辆配置与路径问题优化研究[J]. 工业工程, 2020, 23(6): 83-88,116.
[4]	李魁梅, 郑波. 考虑综合运输成本的多式联运路径优化问题[J]. 工业工程, 2020, 23(5): 67-74.
[5]	周娜, 舒帆, 金佩卿. 基于混合启发式算法的设备混合布局问题[J]. 工业工程, 2017, 20(1): 77-82.
[6]	阮焕1，耿亮1,2，肖人彬1. 基于极值—蚁群算法的电商末端物流弹性配送策略研究[J]. 工业工程, 2016, 19(1): 51-60.
[7]	何利娟1, 李欣2. 基于蚁群算法的资源均衡优化决策及其MATLAB实现[J]. 工业工程, 2015, 18(6): 125-129.
[8]	项薇1, 殷姣1, 陈赛峰2 . 考虑实际护士排班约束的手术排程优化[J]. 工业工程, 2013, 16(5): 120-124.
[9]	屈国强1，2，李俊芳1，侯东亮1，3. 蚁群系统结合指派规则求解HFS调度问题[J]. 工业工程, 2012, 15(3): 62-68.
[10]	张毕西，张万里，宋静. 基于蚁群算法的中小手工制造企业人员调度 [J]. 工业工程, 2011, 14(4): 119-123.