您的位置:首页  > 论文页面

基于动态规划改进求解VRP问题的节约法的研究

发表时间:2008-01-31  浏览量:1613  下载量:526
全部作者: 张艳
作者单位: 大连海事大学交通工程与物流学院
摘 要: 本文提出了车辆路线优化调度问题(VRP问题)节约法的一种改进方法—动态规划节约法(DSM)。由于节约法的优化过程是一个多阶段决策过程,每个阶段所做决策都影响着未来的可选决策集合,且决策过程不可逆,具备动态规划问题的基本特征。该法利用了VRP问题在优化过程中的动态规划特性,将代表启发式算法的节约法与代表精确算法的动态规划相结合,建立不断增加节约量的动态规划数学模型,使其能够得到全局最优解。一方面解决了传统节约法不能保证得到最优解和求解结果不统一的问题;另一方面又避免了精确算法的计算量膨胀。该法计算过程平稳收敛,对增加约束条件的情况更易接受,具有一定的实用价值。
关 键 词: 交通运输规划与管理;DSM;节约法;VRP;动态规划
Title: Studying of improved Saving method of VRP based on Dynamic programming
Author: ZHANG Yan
Organization: Faculty of Management Engineering, Dalian Vocational Technical College
Abstract: In this paper, a new algorithm named DSM (Dynamic programming Saving Method) is submitted which improving the Saving Method of VRP. The optimization procedure of Saving Method is a multi-stage decision process, decision-making in each stage will always affect the future optional set of support strategy, even the decision procedure is nonreciprocal, it has basic characteristic of dynamic programming. DSM uses the basic characteristic of dynamic programming in the optimization procedure of Saving Method, combines the Saving Method standing in for heuristic approach and dynamic programming standing in for precise algorithmic, and to set up a dynamic programming mathematical model in which the saving value increased continually, so as to find the global optimal solution, which solved the inexactitude problems of couldn’t be assure of finding the precision optimal solution and the skimble-scamble solution, also avoids expanding of calculation. Yet, DSM model accepts increased constraint easily, it can add more filtrate conditions which make the computational procedure converging smoothly. DSM gives a certain practical value to micro midi VRP
Key words: transportation planning and management; DSM; saving method; VRP; dynamic programming
发表期数: 2008年5月第2期
引用格式: 张艳. 基于动态规划改进求解VRP问题的节约法的研究[J]. 中国科技论文在线精品论文,2008,1(2):185-189.
 
0 评论数 0
暂无评论
友情链接