车辆路径问题与相关算法总结

　　车辆路径优化是解决物流中运输环节效率问题的方案和方法。最近在学习车辆路径优化问题，这个问题虽然很普遍，但是没有一篇文章能够让我对问题有个全面的了解，尤其是解决方法，需要查阅很多论文才能整理全，经过一段时间的整理，把一些要点给写了下来。 　　车辆路径问题存在很长时间了，经过多代人的研究，目前在算法上已经比较成熟。但是由于各种限制，我国在物流领域还没有大规模的应用，这可能跟我国的信息化水平有关；首先因为算法对数据要求比较高，目前我国还有很多物流企业处在信息化的初级阶段，数据的及时性和有效性还不能很好的保证。因为篇幅有限本文只是做一个抛砖引玉，简要介绍下车辆路径问题的主要解决思路，文中的算法只做简要说明，有兴趣的朋友可以深入研究。 　　问题描述 　　车辆路径问题（Vehicle Routing Problem, VRP）, 车辆路线问题最早是由Dantzig和Ramser于1959年首次提出，它是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。 　　VRP属于组合优化问题，在有限个可行解集合中找出最优解，这类问题称为组合优化问题，是指在离散的、有限的数学结构上，求满足给定约束条件的目标函数最优值（最大值或最小值）的问题，也称离散优化问题，该类问题都与顺序有关。 　　车辆路径问题作为运筹学和组合优化领域的热点问题，与现实生活息息相关。是运筹学、管理学、计算机应用、组合数学、图论等学科的组合优化问题。 　　问题模型 　　VRP在算法层面可以抽象为有向图、无向图、连通图、网络图等图类问题的求解。物流中的运输路线图中每个点代表着城市、集货点、仓库等，点与点间的连线代表两个城市间的路线（公路、铁路、航空、水运），显然这只是一个示意图，而不是真实的交通图，但它能清楚的反应各个节点之间的联通关系。有向图说明道路是非对称的，是单向的，无向图代表道路是双向的。 　　VRP属于NP问题，Nondeterministic Polynomial即非决定性多项式算法能够解决的问题；解决这类问题的方法有很多，主要的是启发式算法。 　　按照判定问题的复杂性对最优化问题进行分类。问题复杂性的形式定义可用图灵机(Turing Machine)计算模型给出。如果一个问题有解它的多项式时间DTM(确定型图灵机)程序，则称该问题属于P类。P类问题表示多项式算法所能解决的判定问题类。如果一个问题有解它的多项式时间NTM（非确定型图灵机）程序，则称该问题属于NP类。NP类问题是指可在多项式时间内检测的问题类，至今尚未找到多项式时间算法。 　　对于一个NP类问题，并不要求它的每个实例都能用某个算法在多项式的时间内得到回答，只要求，如果x是问题的答案为“是”的实例，在存在对x的一个简短（即起长度以x的长度的多项式为界）证明，使得能在多项式时间内检验这个证明的真实性。 　　基本问题 　　VRP问题是一个组合优化问题，可以分解为各种不同的基本问题进行求解，对基本问题的了解有助于了解VRP问题的求解过程。主要有如下几种问题类型： 　　最小生成树 　　最小生成树问题是运筹学、图论的基本问题之一，它可以直接或间接的用来设计运输网络，在处理复杂问题是常常起着重要的作用。 　　定义：一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。 　　如果图T是图G的一个生成子图，而且又是一棵树，则称树T是图G的一个生成树，显然，图的生成树不唯一。一棵生成树上所有树枝上权的总和，称为这个这个生成树的权。具有最小权的生成树成为最小生成树，简称最小树。 　　解决方法： 　　丢表发（破圈法）：在连通无向图G中，任取一个圈，将该圈中权最大的一条边（如有两条或两条以上这样的彼边，可任取其一）去掉；在余下的圈中重复这一步骤，直到不含圈为止，就得到了最小树。 　　加边法（避圈法）：对含有n个点的连通无向图G,从其所有边中选出一条权最小的边，并把它纳入树中；在余下的未选边中，再选出一条权最小且与已选入树中的边不构成圈的边，将其纳入树中；如此重复，直到树中含有n-1条边为止，这就构成了最小树。 　　最短路问题 　　最短路问题可以直接用来解决许多生产实际问题，例如管道铺设、线路安排、厂区布局、设备更新等。另外，诸如运价最小、运行时间最短、最可靠路等问题，都可能转化为最短路问题加以解决。 　　最短路问题（short-path problem）是网络理论解决的典型问题之一，可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。基本内容是：若网络中的每条边都有一个数值（长度、成本、时间等），则找出两节点（通常是源节点和阱节点）之间总权和最小的路径就是最短路问题。 　　问题分类 　　指定点间的最短路问题：又分为所有有向边的权大于零的情形和具有负权的最短路问题任意点对间的最短路问题 　　问题求解 　　优化矩阵算法Floyd算法 　　最大流问题 　　在日常生活和工程技术以及科学管理中，经常会遇到一些问题，需要研究网络的流量，例如供水系统中的水流、交通系统中的车流、金融系统中的现金流、控制系统中的信息流等，即流过网络的物质流、能量流或信息流。在确定的网络中，人们常常需要确定该网络中能通过的最大流量，以判断设备的充分利用程度，这就是最大流问题。 　　最大流问题(maximum flow problem)，一种组合最优化问题，就是要讨论如何充分利用装置的能力，使得运输的流量最大，以取得最好的效果。求最大流的标号算法最早由福特和福克逊与与1956年提出，20世纪50年代福特(Ford)、(Fulkerson)建立的“网络流理论”，是网络应用的重要组成成分。 　　问题求解之标号算法： 从可行流和可增广链关系来看，就可以知道一种寻求最大流的方法：从一个可行流开始，寻求关于这个可行流的可增广链，若存在，则可以经过调整，得到一个新的可行流，其流量比原来的可行流要大，重复这个过程，直到不存在关于该流的可增广链时就得到了最大流。这种算法由Ford 和 Fulkerson于1956年提出，故又称 　Ford-Fulkerson标号法。 　　最小费用流问题 　　网络也可以看作是输送一般货物的运输网络，此时最大流问题仅仅表明运输网络运输货物的能力，但没有考虑运送货物的费用。由于在实际问题中，运送同样流量的货物的运输方案可能有多个，从中寻找一个运输费用最小的方案是一个重要的问题。在网络中实现某一输送任务时，流在网络中的分配不同，所花的代价也不同，如何在完成输送任务的前提下所花的费用最低，这是最小费用流问题。 　　最小费用流问题(minimum - costlow pro - blem)一种组合最优化问题.对给定网络D- (V,A,C)，在弧集A上定义非负函数6，对a E A, c 　　中国邮递员问题 　　管梅谷教授与1962年提出，一般定义为邮递员从邮局出发经过他所管辖的街道、巷子完成信件、报纸的投递任务以后返回邮局，要求邮递员经过的各条街道至少一次，如何安排邮递员的行走路线，才能使总路程最短等。 　　旅行商问题 　　旅行商问题（Traveling Salesman Problem, TSP)是一个典型的NP问题，一般描述为：旅行商从驻地出发，经过所要去的城市至少一次返回原地，应该如何安排起旅行线路，才能使总的旅行距离（时间、费用等）最短。对于现实问题，由于限制条件的增加，TSP可衍生出许许多多相关的问题。 　　问题求解： 　　线路构造法 　　节约算法最邻近法最小生成树法几何启发式算法最近插入法最节约插入算法凸集插入算法非对称距离的TSP构造算法 　　线路改进法 　　2 - 交换3 - 交换or - 交换 　　综合法 　　将几种方法联合起来应用 　　VRP问题分类 　　VRP问题按照不同的约束可以问题如下几类： 　　Basic VRP, 基本VRPCVRP: Capacitated Vehicle Routing Problem, 能力约束的VRPVRPTW: VRP with Time Window, 有时间窗的VRPVehicleRouting Problem with precedence Constraints，优先约束的VRPVRP with Backhauls (Deliveries first), 带回程的VRP(投递优先)VRP with Backhauls (mixed Pickups and Deliveries),带回程的VRP(捡获和送货结合)Multiple Depot VRP, 多仓储的VRPVRP with Heterogeneous Fleet: 多车辆车型VRP VehicleRouting Problem with Compatibility Constraints，相容性约束VRPOpen VRP: 开放回路VRPTime Dependent VRP: 基于时序变化的VRPDynamic VRP: 动态VRP 　　精确求解方法 　　分枝界限法(Branch and Bound Approach) 　　分枝界限法是由三栖学者查理德·卡普（Richard M.Karp）在20世纪60年代发明，成功求解含有65个城市的旅行商问题，创当时的记录。“分枝界限法”把问题的可行解展开如树的分枝，再经由各个分枝中寻找最佳解。 　　分枝界限法也能够使用在混合整数规划问题上，其为一种系统化的解法，以一般线性规划之单形法解得最佳解后，将非整数值之决策变量分割成为最接近的两个整数，分列条件，加入原问题中，形成两个子问题(或分枝)分别求解，如此便可求得目标函数值的上限（上界）或下限（下界），从其中寻得最佳解。 　　割平面法(Cutting Planes Approach) 　　割平面法是1958年由美国学者高莫利(R.E.GoMory)提出的求解全整数规划的一种比较简单的方法。其基本思想和分枝定界法大致相同，即先不考虑变量的取整约束，用单纯形法求解相应的线性规划。如果所得的最优解为整数解，那么它也是原整数规划问题的最优解3如果最优解不是整数解，那么分枝定界法是任取一个取分数值的变量Xk = bk将原整数规划分成两枝，其实质是用两个垂直于坐标轴的平行平面Xk = [bk]和Xk = [bk] + 1将原可行域R分成两个可行域R1和R2，并将两个平行平面之间的不含有整数解的那一部分可行域去掉，以缩小可行域。 　　网络流算法(Network Flow Approach) 　　图论中的一种理论与方法，研究网络上的一类最优化问题 。1955年 ，T.E.哈里斯在研究铁路最大通量时首先提出在一个给定的网络上寻求两点间最大运输量的问题。1956年，L.R. 福特和 D.R. 富尔克森等人给出了解决这类问题的算法，从而建立了网络流理论。所谓网络或容量网络指的是一个连通的赋权有向图 D= （V、E、C） ， 其中V 是该图的顶点集，E是有向边(即弧)集，C是弧上的容量。此外顶点集中包括一个起点和一个终点。网络上的流就是由起点流向终点的可行流，这是定义在网络上的非负函数，它一方面受到容量的限制，另一方面除去起点和终点以外，在所有中途点要求保持流入量和流出量是平衡的。如果把下图看作一个公路网，顶点v1…v6表示6座城镇，每条边上的权数表示两城镇间的公路长度。现在要问 ：若从起点v1将物资运送到终点v6去 ，应选择那条路线才能使总运输距离最短?这样一类问题称为最短路问题 。 如果把上图看作一个输油管道网 ， v1 表示发送点，v6表示接收点，其他点表示中转站 ，各边的权数表示该段管道的最大输送量。现在要问怎样安排输油线路才能使从v1到v6的总运输量为最大。这样的问题称为最大流问题。 　　动态规划算法(Dynamic Programming Approach) 　　动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。 　　由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。 　　总的说来，精确性算法基于严格的数学手段，在可以求解的情况下，其解通常要优于人工智能算法。但由于引入严格的数学方法，计算量一般随问题规模的增大呈指数增长，因而无法避开指数爆炸问题，从而使该类算法只能有效求解中小规模的确定性VRP，并且通常这些算法都是针对某一特定问题设计的,适用能力较差,因此在实际中其应用范围很有限。 　　启发式算法求解 　　启发式算法（heuristic algorithm)是相对于最优化算法提出的，是通过对过去经验的归纳推理以及实验分析来解决问题的方法。用启发式算法解决问题时强调的是“满意”，常常是得到满意解，决策者就认为可以了，而不去追求最优性和探索最优解。所以启发式算法能够比较快的得到满意解，这对解决NP难题来说有个不可估量的作用。 　　元启发式算法 　　元启发式算法是对启发式算法的改进，增加了随机干扰算法以防止算法进入局部陷阱或早熟。 　　C-W节约启发式算法 　　节约里程法是用来解决运输车辆数目不确定的问题的最有名的启发式算法。又称节约算法或节约法，可以用并行方式和串行方式来优化行车距离。 　　节约里程法核心思想是依次将运输问题中的两个回路合并为一个回路，每次使合并后的总运输距离减小的幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。优化过程分为并行方式和串行方式两种。 　　遗传算法 　　遗传算法是60年代由美国J.Holland教授和他的学生建立发展的，其思想源于生物遗传学适者生存的自然规律，是一种新兴的自适应随机搜索方法。 　　遗传算法的工作原理是从达尔文的进化论中得到灵感和启迪，借鉴自然选择和自然进化的原理，模拟生物在自然界中的进化过程所形成的一种优化求解方法。尽管这种自适应寻优技术可以用来处理复杂的线形、非线性问题，但它的工作原理却十分简单。 　　模拟退火 　　模拟退火算法（Simulate Anneal，SA）是一种通用概率演算法，用来在一个大的搜寻空间内找寻命题的最优解。模拟退火是由S.Kirkpatrick, C.D.Gelatt和M.P.Vecchi在1983年所发明的。V.Černý在1985年也独立发明此演算法。模拟退火算法是解决TSP问题的有效方法之一。 　　模拟退火的出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法是一种通用的优化算法，其物理退火过程由加温过程、等温过程、冷却过程这三部分组成。 　　蚁群算法 　　蚁群算法是一种用来寻找优化路径的概率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。 　　蚁群系统(Ant System或Ant Colony System)是由意大利学者Dorigo、Maniezzo等人于20世纪90年代首先提出来的。他们在研究蚂蚁觅食的过程中，发现单个蚂蚁的行为比较简单，但是蚁群整体却可以体现一些智能的行为。例如蚁群可以在不同的环境下，寻找最短到达食物源的路径。这是因为蚁群内的蚂蚁可以通过某种信息机制实现信息的传递。后又经进一步研究发现，蚂蚁会在其经过的路径上释放一种可以称之为“信息素”的物质，蚁群内的蚂蚁对“信息素”具有感知能力，它们会沿着“信息素”浓度较高路径行走，而每只路过的蚂蚁都会在路上留下“信息素”，这就形成一种类似正反馈的机制，这样经过一段时间后，整个蚁群就会沿着最短路径到达食物源了。 　　超启发式算法 　　超启发式算法是一种启发式搜索方法，旨在实现自动化，常常与机器学习技术，选择、组合、生成过程，或调整几个简单的启发式算法（或启发式组件）有效地解决计算搜索类问题。研究超启发式的动机之一是建立能够处理一类问题的系统，而不是只解决一个问题。很明显超启发式算法的解决问题的范围更广，跨领域的应用能力更强大。 　　可能有多种启发式方法来解决一个问题，每个启发式都有自己的优点和缺点。其思想是通过结合已知启发式算法的强项和补偿算法的弱项来实现算法。在一个典型的超启发式框架中，有一个高层次的方法论和一组低级启发式算法（无论是构造性的还是微扰的启发式方法）。给定一个问题实例，高级方法根据当前的问题状态或搜索阶段选择在任何给定时间点应用哪种低级启发式。 　　大规模邻域搜索 　　VLSN: Very Large Scale Neighborhood search: 在数学优化中，邻域搜索是一种通过将当前解反复变换为当前解邻域内不同解的方法，试图找到一个组合优化问题的最优解或接近最优解。解的邻域是通过对原始解进行相对简单的修改而得到的一组类似的解。对于一个非常大规模的邻域搜索，邻域是非常大的并且可能是指数大小的。