车辆路径问题的车辆路径问题的发展
1959年Dantzig和Ramse首次对闭合式VRP进行了研究，描述的是将汽油送往各个加油站的实际问题，并首次提出了相应的数学规划模型以及求解算法。1964年，Clark和Wright[4]一种对Dantzig-Ramse方法改进的有效的启发式算法Clark-Wright节约算法。正是由于以上两篇开创性论文的发表，使得VRP成为运筹学以及组合优化领域的前沿和研究热点课题。1969年，Christofides和Eilon应用2-opt[5]和3-opt[6]处理车辆路径问题。1970年，提出了两阶段方法求解车辆路径问题，包括先分组后定路线（clusterfirst-route second）和先定路线后分组（routefirst-cluster second）两种启发式策略。1981年，Fisher和Jaikumar提出以数学规划为主的最优化方法来处理包含大约50个顾客点的问题,同样其运算效率是一个亟待解决的问题。同年，Gullen，Jarvis和Ratliff建立了人机互动的启发式方法。1981年，Bodin and Golden将众多的VRP求解方法进行了归纳。分为以下七种：数学解析法（Exact Procedure）；人机互动法（Interactive Optimization）；先分群再排路线（Cluster First–Route Second）；先排路线再分群（Route First–Cluster Second）；节省法或插入法（Saving or Insertion）；改善或交换法（Improvement or Exchanges）；数学规划近似法（Mathematical programming）。1990年以来，人工智能方法在解决组合优化问题上显示出强大功能，在各个领域得到充分应用，很多学者也将人工智能引入车辆路线问题的求解中，并构造了大量的基于人工智能的启发式算法。 禁忌搜索法（TS）基本上是属于一种人工智能型（AI）的局部搜寻方法，Willard首先将此算法用来求解VRP 。袁庆达[7]等设计了考虑时间窗和不同车辆类型的禁忌算法，这种算法主要采用GA方法产生初始解，然后禁忌算法对初始解优化。模拟退火方法具有收敛速度快，全局搜索的特点，Osman[8]对VRP的模拟退火算法进行了研究。遗传算法具有求解组合优化问题的良好特性，Holland首先采用遗传算法（GA）编码解决VRPTW 问题。现在多数学者采用混合策略，分别采用两种人工智能方法进行路线分组和路线优化。Ombuki[9]提出了用GA进行路线分组，然后用TS方法进行路线优化的混合算法。Bent和Van Hentenryck[10]则首先用模拟退火算法将车辆路线的数量最小化，然后用大邻域搜索法（largneighborhood search）将运输费用降到最低。综合过去有关VRP的求解方法，可以将其分为精确算法（exact algorithm）与启发式算法（heuristics），其中精确算法有分支界限法、分支切割法、集合涵盖法等；启发式算法有节约法、模拟退火法、确定性退火法、禁忌搜寻法、基因算法、神经网络、蚂蚁殖民算法等。
车辆路径问题的内容简介
《车辆路径问题(影印版)》内容简介：in the field of combinatorial optimization problems, the vehicle routing problem (vrp) is one of the most challenging. defined more than 40 years ago, the problem involves designing the optimal set of routes for fleets of vehicles for the purpose of serving a given set of customers . interest in vrp is motivated by its practical relevance as well as its considerable difficulty.the vehicle routing problem covers both exact and heuristic methods developed for the vrp and some of its main variants, emphasizing the practical issues common to vrp. the book is composed of three parts containing contributions from well-known experts. the first part covers basic vrp, known more commonly as capacitated vrp. the second part covers three main variants of vrp: with time windows, backhauls, and pickup and delivery. the third part covers issues arising in real-world vrp applications and includes both case studies and references to software packages.this book will be of interest to both researchers and graduate-level students in the communities of operations research and mathematical sciences. it focuses on a specific family of problems while offering a complete overview of the effective use of the most important techniques proposed for the solution of hard combinatorial problems. practitioners will find this book particularly useful.reader need a basic knowledge of the main methods for the solution of combinatorial optimization problems.
想问一下什么是vrp问题，什么是tsp问题？
、旅行商问题（TRAVELING SALESMAN PROBLEM, TSP） 这个问题字面上的理解是：有一个推销员，要到N个城市推销商品，他要找出一个包含所有N个城市的具有最短路程的环路。 TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。 TSP由美国RAND公司于1948年引入，该公司的声誉以及线性规划这一新方法的出现使得TSP成为一个知名且流行的问题。 2、中国邮递员问题（CHINESE POSTMAN PROBLEM CPP） 同样的问题，在中国还有另一个描述方法：一个邮递员从邮局出发，到所辖街道投递邮件，最后返回邮局，如果他必须走遍所辖的每条街道至少一次，那么他应如何选择投递路线，使所走的路程最短？这个描述之所以称为中国邮递员问题， 因为是 国学者管梅古谷教授于1962年提出的这个问题并且给出了一个解法。 3、“一笔画”问题（DRAWING BY ONE LINE） 还有一个用图论语言的描述方式：平面上有N个点，用最短的线将全部的点连起来。称为“一笔画”问题。 4、配送路线问题（ROUTE OF DISTRIBUTION） TSP问题在物流中的描述是对应一个物流配送公司，欲将N个客户的订货沿最短路线全部送到。如何确定最短路线。 TSP问题最简单的求解方法是枚举法。它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间，搜索空间是N个点的所有排列的集合，大小为（N-1）！。可以形象地把解空间看成是一个无穷大的丘陵地带，各山峰或山谷的高度即是问题的极值。求解TSP，则是在此不能穷尽的丘陵地带中攀登以达到山顶或谷底的过程。 5、多回路运输问题（VEHICLE ROUTING PROBLEM, VRP） 多回路运输问题在物流中的解释是对一系列客户的需求点设计适当的路线，使车辆有序地通过它们，在满足一定的约束条件下，如货物需求量、发送量、交发货时间、车辆载重量限制、行驶里程限制、时间限制等等，达到一定的优化目标，如里程最短、费用最少、时间最短，车队规模最少、车辆利用率高。 VRP问题和TSP问题的区别在于：客户群体的数量大，只有一辆车或一条路径满足不了客户的需求，必须是多辆交通工具以及运输工具的行车顺序两个问题的求解。相对于TSP问题，VRP问题更复杂，求解更困难，但也更接近实际情况。 6、多个旅行商问题（MULTIPLE TSP） 由于限制条件的增加，TSP问题可以衍生出多个旅行商问题（MTSP），就是一个出发点，M个旅行商的TSP，即所访问的客户没有需求，车辆没有装载的限制，优化目标就是要遍历所有的客户，达到总里程最短。 VRP问题是MTSP问题的普遍化，当客户的需求不仅仅是被访问，而是有一定容积和重量的商品的装载和卸载，涉及到不同种类和型号或不同载重量车辆的调度策略时，MTSP问题转换为VRP问题。 7、最近邻点法（NEAREST NEIGHBOR） 这是一种用于解决TSP问题的启发式算法。方法简单，但得到的解并不十分理想，可以作为进一步优化的初始解。求解的过程一共四步：首先从零点开始，作为整个回路的起点，然后找到离刚刚加入到回路的上一节点最近的一个节点，并将其加入到回路中。重复上一步，直到所有的节点都加入到回路中，最后，将最后一个加入的节点和起点连接起来，构成了一个TSP问题的解。 8、最近插入法（NEAREST INSERTION） 最近插入法是另一个TSP问题的求解方法。它的求解过程也是4步：首先从一个节点出发，找到一个最近的节点，形成一个往返式子回路；在剩下的节点中，寻找一个离子回路中某一节点最近的节点，再在子回路中找到一个弧，使弧的两端节点到刚寻找到的最近节点的距离之和减去弧长的值最小，实际上就是把新找到的节点加入子回路以后使得增加的路程最短，就把这个节点增加到子回路中。重复以上过程，直到所有的节点都加入到子回路中。最近插入法比最近邻点法复杂，但可以得到相对比较满意的解。 9、节约里程法（SAVING ALGORITHM） 节约算法是用来解决运输车辆数目不确定的VRP问题的最有名的启发式算法。它的核心思想是依次将运输问题中的两个回路合并为一个回路，每次使合并后的总运输距离减小得幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。优化过程分为并行方式和串行方式两种。 10、扫描算法（SWEEP ALGORITHM） 它也是求解车辆数目不限制的VRP问题的启发式算法。求解过程同样是4步：以起始点为原点建立极坐标系，然后从最小角度的两个客户开始建立一个组，按逆时针方向将客户逐个加入到组中，直到客户的需求总量超出了车辆的载重定额。然后建立一个新的组，继续该过程，直到将全部客户都加入到组中 记得采纳啊