车辆路径问题指的是什么意思（什么是车辆路径问题)-外贸知识大全网

摘要：车辆路径问题指的是什么意思（什么是车辆路径问题) 你真的知道车辆路径问题吗？你知道多少？以下是爱68为您整理车辆路径问题的相关知识，让您更深入地了解什么是车辆路径问题。那么，车辆路径问题在公路运输行业代表什么呢？让我们一起看看。车辆路径问题（Vehicle Routing Problem,VRP）目录 1 &...

车辆路径问题指的是什么意思（什么是车辆路径问题)

你真的知道车辆路径问题吗？你知道多少？以下是爱68为您整理车辆路径问题的相关知识，让您更深入地了解什么是车辆路径问题。那么，车辆路径问题在公路运输行业代表什么呢？让我们一起看看。

车辆路径问题（Vehicle Routing Problem,VRP）

车辆路径问题是什么？

车辆路线问题（VRP）最早是由Dantzig和Ramser于1959年首次提出，它是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。

这个定义不难看出旅行者的问题（Traveling Saleman Problem,TSP）是VRP因为Gaery已证明TSP问题是NP所以，VRP也属于NP难题。

自1959年提出以来，车辆路线问题一直是网络优化中最基本的问题之一。由于其广泛的应用和重大的经济价值，它一直受到国内外学者的广泛关注。车辆路线问题可描述如下（如图1所示）：

车辆路径问题指的是什么意思（什么是车辆路径问题)-图1

设有一场站（depot），共有M 卡车，车辆容量为Q，有N位顾客（customer），每个客户都有自己的需求D。车辆从车站出发，为客户提供配送服务，最后返回车站，要求所有客户配送，每位客户一次完成配送，不得违反车辆容量限制。目的是尽量减少所有车辆路线的总距离。车辆路线的实际问题包括配送中心配送、公交路线制定、信件报纸配送、航空铁路时间表安排、工业废物收集等。

车辆路径问题类型

一般来说，车辆路线问题可分为以下三种类型（Ballou，1992）：

1.不同的单一起点和单一终点。

2.单个起点和终点相同。

3.多个起点和终点。

车辆路径问题的方法

有许多关于车辆路线问题的学术研究文献，也提出了相当多的求解策略和方法，Bodin and Golden(1981)将多种求解方法归纳为以下七种:

数学解析法（Exact Procedure）；
人机互动法（Interactive Optimization）；
先分组再排路线（Cluster First–Route Second）；
先排路线再分组（Route First–Cluster Second）；
节约法或插入法（Saving or Insertion）；
改进或交换法（Improvement or Exchanges）；
近似法的数学规划（Mathematical programming）。

车辆路线问题研究现状

经过几十年的研究和发展，车辆路线问题的研究取得了很大的成果。以下从车辆路线问题的现有研究模式和解决方案两个方面介绍了车辆路线问题的研究现状。

车辆路线问题型态

基本车辆路线问题（VRP）在此基础上，车辆路线问题在学术研究和实际应用中产生了许多不同的延伸和变化，包括时窗限制车辆路线问题（vehicle routing problems with time windows，VRPTW）、追求最佳服务时间的车辆路线问题（VRPDT）、多车种车辆路线问题（fleet size and mix vehicle routing problems，FSVRP）、多次使用车辆的车辆路线问题（vehicle routingproblems with multiple use of vehicle，VRPM）、考虑收集的车辆路线（vehicle routingproblems with backhauls，VRPB）、随机车辆路线问题（vehicle routing problem with stochastic demand，VRPSD）等。

求解方法

1.解决方法的演进

结合过去对车辆路线问题的解决方法，可分为精确算法（exact algorithm）和启发式解法（heuristics），精密算法包括分支边界法、分支切割法、***覆盖法等。启发式解决方案包括节约法、模拟退火法、确定性退火法、禁忌搜索法、基因算法、神经网络、蚂蚁殖民算法等。1995年，Fisher将解决车辆路线问题的算法分为三个阶段。第一阶段是从1960年到1970年，它是一种简单的启发方式，包括各种局部改进启发算法和贪婪法（Greedy）等等；第二阶段是从1970年到1980年，它是一种基于数学规划的启发性解决方案，包括分配法、***分割法和***涵盖法；第三阶段是自1990年以来的一种新方法，包括使用严格的启发法、人工智能法等。

2.启发算法

由于VRP是NP-hard问题很难用精确的计算来解决。启发算法是解决车辆运输问题的主要方法。多年来，许多学者研究了车辆运输问题，并提出了各种启发方法。车辆运输问题的启发方法可分为简单启发算法、两阶段启发算法和人工智能方法。

简单的启发方法包括节省法或插入法、路线/间节点交换法、贪婪法和局部搜索法。节省法或插入法（savings or insertion）在求解过程中，采用节约成本的最可行方式构建路线，直至无法节约。交换规则是依靠其他方法生成起始路线，然后通过迭代减少路线距离，直到无法改善。1960年，Clarke和Wright首先，提出启发性节约法（savings methods）建立团队配送路线。简单的启发方法简单易懂，求解速度快，但只适合求解小而简单VRP问题。

两阶段的方法包括先分组后定路线（clusterfirst-route second）先定路线后分组（routefirst-cluster second）两种启发式策略。前者是先将所有需求点大略分为几个组，然后再对各个组分别进行路线排序；后者则是先将所有的需求点建构成一条路线，再根据车辆的容量将这一路线分割成许多适合的单独路线。

自1990年以来，人工智能方法在解决组合优化问题方面发挥了强大的作用，并在各个领域得到了充分的应用。许多学者还将人工智能引入了车辆路线问题的解决方案，并构建了大量基于人工智能的启发性算法。禁止搜索方法（TS）基本属于人工智能型（AI）局部搜索方法，Willard首先，该算法用于解释VRP ，随后，许多学者也发表了求解VRP的TS 算法。西南交通大学的袁庆达设计了考虑时间窗口和不同车辆类型的禁忌算法，该算法主要采用GENIUS该方法产生初始解，然后禁忌算法优化初始解。模拟退火方法具有收敛速度快、全局搜索的特点，Osman对VRP研究了模拟退火算法，他提出的模拟退火方法主要适用于解决路线分组。遗传算法具有解决组合优化问题的良好特点，Holland首先采用遗传算法（GA）编码解决VRPTW 问题。现在大多数学者采用混合策略，路线分组和路线优化分别采用两种人工智能方法。Ombuki提出了用遗传算法分组路线，然后用禁忌搜索方法优化路线的混合算法。Bent和Van Hentenryck先用模拟退火算法将车辆路线数量最小化，再用大邻域搜索法（largneighborhood search）尽量减少运输成本。

总结几种人工智能方法，TS算法获得的解最接近最优解，但其计算时间也最长GA算法的2~3倍，SA算法的近20倍；因为GA算法也能更好地接近最优解，大大缩短操作时间，因此GA算法可以兼顾计算时间和效率，是一种发展前景良好的方法；SA算法求解速度非常快，也能在一定程度上提供优化方案，求解小规模问题上有很好的效果。

参考文献

↑ Paolo Toth，Daniele Vigo。THE VEHICLE ROUTING PROBLEM。Society for Industrial and Applied Mathematics philadephia.2002
↑ 朱崇军，刘民，吴澄.供应链中车辆路径问题的研究进展和前景.计算机集成制造系统-CMS.2001,7(11):1-6
↑ 邱志鸿.物流配送中心货车路线问题研究
↑ 张强、荆刚、陈建岭.研究车辆路线的现状和发展方向.2004年(1)交通技术:60-62
↑ Fisher M L，Vehicle Routing．Handbooks in Operations Research ＆ Management Science Vol 8，1995.1～33
↑ Clarke G，Wright J．Sche***ng of vehicles from central depot to a number of delivery points.Operations Research,1964,12:568～581
↑ 袁庆达、闫昱、周再玲Tabu Search算法在优化配送路线中的应用.2001(11)计算机工程:86~89
↑ Osman I H.Meta-strategy simulatedannealing an Tabu search algorithms for the vehicle routin problem.Annu Oper Res,1993,41:77～86
↑ Ombuki.B M，Nakamura M，Osamu M．Ahybri search based on genetic algorithm s and tabu search for vehicle routing.Brock University T echnica Report:#CS-02-07,2002,5:1～7
↑ R .Bent and P.Van Hentenryck.A two-stage hybri local search for the vehicle routing problem with tim windows.Technical Report,CS-01-06,Brown University,2001,9:1～30

车辆路径问题指的是什么意思（什么是车辆路径问题)

车辆路径问题指的是什么意思（什么是车辆路径问题)发表于2022-06-29，由周林编辑，文章《车辆路径问题指的是什么意思（什么是车辆路径问题)》由admin于2022年06月29日发布于本网，共4253个字，共5106人围观，目录为公路运输，如果您还要了解相关内容敬请点击下方标签，便可快捷查找与文章《车辆路径问题指的是什么意思（什么是车辆路径问题)》相关的内容。