VRP的求解方法及优化算法综.pdf

《VRP的求解方法及优化算法综.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、商业文化·学术探讨2007年7月VRP的求解方法及优化算法综刘静（西安交通大学经济与金融学院，西安，710061）中图分类号：U492.22文献标识码：A文章编号：1006—4117（2007）07—0225—01车辆路径问题（VehicleRoutingProblem，VRP）是1959这些传统启发式算法是人类智能的结晶，能够较好的年由Dantzig和Ramser提出的，是指在客户需求位置已知解决顶点数较少的VRP问题。但是，随着顶点数的增加，的情况下，确定车辆在各个客户间的行程路线，使得运输计算量增加较快，因此应用受到了一定的限制。路线最短或运输成

2、本最低，通过研究车辆路径问题可以合（三）智能优化算法理使用调运工具，优化运输路线，降低企业物流成本。进入20世纪80年代，一些新颖的优化算法，如遗传VRP已被研究证实为NP难题，它的求解算法也非常算法、模拟退火算法、禁忌搜索算法、蚁群算法、混沌随丰富，不过究其实质，基本上可分为精确算法、传统启发机搜索算法等，通过揭示或模拟自然现象或过程得到发展，式算法和智能优化算法三类。为解决复杂问题提供了新的思路和手段。在优化领域，由（一）精确算法于这些算法构造的直观性与自然机理，因而被称为智能优精确算法是针对VRP图模型和数学模型的求解方法。化算法或现代启发式算法

3、。目前最引人注目的智能优化算其代表性的算法有单纯形法、割平面法、分支定界法、隐法，主要有三种，即模拟退火法（SimulatedAnnealing，SA）、枚举法、动态规划、整数规划和列生成技术法等。1949年禁忌搜索算法（TabuSearch，TS）和遗传算法（GeneticDantzig提出了著名的求解线性规划问题的单纯形法，可以Algorithm，GA）。解决整数规划中的运输问题。1958年Gomory提出了著名1975年，美国密歇根大学J.H.Holland教授发表专著的割平面法求解线性规划。Land和Doing于1960年开发了《Adaptat

4、ioninNaturalandArtificialSystems》标志着GA的分支定界法，1960年Balas提出隐枚举法求解0-1整数规划。创立，它是一种基于生物体进化机制而建立起来的算法。1988年Fisher提出了K-树法。1991年M.Padberg等提出了D.Goldberg博士的《GeneticAlgorithminSearch著名的分枝剪枝法。1995年Christofides等用动态规划放宽OptimizationandMachineLearning》一书对GA的发展历史、空间变量解决VRP。2000年Fumero等提出了修正的拉格现状

5、、各种算法及在实际工程中的应用作了详细的阐述。朗日松弛及子梯度优化方法。2004年LorenaLuiz等对列生GA的基本原理是通过多个个体间的选择、交叉、变异等操成方法的改进等。作对解空间进行搜索。GA对于解诸如带有时间窗的VRP，精确算法有着悠久的发展历史，其最大的优点是能够取得了很好的效果。算法所得结果的好坏，主要依赖于遗找到问题的全局最优解。但是过于拘泥于数学抽象，并且传代数和解组的规模，在实际应用若所得解不能令人满意，计算量一般随问题规模的增大呈指数增长，因此在应用中就要增大解组规模或遗传代数，而这是以延长计算时间为仅适合求解规模较小的VRP。

6、代价的。（二）传统启发式算法1983年，Kirkpatrick等提出了求解组合最优化问题的对于VRP这种强NP难题，高效的精确算法几乎不存SA，它是模拟对金属进行加热处理的退火过程。该方法将在，所以寻找近似算法是必要的，启发式算法成为解决该路径规划的目标函数视作能量函数，模仿物理学中固体物问题最有效的一种途径。所谓启发式算法(Heuristic质的退火处理，先加温使之具有足够高的能量，然后再逐Algorithms)，是指运用一些经验法则来降低优化模型的数渐降温，其内部能量也相应下降，在热平衡条件下，物体学精确度，通过模仿人的跟踪校正过程求取物流系统的满

7、内部处于不同状态的概率服从Boltzmann分布，若退火步意解的数学方法。骤恰当，则最终会形成最低能量的基态。这种算法在求解目前已经提出的启发式算法有很多，如基于数学规划路径规划问题时，不但接受对目标函数有改进的状态，还的方法、改进-交换法、节约插入法、先分组后安排路线的以某种概率接受使目标函数恶化的状态，从而可使之避免方法、先安排路线后分组的方法等。其中最具代表性的就过早收敛到某个局部极值点，也正是这种概率性的扰动能是由Clarke和Wright在1964年提出的节约法。1965年由够使之跳出局部极值点，故而得到全局最优解。Lin和Kemighan提

8、出的，并由Christofides和GilbertLaporte1986年，F.Glove最早