VRP的求解
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
及优化算法综商业文化·学术探讨2007年7月225VRP的求解方法及优化算法综刘静（西安交通大学经济与金融学院，西安，710061）中图分类号：U492.22文献标识码：A文章编号：1006—4117（2007）07—0225—01车辆路径问题（VehicleRoutingProblem，VRP）是1959年由Dantzig和Ramser提出的，是指在客户需求位置已知的情况下，确定车辆在各个客户间的行程路线，使得运输路线最短或运输成本最低，通过研究车辆路径问题可以合理使用调运工具，优化运输路线，降低企业物流成本。VRP已被研究证实为NP难题，它的求解算法也非常丰富，不过究其实质，基本上可分为精确算法、传统启发式算法和智能优化算法三类。（一）精确算法精确算法是针对VRP图模型和数学模型的求解方法。其代
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
性的算法有单纯形法、割平面法、分支定界法、隐枚举法、动态规划、整数规划和列生成技术法等。1949年Dantzig提出了著名的求解线性规划问题的单纯形法，可以解决整数规划中的运输问题。1958年Gomory提出了著名的割平面法求解线性规划。Land和Doing于1960年开发了分支定界法，1960年Balas提出隐枚举法求解0-1整数规划。1988年Fisher提出了K-树法。1991年M.Padberg等提出了著名的分枝剪枝法。1995年Christofides等用动态规划放宽空间变量解决VRP。2000年Fumero等提出了修正的拉格朗日松弛及子梯度优化方法。2004年LorenaLuiz等对列生成方法的改进等。精确算法有着悠久的发展历史，其最大的优点是能够找到问题的全局最优解。但是过于拘泥于数学抽象，并且计算量一般随问题规模的增大呈指数增长，因此在应用中仅适合求解规模较小的VRP。（二）传统启发式算法对于VRP这种强NP难题，高效的精确算法几乎不存在，所以寻找近似算法是必要的，启发式算法成为解决该问题最有效的一种途径。所谓启发式算法(HeuristicAlgorithms)，是指运用一些经验法则来降低优化模型的数学精确度，通过模仿人的跟踪校正过程求取物流系统的满意解的数学方法。目前已经提出的启发式算法有很多，如基于数学规划的方法、改进-交换法、节约插入法、先分组后安排路线的方法、先安排路线后分组的方法等。其中最具代表性的就是由Clarke和Wright在1964年提出的节约法。1965年由Lin和Kemighan提出的，并由Christofides和GilbertLaporte人推广的分支交换探索法。1971年，英国学者Wren在其一本名为《ComputersinTransportPlanningandOperation》的书提及一种扫描算法。该算法后经Gillett和Miller(1974)加以推广。1981年Fisher和Jaikumar提出了另一种先分组后安排路线的Fisher-Jaikumar算法。Bramel和Simchi-Levi在两人研究的基础上，于1995年提出了一种两阶段启发式方法，将先分组后安排路线的问题彻底加以解决。这些传统启发式算法是人类智能的结晶，能够较好的解决顶点数较少的VRP问题。但是，随着顶点数的增加，计算量增加较快，因此应用受到了一定的限制。（三）智能优化算法进入20世纪80年代，一些新颖的优化算法，如遗传算法、模拟退火算法、禁忌搜索算法、蚁群算法、混沌随机搜索算法等，通过揭示或模拟自然现象或过程得到发展，为解决复杂问题提供了新的思路和手段。在优化领域，由于这些算法构造的直观性与自然机理，因而被称为智能优化算法或现代启发式算法。目前最引人注目的智能优化算法，主要有三种，即模拟退火法（SimulatedAnnealing，SA）、禁忌搜索算法（TabuSearch，TS）和遗传算法（GeneticAlgorithm，GA）。1975年，美国密歇根大学J.H.Holland教授发表专著《AdaptationinNaturalandArtificialSystems》标志着GA的创立，它是一种基于生物体进化机制而建立起来的算法。D.Goldberg博士的《GeneticAlgorithminSearchOptimizationandMachineLearning》一书对GA的发展历史、现状、各种算法及在实际工程中的应用作了详细的阐述。GA的基本原理是通过多个个体间的选择、交叉、变异等操作对解空间进行搜索。GA对于解诸如带有时间窗的VRP，取得了很好的效果。算法所得结果的好坏，主要依赖于遗传代数和解组的规模，在实际应用若所得解不能令人满意，就要增大解组规模或遗传代数，而这是以延长计算时间为代价的。1983年，Kirkpatrick等提出了求解组合最优化问题的SA，它是模拟对金属进行加热处理的退火过程。该方法将路径规划的目标函数视作能量函数，模仿物理学中固体物质的退火处理，先加温使之具有足够高的能量，然后再逐渐降温，其内部能量也相应下降，在热平衡条件下，物体内部处于不同状态的概率服从Boltzmann分布，若退火步骤恰当，则最终会形成最低能量的基态。这种算法在求解路径规划问题时，不但接受对目标函数有改进的状态，还以某种概率接受使目标函数恶化的状态，从而可使之避免过早收敛到某个局部极值点，也正是这种概率性的扰动能够使之跳出局部极值点，故而得到全局最优解。1986年，F.Glove最早提出了TS，几乎同时P.Hansen也作了类似的研究。TS是一种全局逐步寻优算法，所谓禁忌就是禁止重复前面的工作，具有记忆功能是TS独创的特点。该算法的思想是首先按照随机方法产生一个初始解作为当前解，然后在当前解的邻域中搜索若干个解，取其中最好的解作为新的当前解。由于TS使用了记忆，在搜索过程中可以接受劣解，这使得TS在搜索过程中能够跳出局部最优解，从而使获得全局最优解的概率大大增加。
浙公网安备 33021202002483