部队给养物资配送方案优化模型及其应用研究
摘要
随着信息技术在军事领域的广泛运用,军事物流发生了新的重要变革,物资配送工作是其中一个重要环节。在补给中心的给养物资配送工作中,配送方案优化问题是一个非常有价值而极具魅力的问题,优质的配送方案将产生可观的军事经济效益。
论文在分析物流配送方案优化方法发展过程的基础上,研究了补给中心与部队用户之间不同情况下配送方案优化问题的模型建立与算法设计。根据用户库存情况和对配送时间的要求,分别建立了不考虑补给中心库存的单周期配送方案优化模型与考虑补给中心库存的多周期配送方案优化模型。在不考虑补给中心库存的单周期配送优化过程中,分析了补给中心配送资源在受限与不受限情况下模型建立与求解方法。如果补给中心的资源受限,配送成本受用户的库存影响,随机库存分配问题的解决决定着整个问题的解决,论文根据相关文献设计了用于解决这一问题的近似算法,将禁忌搜索算法用到了这一问题中,取得了较好的优化效果;如果配送资源不受限制,总配送成本不受用户库存成本的影响,问题转化为带有时间窗的车辆路径问题(VRPTW),论文将这一问题分解为两个阶段来设计求解,在第一阶段使用遗传算法,第二阶段使用快速有效的节约启发式算法。在考虑补给中心库存的多周期配送优化过程中则利用启发式算法,通过反复迭代,不断协调补给中心和用户之间的相互影响,不断优化策略,最终确定配送方案。
最后,以某师远程机动演习为背景,对资源不受限制的一对多给养物资单周期配送方案优化进行了实例分析,分析解决了几种模型中都涉及的核心问题,即带有软硬时间窗的配送方案的确定。在利用计算机实现过程中,充分考虑了用户对软硬时间窗的要求,最终生成了车辆路径的最优配送方案,基本满足了实际应用。
With the wide application of imformation technology, military logistics industry has made a newly important change, and the freight distribution is an important link. In the course of freight distribution in a distribution center, the distribution plan optimization problem is a fascinating one. An excellent distribution plan can bring extremely considerable military economic profits.
On the base of analyzing the developing process of the logistics planning optimization, we make a research on the algorithm design of the distribution plan optimization problem under different conditions in the thesis, then set up the optimization model of the distribution plan including not only the single cycle which doesn't consider the inventory cost but also the multicycle considering the inventory cost according to the customers' inventory instance and demand of the distribution time.We analyze the method of the model's setting up and the solution depending on different conditions. If the resource in the distribution center is finite, the custom inventory would affects the distribution cost and the stochastic inventory allocation problem is the key to whole problem's resolving. An approximate algorithm is designed in order to resolve this problem according to interrelated documents in this thesis in which the Tabu Search is used and a good optimization result is obtained; If the resource is infinite in the distribution center, the distribution cost would not be affected by the custom inventory, then it changes into the vehicle routing problem with time windows (VRPTW), which is disintegrated into two parts solved respectly. Genetic algorithm is used in the first part and the saved heuristics algorithm is used in the second part. During the multicycle distribution optimization, we use heuristic algorithm through iterative computing, unceasingly balancing the interactions between supply center and customers and incessant plan optimization to confirm the distribution plan finally.
In the end, on the background of the remote mobility military manoeuvres, the thesis gives a case analysis of the One-Many military logistics single cycle distribution without resources limitations, and analyzes the key problem involved in several models, which is the determination of the distribution plan with soft and hard time windows. Completely considering the customers' require in soft and hard time windows, the vehicle optimization distribution plan has been formed and the total cost is being computed out at the same time, which satisfies the practical appliance.
论文在分析物流配送方案优化方法发展过程的基础上,研究了补给中心与部队用户之间不同情况下配送方案优化问题的模型建立与算法设计。根据用户库存情况和对配送时间的要求,分别建立了不考虑补给中心库存的单周期配送方案优化模型与考虑补给中心库存的多周期配送方案优化模型。在不考虑补给中心库存的单周期配送优化过程中,分析了补给中心配送资源在受限与不受限情况下模型建立与求解方法。如果补给中心的资源受限,配送成本受用户的库存影响,随机库存分配问题的解决决定着整个问题的解决,论文根据相关文献设计了用于解决这一问题的近似算法,将禁忌搜索算法用到了这一问题中,取得了较好的优化效果;如果配送资源不受限制,总配送成本不受用户库存成本的影响,问题转化为带有时间窗的车辆路径问题(VRPTW),论文将这一问题分解为两个阶段来设计求解,在第一阶段使用遗传算法,第二阶段使用快速有效的节约启发式算法。在考虑补给中心库存的多周期配送优化过程中则利用启发式算法,通过反复迭代,不断协调补给中心和用户之间的相互影响,不断优化策略,最终确定配送方案。
最后,以某师远程机动演习为背景,对资源不受限制的一对多给养物资单周期配送方案优化进行了实例分析,分析解决了几种模型中都涉及的核心问题,即带有软硬时间窗的配送方案的确定。在利用计算机实现过程中,充分考虑了用户对软硬时间窗的要求,最终生成了车辆路径的最优配送方案,基本满足了实际应用。
With the wide application of imformation technology, military logistics industry has made a newly important change, and the freight distribution is an important link. In the course of freight distribution in a distribution center, the distribution plan optimization problem is a fascinating one. An excellent distribution plan can bring extremely considerable military economic profits.
On the base of analyzing the developing process of the logistics planning optimization, we make a research on the algorithm design of the distribution plan optimization problem under different conditions in the thesis, then set up the optimization model of the distribution plan including not only the single cycle which doesn't consider the inventory cost but also the multicycle considering the inventory cost according to the customers' inventory instance and demand of the distribution time.We analyze the method of the model's setting up and the solution depending on different conditions. If the resource in the distribution center is finite, the custom inventory would affects the distribution cost and the stochastic inventory allocation problem is the key to whole problem's resolving. An approximate algorithm is designed in order to resolve this problem according to interrelated documents in this thesis in which the Tabu Search is used and a good optimization result is obtained; If the resource is infinite in the distribution center, the distribution cost would not be affected by the custom inventory, then it changes into the vehicle routing problem with time windows (VRPTW), which is disintegrated into two parts solved respectly. Genetic algorithm is used in the first part and the saved heuristics algorithm is used in the second part. During the multicycle distribution optimization, we use heuristic algorithm through iterative computing, unceasingly balancing the interactions between supply center and customers and incessant plan optimization to confirm the distribution plan finally.
In the end, on the background of the remote mobility military manoeuvres, the thesis gives a case analysis of the One-Many military logistics single cycle distribution without resources limitations, and analyzes the key problem involved in several models, which is the determination of the distribution plan with soft and hard time windows. Completely considering the customers' require in soft and hard time windows, the vehicle optimization distribution plan has been formed and the total cost is being computed out at the same time, which satisfies the practical appliance.
引文
[1]王宗喜,徐东.军事物资流学[M].北京:清华人学出版社,2007.
[2]胡德全.军事物资配送研究[D].中国人民解放军后勤指挥学院博士学位论文,2002.
[3]黄文寿主编.当代外军后勤研究[M].北京:中国青年出版社,2005.
[4]Sariklis D,Powell S.A heuristic method for the open vehicle routing problem[J].Journal of the Operational Research Society,2000,(51):564-573.
[5]李显生,赵鲁华,李文斐,高乃修,鹿应荣.城市配送车辆调度模型及算法设计[J].吉林大学学报(工学版),2006,(4).
[6]王平,唐喜平,李云.一类多源点物流配送优化模型的探讨[J].系统工程理论与实践,2003,(3).
[7]聂凯,赖明勇,李巍,曹二保.基于陌生户问题的配送车辆调度优化模型研究[J].湖南大学学报(自然科学版),2007,(6).
[8]蒋忠中,汪定伟.物流配送车辆路径优化的模糊规划模型与算法[J].系统仿真学报,2006,(11).
[9]谭跃进.定量分析方法[M].北京:中国人民大学出版社,2003.
[10]韩大卫.管理运筹学[M].大连:大连理工大学出版社,2003.
[11]Clarke,G.&Wright,J.W.scheduling vehicles from a center delivery depot to a number of delivery points[J].Operation research puarterly,1964,(12).
[12]S.Lint and B.Kernighan.An Effective Heuristic Algorithm for me Traveling Salesman Problem[J].Operation Research,1973,(21).
[13]N.Christofides,A.Mingozzi,and P.Toth.Exact Algorithms for the Vehicle Routing Problem,Based on Spanning Trees and Shortest Path Relaxations[J].Math.Programme to appear.
[14]Gilbert Laporte,Helene Mercure and Yves Nobert.A Branch and Bound Algorithm for a Class of Asymmetrical Vehicle Routing Problems[J].J.Opl.Res.Soc,1992,43(5).
[15]Gillert,B.&Miller,L.A heuristic algorithm for the vehicle dispatch problem[J].Operation research.,1974,(22).
[16]张潜.物流配送路径优化渊度建模与实务[M].北京:中国物资出版社,2006.
[17]李军,郭耀煌.物流配送车辆优化调度理论与方法[M].北京:中国物资出版社,2001.
[18]袁庆达.随机库存—运输联合优化问题研究[D].西南交通大学博士学何论文,2001.
[19]薛毅.最优化原理与方法[M].北京:北京工业大学出版社,2001.
[20]Golden.B.L.& Skiscim,C.C.Using simulated annealing to solve routing and locating problem[J].Maval research logistics quarterly,1986,(33).
[21]Tim D.Nguyen.A neural network heuristic for the traveling salesman problem[D].B.S.University of Louisville Docter thesis,2002,(5).
[22]HuangBingXian.Memory Consolidationand Neural Network of the Hipocampus[R].Proc.IntConfNeu～ral Networkxand Signal Processing.Guangzhou,1993.
[23]Held,M.& R.Karp.The Traveling salesman problem and minimum spanning trees[J].Operations Research,1970,(18).
[24]Akaufmann.Integerand Mixed Programming:Theory and Application[M].Academic Press,Inc(London),1982.
[25]Solomon,M.M.Vehicle routing and scheduling with time windows constraints:models and algorithms[R].Ph.D.dissertation,Dept of decision sciences,University of Pennxylvania,1983.
[26]Mole,R.H.& Jameson.A Sequential route building algorithm employing generalized saving criterion[J].Operation Research quarterly,1976,(27).
[27]Herron D.Manging physical distribution for profit[C].Harvard Business Review,1979,(79).
[28]Federgruen A.Zipkin P.A combined vehicle routing and inventory allocation problem[J].Perations Research,1984,32,(5).
[29]马良.旅行推销员问题的算法综述[J].数学的实践与认识,2000,(4).
[30]徐宁,李春光等.几种现代优化算法的比较研究[J].系统工程与电子技术,2002,(12).
[31]张远福,时连强.车辆路径问题(VRP)的一个启发式算法[J].河北建筑科技学院学报,2002(9).
[32]李冰,杜文.单货物品种的运输和存储联合调度问题[J].西南交通大学学报,2003,(12).
[33]汪祖柱,程家兴.求解组合优化问题的一种方法—分枝定界法[J].安徽大学学报(自然科学版),2004,(1).
[34]张莹.运筹学基础[M].北京:清华大学出版社,1995.
[35]Bodin L.Optimization procedures for the analysis of coherent structures[C].IEEE Transaction on Reliability,1969,(18).
[36]Zipkin P.Single ranking methods for allocation of one resource[J].Mannagement Science,1980,(26).
[37]骆义.物流配送车辆调度优化研究[D].大连海事大学硕士学位论文.2003.
[38]袁庆达,杜文.带有时间窗的混合车队车辆路线问题的模型与算法研究[J].西南交通大学学报,2001,(4).
[39]张丽萍,柴跃廷,曹瑞.有时间窗车辆路径问题的改进遗传算法[J].计算机集成制造系统,2002,(6).
[40]冷德惠,张金梅,李大卫.遗传算法在有时间窗车辆路径问题上的应用[J].系统工程理论与实践,1999,(8).
[41]姜大立,杨西龙,杜文,周贤伟.车辆路径问题的遗传算法研究[J].系统工程理论与实践,1999,(6).
[42]Lover F.uture paths for integer programming and links to artifical intelligence[J].Computer and Operations Research,1986,(5).
[43]Xu J.Kelly J P.A network flow～based tabu search heuristic for the vehicle routing problem[J].Transportation Science,1996.(30).
[44]Hooker J.N.Natraj N.R.Solving a general routing and scheduling problem by chain declmposition and tabu search.[J].Transportation Science,1995,(29).
[45]Taillard E.A tabu search heuristic for the vehicle routing problem with soft time windows[J].Transportation Science,1997,(31).
[46]Gendreau M,Hertz A.tabu search heuristic for the vehicle routing problem[J].Management Science,1994,(40).
[47]Gendreau M.etc.A tabu search heuristic for the heterogeneous fleet vehicle routing problem[J].Computer & operations research,1999,(26).
[48]B.Ombuki,M.Nakamura& M.Osamu.A Hybrid Search Based on Genetic Algorithms and Tabu Search for Vehicle Routing[R].Presented at the 6th IASTED international Conference on Artificial Intelligence and Soft Computing,PP.2002,(7).
[49]P.Badeau,M.Gendreau,F.Guertin,J.～Y.Potvin and E.tailard.A Parallel Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows[J].Transportation Research,1997,(5).
[50]刘民.遗传算法方法及其在生产线调度问题中的应用研究[D].清华大学博士论文,1997.
[51]李军,谢秉磊,郭强.非满载车辆调度问题的遗传算法[J].系统工程理论方法应用,2000,(3).
[52]李军.车辆调度问题的分派启发式算法[J].系统工程理论与实践,1999,(1).
[53]谢秉磊,李军,郭耀煌.有时间窗的车辆调度问题的遗传算法[J].系统工程学报,2000,(17).
[54]Balakrishnan,N.Simple heuristics for the vehicle routing problems with soft time windows[J].Journal of operational research society,1993,44(3).
[55]Desrocher,M.Desrosiers,J.& Solomon,M.A new optimization algorithm for the vehicle routing problem with time windows[J].Operations research,1992,40(2).
[2]胡德全.军事物资配送研究[D].中国人民解放军后勤指挥学院博士学位论文,2002.
[3]黄文寿主编.当代外军后勤研究[M].北京:中国青年出版社,2005.
[4]Sariklis D,Powell S.A heuristic method for the open vehicle routing problem[J].Journal of the Operational Research Society,2000,(51):564-573.
[5]李显生,赵鲁华,李文斐,高乃修,鹿应荣.城市配送车辆调度模型及算法设计[J].吉林大学学报(工学版),2006,(4).
[6]王平,唐喜平,李云.一类多源点物流配送优化模型的探讨[J].系统工程理论与实践,2003,(3).
[7]聂凯,赖明勇,李巍,曹二保.基于陌生户问题的配送车辆调度优化模型研究[J].湖南大学学报(自然科学版),2007,(6).
[8]蒋忠中,汪定伟.物流配送车辆路径优化的模糊规划模型与算法[J].系统仿真学报,2006,(11).
[9]谭跃进.定量分析方法[M].北京:中国人民大学出版社,2003.
[10]韩大卫.管理运筹学[M].大连:大连理工大学出版社,2003.
[11]Clarke,G.&Wright,J.W.scheduling vehicles from a center delivery depot to a number of delivery points[J].Operation research puarterly,1964,(12).
[12]S.Lint and B.Kernighan.An Effective Heuristic Algorithm for me Traveling Salesman Problem[J].Operation Research,1973,(21).
[13]N.Christofides,A.Mingozzi,and P.Toth.Exact Algorithms for the Vehicle Routing Problem,Based on Spanning Trees and Shortest Path Relaxations[J].Math.Programme to appear.
[14]Gilbert Laporte,Helene Mercure and Yves Nobert.A Branch and Bound Algorithm for a Class of Asymmetrical Vehicle Routing Problems[J].J.Opl.Res.Soc,1992,43(5).
[15]Gillert,B.&Miller,L.A heuristic algorithm for the vehicle dispatch problem[J].Operation research.,1974,(22).
[16]张潜.物流配送路径优化渊度建模与实务[M].北京:中国物资出版社,2006.
[17]李军,郭耀煌.物流配送车辆优化调度理论与方法[M].北京:中国物资出版社,2001.
[18]袁庆达.随机库存—运输联合优化问题研究[D].西南交通大学博士学何论文,2001.
[19]薛毅.最优化原理与方法[M].北京:北京工业大学出版社,2001.
[20]Golden.B.L.& Skiscim,C.C.Using simulated annealing to solve routing and locating problem[J].Maval research logistics quarterly,1986,(33).
[21]Tim D.Nguyen.A neural network heuristic for the traveling salesman problem[D].B.S.University of Louisville Docter thesis,2002,(5).
[22]HuangBingXian.Memory Consolidationand Neural Network of the Hipocampus[R].Proc.IntConfNeu～ral Networkxand Signal Processing.Guangzhou,1993.
[23]Held,M.& R.Karp.The Traveling salesman problem and minimum spanning trees[J].Operations Research,1970,(18).
[24]Akaufmann.Integerand Mixed Programming:Theory and Application[M].Academic Press,Inc(London),1982.
[25]Solomon,M.M.Vehicle routing and scheduling with time windows constraints:models and algorithms[R].Ph.D.dissertation,Dept of decision sciences,University of Pennxylvania,1983.
[26]Mole,R.H.& Jameson.A Sequential route building algorithm employing generalized saving criterion[J].Operation Research quarterly,1976,(27).
[27]Herron D.Manging physical distribution for profit[C].Harvard Business Review,1979,(79).
[28]Federgruen A.Zipkin P.A combined vehicle routing and inventory allocation problem[J].Perations Research,1984,32,(5).
[29]马良.旅行推销员问题的算法综述[J].数学的实践与认识,2000,(4).
[30]徐宁,李春光等.几种现代优化算法的比较研究[J].系统工程与电子技术,2002,(12).
[31]张远福,时连强.车辆路径问题(VRP)的一个启发式算法[J].河北建筑科技学院学报,2002(9).
[32]李冰,杜文.单货物品种的运输和存储联合调度问题[J].西南交通大学学报,2003,(12).
[33]汪祖柱,程家兴.求解组合优化问题的一种方法—分枝定界法[J].安徽大学学报(自然科学版),2004,(1).
[34]张莹.运筹学基础[M].北京:清华大学出版社,1995.
[35]Bodin L.Optimization procedures for the analysis of coherent structures[C].IEEE Transaction on Reliability,1969,(18).
[36]Zipkin P.Single ranking methods for allocation of one resource[J].Mannagement Science,1980,(26).
[37]骆义.物流配送车辆调度优化研究[D].大连海事大学硕士学位论文.2003.
[38]袁庆达,杜文.带有时间窗的混合车队车辆路线问题的模型与算法研究[J].西南交通大学学报,2001,(4).
[39]张丽萍,柴跃廷,曹瑞.有时间窗车辆路径问题的改进遗传算法[J].计算机集成制造系统,2002,(6).
[40]冷德惠,张金梅,李大卫.遗传算法在有时间窗车辆路径问题上的应用[J].系统工程理论与实践,1999,(8).
[41]姜大立,杨西龙,杜文,周贤伟.车辆路径问题的遗传算法研究[J].系统工程理论与实践,1999,(6).
[42]Lover F.uture paths for integer programming and links to artifical intelligence[J].Computer and Operations Research,1986,(5).
[43]Xu J.Kelly J P.A network flow～based tabu search heuristic for the vehicle routing problem[J].Transportation Science,1996.(30).
[44]Hooker J.N.Natraj N.R.Solving a general routing and scheduling problem by chain declmposition and tabu search.[J].Transportation Science,1995,(29).
[45]Taillard E.A tabu search heuristic for the vehicle routing problem with soft time windows[J].Transportation Science,1997,(31).
[46]Gendreau M,Hertz A.tabu search heuristic for the vehicle routing problem[J].Management Science,1994,(40).
[47]Gendreau M.etc.A tabu search heuristic for the heterogeneous fleet vehicle routing problem[J].Computer & operations research,1999,(26).
[48]B.Ombuki,M.Nakamura& M.Osamu.A Hybrid Search Based on Genetic Algorithms and Tabu Search for Vehicle Routing[R].Presented at the 6th IASTED international Conference on Artificial Intelligence and Soft Computing,PP.2002,(7).
[49]P.Badeau,M.Gendreau,F.Guertin,J.～Y.Potvin and E.tailard.A Parallel Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows[J].Transportation Research,1997,(5).
[50]刘民.遗传算法方法及其在生产线调度问题中的应用研究[D].清华大学博士论文,1997.
[51]李军,谢秉磊,郭强.非满载车辆调度问题的遗传算法[J].系统工程理论方法应用,2000,(3).
[52]李军.车辆调度问题的分派启发式算法[J].系统工程理论与实践,1999,(1).
[53]谢秉磊,李军,郭耀煌.有时间窗的车辆调度问题的遗传算法[J].系统工程学报,2000,(17).
[54]Balakrishnan,N.Simple heuristics for the vehicle routing problems with soft time windows[J].Journal of operational research society,1993,44(3).
[55]Desrocher,M.Desrosiers,J.& Solomon,M.A new optimization algorithm for the vehicle routing problem with time windows[J].Operations research,1992,40(2).