车辆路径问题(Vehicle Routing Problem，VRP )什么是车辆路径问题
所谓车辆路线问题(VRP )，就是一定数量的客户各有不同数量的货物需求，配送中心为客户提供货物，一个团队负责配送货物，组织合适的行驶路线，满足客户的需求，在一定的约束下，比如路程的最短化、可可
旅行社问题(Traveling Saleman Problem，TSP )是VRP的特例，TSP问题是NP-hard问题，因此VRP也属于NP-hard问题。
车辆路线问题一直是网络优化问题中最基本的问题之一，由于其应用的广泛性和经济上的重要价值，受到国内外学者的广泛关注。 车辆路线的问题可以记述如下(图1 )。
有工位(depot )，共有m辆卡车，车辆容量为q，有n名顾客)，每个顾客有需求量d。 车辆从入场站出发为客户提供配送服务，最后返回入场站，要求所有客户配送，每位客户一次配送完毕，且不得违反车辆容量限制。 目的是所有车辆路线的总距离最小。 车辆路线的实际问题包括配送中心的配送、巴士路线的制定、信件和报纸的配送、航空和铁路的时间表的安排、工业废弃物的收集等。
车辆路径问题的类型
一般来说，车辆路线的问题大致可分为以下三种类型。
1、不同的单一起点和单一终点。
2、同一个单一的开始和终点。
3、多个起点和终点。
车辆路径问题的方法
关于车辆路线问题的学术研究文献很多，也提出了相当多的解决方案和方法。 Bodin and Golden(1981将多种解决方法归纳为以下7种。
解析法(Exact Procedure ) )。
交互式优化)。
分组后再安排课程(cluster firstroute second ) ) ) ) ) ) ) ) )。
先排列课程，然后将其分成组(route firstclustersecond ) )。
节约法或插入法(Saving or Insertion )
或改进交换方法(Improvement or Exchanges )
数学规划近似法(Mathematical programming )。
车辆路线问题型态
在基本车辆路线问题(VRP )的基础上，车辆路线问题在学术研究和实际应用中产生了许多不同的扩展和变化类型。 包括以下内容。
时窗限制车辆路线问题(vehicleroutingproblemswithtimewindows，VRPTW ) ) ) ) ) )。
追求最佳服务时间的车辆路线问题(VRPDT ) )。
多车型车辆路线问题(fleetsizeandmixvehicleroutingproblems，FSVRP ) ) ) ) ) ) )。
车辆多次使用的车辆路线问题(vehicleroutingproblemswithmultipleuseofvehicle，VRPM ) ) ) ) ) ) ) ) )。
考虑收集到的车辆路线问题(vehicleroutingproblemswithbackhauls，VRPB )
随机需求车辆路线问题(vehicleroutingproblemwithstochasticdemand，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算法求解速度非常快，也能提供一定程度上的优化方案在求解较小规模问题上具有较好效果。
本文转自：车辆路径问题-MBA智库