《车辆路径问题》

《《车辆路径问题》》由会员分享，可在线阅读，更多相关《《车辆路径问题》（8页珍藏版）》请在装配图网上搜索。

1、车辆路径问题（VRP ）般定义为：对一系列装货点和卸货点， 组织适当的行车线路，使车辆有序地通过它们，在满足一定的约束条 件（如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程 限制、时间限制等）下，达到一定问题的目标（如路程最短、费用最少、 时间尽量少、使用车辆数尽量少等）。目前有关VRP的研究已经可以表示（如图1）为：给定一个或多 个中心点（中心仓库，central depot）、一个车辆集合和一个顾客集 合，车辆和顾客各有自己的属性，每辆车都有容量，所装载货物不能 超过它的容量。起初车辆都在中心点，顾客在空间任意分布，车把货 物从车库运送到每一个顾客（或从每个顾客处把货物运到车库）

2、，要 求满足顾客的需求，车辆最后返回车库，每个顾客只能被服务一次， 怎样才能使运输费用最小。而顾客的需求或已知、或随机、或以时间 规律变化。图1 VRP示意图一、在VRP中，最常见的约束条件有：（1）容量约束：任意车辆路径的总重量不能超过该车辆的能力负荷。引出带容量约束的车辆路径问题(CapacitatedVehicle Routing Problem，CVRP)。 优先约束：引出优先约束车辆路径问题(VehicleRoutingProblem with precedence Constraints，VRPPC)。 车型约束:引出多车型车辆路径问题(Mixed/Heterogeneous Fl

3、eet Vehicle Routing Problem，MFVRP/ HFVRP)。(4) 时间窗约束：包括硬时间窗(Hard Time windows)和软时间 窗(Soft Time windows)约束。引出带时间窗(包括硬时间窗和软时 间窗)的车辆路径问题(Vehicle Rout ing Problem wit hTime windows，VRPTW)。(5) 相容性约束：引出相容性约束车辆路径问题 (VehicleRouting Problem with Compatibility Constraints， VRPCC)。(6) 随机需求：引出随机需求车辆路径问题(VehicleR

4、outing Problem with Stochastic Demand，VRPSD) 。(7) 开路：引出开路车辆路径问题(Open Vehicle RoutingProblem)。(8) 多运输中心:引出多运输中心的车辆路径问题(Multi-Depot Vehicle Routing Problem)。(9) 回程运输：引出带回程运输的车辆路径问题 (VehicleRouting Problem with Backhauls)。(10) 最后时间期限：引出带最后时间期限的车辆路径问题 (Vehicle Routing Problem with Time Deadlines)。(11) 车

5、速随时间变化：引出车速随时间变化的车辆路径问题 (Time-Dependent Vehicle Routing Problem)。二、CVRP问题描述及其数学模型CVRP的描述：设某中心车场有k辆车，每辆配送车的最大载重 量Q,需要对n个客户(节点)进行运输配送，每辆车从中心车场出发 给若干个客户送货，最终回到中心车场，客户点i的货物需求量是 q. (i=l,2,n),且q.Q。记配送中心编号为0,各客户编号为 iii (i=1,2，,n), c.表示客户i到客户j的距离。求满足车辆数最 ij小,车辆行驶总路程最短的运送方案。定义变量如下:=Jl车辆Mlh刊_ (1 车辆蹴帥V否则儿訓否则建立

6、此问题的数学模型：约束条件：minz 呈工工c xi. i.ki j k(2.2)工y =1ki(2.3) k工x =yi.k k.(j=0,1,，n(i=0,1, ,n )k=1,2, ,m)(2.4)工 Xjik二ykj(j=o,l,nk=l,2,，m)(2.5) i工 qy Q(k=l,2,m)(2.6)i kii三、车辆路径问题算法综述目前，求解车辆路径问题的方法非常多，基本上可以分为精确算 法和启发式算法2大类。3.1精确算法精确算法是指可求出其最优解的算法，主要运用线性规划、整数 规划、非线性规划等数学规划技术来描述物流系统的数量关系，以便 求得最优决策。精确算法主要有：分枝定界法

7、(Branch and Bound Approach)割平面法(Cu tt ing Planes Approach)网络流算法(Network Flow Approach)动态规划算法(Dynamic Programming Approach)总的说来，精确性算法基于严格的数学手段，在可以求解的情况 下，其解通常要优于人工智能算法。但由于引入严格的数学方法，计 算量一般随问题规模的增大呈指数增长，因而无法避开指数爆炸问 题，从而使该类算法只能有效求解中小规模的确定性VRP,并且通常 这些算法都是针对某一特定问题设计的,适用能力较差,因此在实际 中其应用范围很有限。3.2启发式算法由于车辆路径优

8、化问题是NP难题，高效的精确算法存在的可能性 不大（除非P=NP）,所以寻找近似算法是必要和现实的，为此专家主要 把精力花在构造高质量的启发式算法上。启发式算法是在状态空间中 的改进搜索算法，它对每一个搜索的位置进行评价，得到最好的位置， 再从这个位置进行搜索直到目标。在启发式搜索中，对位置的估价十 分重要，采用不同的估价可以有不同的效果。目前已提出的启发式算 法较多，分类也相当多，按Van Breedam的分类法，主要的启发式算 法有以下几类：构造算法、两阶段法、智能化算法。3.2.1 构造算法（Cons truct ive Algori thm）这类方法的基本思想是：根据一些准则，每一次将

9、一个不在线路 上的点增加进线路，直到所有点都被安排进线路为止。该类算法的每 一步把当前的线路构形（很可能是不可行的）跟另外的构形（也可能是 不可行的）进行比较并加以改进，后者或是根据某个判别函数（例如总 费用）会产生最大限度的节约的构形，或是以最小代价把一个不在当 前构形上的需求对象插入进来的构形，最后得到一个较好的可行构 形。这类算法中中最著名的是Clarke和Wright在1964年提出的节约算 法。构造算法最早提出来解决旅行商问题，这些方法一般速度快，也 很灵活，但这类方法有时找到的解离最优解差得很远。322 两阶段法(Two-phase Algorithm)学者们通过对构造算法的研究，

10、认为由构造算法求得的解可以被 进一步改进，为此提出了两阶段法。第一阶段得到一可行解，第二阶 段通过对点的调整，在始终保持解可行的情况下，力图向最优目标靠 近，每一步都产生另一个可行解以代替原来的解，使目标函数值得以 改进，一直继续到不能再改进目标函数值为止。Gillet和Miller于 1974年提出的sweep算法，Christofides、Mingozzi和Toth的算法以 及Fisher和Jaiku mar的算法都属于两阶段法。一般第一阶段常用构造 算法，在第二阶段常用的改进技术有2-opt(Lin,1965), 3-opt(Lin Kernighan,1973)和0 r-op t (0

11、r,1976)交换法，这是一种在解的邻域 中搜索，对初始解进行某种程度优化的算法，以改进初始解。一些基于数学规划的算法也属于两阶段法，把问题直接描述成一 个数学规划问题，根据其模型的特殊构形，应用一定的技术(如分解) 进行划分，进而求解己被广泛研究过的子问题(Fishe r和 Jaikumar,1981)。在两阶段法求解过程中，常常采用交互式优化技术，把人的主观 能动作用结合到问题的求解过程中，其主要思想是：有经验的决策者 具有对结果和参数的某种判断能力，并且根据知识直感，把主观的估 计加到优化模型中去。这样做通常会增加模型最终实现并被采用的可 能性。此方法是目前成果最丰富、应用最多的一类方法

12、。每一种方法讨 论的情况不尽一致，适用范围也不完全相同。323 智能化算法(Intelligent Algorithm)这类算法以启发式准则来代替精确算法中的决策准则，以缩小解 搜索的空间。总体来看，尽管启发式算法能够在有限的时间内求出质量较高的 解，但由于其搜索解空间的能力有所限制，因此经常无法达到预期的 要求。20世纪90年代以来，由于人工智能方法在解决组合优化问题中 的强大功能，不少学者开始将人工智能引入车辆路线问题的求解中， 并构造了大量的基于人工智能的启发式算法(智能化启发式算法)。智 能化启发式算法从本质上讲仍然属于启发式算法，其基本思想是从一 初始解开始，通过对当前的解进行反复地局部扰乱(Perturbations) 以达到较好的解。目前，最常见的智能化启发式算法包括模拟退火算 法(Simulated Annealing)、禁忌搜索算法(Tabu Search)、遗传算 法(Gene tic Algori thm)、蚁群算法(Ant Colony)和神经网络(Neutral Networks)、粒子群算法(Particle SwarmOptimization,PSO)方法等。(注：素材和资料部分来自网络，供参考。请预览后才下载，期待你的好评与 关注！)