库存与运输整合问题的多种算法比较

工业工程 ›› 2013, Vol. 16 ›› Issue (1): 105-109.

库存与运输整合问题的多种算法比较

（1.上海理工大学管理学院，上海 200093；2.威海职业学院信息工程系,山东威海 264210；3.鲁东大学交通学院，山东烟台 264025）

出版日期:2013-02-28 发布日期:2013-03-22
作者简介:裴英梅（1974-），女，朝鲜族，辽宁省人，博士研究生，主要研究方向为物流系统工程、供应链管理、最优化理论与方法.
基金资助:
教育部人文社会科学规划基金资助项目（10YJA630187）；高等学校博士点基金资助项目（20093120110008）；上海市重点学科建设资助项目（S30504）；上海市研究生教育创新计划资助项目（JWCXSL1021）；鲁东大学校基金资助项目（LY2011008）

A Comparative Study on Algorithms for Inventory-Transportation Integrated Optimization Problem

(1. School of Management, University of Shanghai for Science and Technology, Shanghai 200093, China;  2. Information Engineering Department, Weihai Vocational College, Weihai Shandong 264210, China;  3. School of Communications, Ludong University, Yantai Shandong 264025, China)

Online:2013-02-28 Published:2013-03-22

摘要/Abstract

摘要： 通过循序渐进地应用拉格朗日乘数法、基于样本的DSSP（Dynamic Slope Scaling Procedure）启发法和基于拉格朗日松弛模型的DSSP启发法等几种算法，分别求解多对多配送系统中的库存与运输整合优化问题，逐渐找到了解决问题的更加有效的方法——基于拉格朗日松弛模型的DSSP启发法。通过比较实验证明了此法在解决库存与运输整合优化问题时能在更少的计算时间里获得更优化的解。

关键词: 库存与运输, 整合优化, 基于拉格朗日松弛模型的DSSP启发法

Abstract: The inventory-transportation integrated optimization (ITIO) problem in a distribution network with multiple warehouses and multiple retailers is addressed. For solving this problem, different algorithms are explored. First, a Lagrange multiplier method is used to solve the integrated problem of inventory control and transportation scheduling. Then, to overcome the computationally inefficiency for large-scale problem by the Lagrange multiplier method, a scenario-based dynamic slope scaling procedure (DSSP) heuristic is proposed to establish an ITIO model. Lastly, to improve the solution accuracy of the heuristic, the Lagrangian relaxation-based DSSP heuristic is applied to solve the ITIO problem. Comparison is done for problems in a many-to-many distribution network. Results show that the Lagrangian relaxation-based DSSP heuristic outperforms the others in both solution accuracy and computational efficiency.

Key words: inventory and transportation, integrated optimization, Lagrangian relaxation-based DSSP heuristic

裴英梅1,2，叶春明1，左翠红2, 刘立辉3. 库存与运输整合问题的多种算法比较[J]. 工业工程, 2013, 16(1): 105-109.

Pei Ying-mei1, 2, Ye Chun-ming1, Zuo Cui-hong2, Liu Li-hui3. A Comparative Study on Algorithms for Inventory-Transportation Integrated Optimization Problem[J]. Industrial Engineering Journal , 2013, 16(1): 105-109.

参考文献

［1］刘立辉,钱燕云.一对多配送网络中ITIO问题的建模与算法研究［J］.公路交通科技,2006,23 (10):136-141. Liu Li-hui,Qian Yan-yun.Model and algorithm for inventory-transportation integrated optimization problem:In view of one-many distributing network ［J］.Journal of Highway and Transportation Research and Development, 2006,23 (10):136-141. ［2］傅成红,符卓.单周期离散随机需求的库存-运输整合优化［J］.系统工程,2007,25 (1):9-12. Fu Cheng-hong,Fu Zhuo.Optimization on ITIO of single-cycle discrete and stochastic demand ［J］.Systems Engineering,2007,25 (1):9-12. ［3］王勇,李富昌.基于非对称理性的ITIO动态演化分析［J］.管理工程学报,2011,25 (1):158-164. Wang Yong,Li Fu-chang.Evolutionary ITIO analysis based on asyetric rationality ［J］.Journal of Industrial Engineering and Engineering Management, 2011,25 (1):158-164. ［4］刘立辉,叶春明.多对一配送网络中的库存与运输整合问题［J］.公路交通科技,2009,26 (10):144-148. Liu Li-hui,Ye Chun-ming.Modeling and algorithm for inventory-transportation integrated optimization problem in many-one distribution network ［J］.Journal of Highway and Transportation Research and Development,2009,26 (10):144-148. ［5］Hwang H J,Chung M C,Juang D S,et al.Practical optimization of group piles using discrete Lagrange multiplier method ［J］.Optimization and Engineering,2011,12 (1-2):83-109. ［6］Izmailov A F.On the limiting properties of dual trajectories in the Lagrange multipliers method［J］.Computational Mathematics and Mathematical Physics,2011,51(1):1-20. ［7］娄山佐,吴耀华.基于分解协调法解决多库房库存——路径问题［J］.公路交通科技,2007,24 (9):145-151. Lou Shan-zuo,Wu Yao-hua.Solving Multi-depot inventory-routing problems based on decomposition and coordination Method ［J］.Journal of Highway and Transportation Research and Development,2007,24 (9):145-151. ［8］Ahn K W,Chan K S.Efficient Markov chain Monte Carlo with incomplete multinomial data ［J］.Statistics and Computing,2010,20 (4):447-456. ［9］Kim D.Piecewise lineerities in network flows［D］.Gainesviue:University of Florida,1999. ［10］Kim D,Pardalos P M.A solution approach to the fixed charge network flow problem using dynamic slope scaling procedure ［J］.Operations Research Letters ,1999,24(4):195-203. ［11］Bai L,Hearn D W,Lawohongpanich S.A heuristic method for the minimum toll booth problem［J］.Journal of Global Optimization, 2010,48(4):533-548. ［12］Lawphongpanich S.Dynamic slope scaling procedure and Lagrangian relaxation with subproblem approximation ［J］.Journal of Global Optimization,2006,35 (1):121-130. ［13］Wen Y F,Liao W.Minimum power multicast algorithms for wireless networks with a Lagrangian relaxation approach ［J］.Wireless Networks,2011,17 (6):1401-1421. ［14］Althaus E,Canzanr S.A Lagrangian relaxation approach for the multiple sequence alignment problem ［J］.Journal of Combinatorial Optimization,2008,16 (2):127-154. ［15］Nesterov Y.Primal-dual subgradient methods for convex problems ［J］.Mathematical Programming,2009,120 (1):221-259.