An Improved Ant Colony Algorithm for Solving Production-Transportation Lot-Sizing Problem

Abstract

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

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.

References

［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]	YAN Jun, CHANG Le, WANG Lulu, ZHAO Tong. A Solution Algorithm for the Problem of Taking Delivery Vehicle Path at the Same Time with Time Window [J]. Industrial Engineering Journal, 2021, 24(5): 72-76.
[2]	LIU Dianting, HU Haoping, WU Danling. Weighted Network Modeling and Module Partitioning Among Crowdsourcing Design Tasks for Social Product Development [J]. Industrial Engineering Journal, 2021, 24(5): 95-100.
[3]	ZHOU Xiaoye, MA Xiaoyun, CUI Yao, WANG Sicong. A Research on Optimization of Vehicle Allocation and Routing for Single-line Supermarket [J]. Industrial Engineering Journal, 2020, 23(6): 83-88,116.
[4]	ZHOU Na, SHU Fan, JIN Peiqing. Facility Mixed Layout Problems (FMLP) based on Hybrid Heuristic Algorithms [J]. Industrial Engineering Journal , 2017, 20(1): 77-82.
[5]	RUAN Huan1, GENG Liang1,2, XIAO Renbin1. Ecommerce Ending Logistics Resilient Distribution Strategy Research Based on the Extreme Optimization—Ant Colony Algorithm [J]. Industrial Engineering Journal , 2016, 19(1): 51-60.
[6]	He Li-juan, Li Xin. Resource Leveling Based on Ant Colony Algorithm and MATLAB Optimization Decision [J]. Industrial Engineering Journal , 2015, 18(6): 125-129.
[7]	Zhang Bi-xi，Zhang Wan-li，Song Jing. Ant Colony-Based Labor Allocation Method for Small-and-Medium-Size Manufacturing Workshops [J]. Industrial Engineering Journal , 2011, 14(4): 119-123.