(整理)车辆路径问题.

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

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

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

4、机需求：引出随机需求车辆路径问题( VehicleRoutingProblem with Stochastic Demand， VRPSD)。(7) 开路：引出开路车辆路径问题( Open VehicleRoutingProblem) 。(8) 多运输中心：引出多运输中心的车辆路径问题(Multi - DepotVehicle Routing Problem) 。(9) 回程运输：引出带回程运输的车辆路径问题( VehicleRouting Problem with Backhauls)。(10) 10) 最后时间期限：引出带最后时间期限的车辆路径问题( Vehicle Routing Pro

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

6、辆才由f到:o 否则否则精品文档(2. 2) yki =1kZ Xjk =ykj“, xjik=ykj、qiyki -Q建立此问题的数学模型：minz = cijxijki j k约束条件：(i=0,1，n )(2. 3)(j=0,1，n k=1,2，m)(2.4)(j=0,1，n k=1,2，m) (2. 5)(k=1,2，m)(2. 6)三、车辆路径问题算法综述目前，求解车辆路径问题的方法非常多，基本上可以分为精确算法和启发式算法2 大类。3.1 精确算法精确算法是指可求出其最优解的算法，主要运用线性规划、整数规划、 非线性规划等数学规划技术来描述物流系统的数量关系，以便求得最优决策。精确

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

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

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

10、构造算法的研究，认为由构造算法求得的解可以被进一步改进，为此提出了两阶段法。第一阶段得到一可行解，第二阶段通过对点的调整，在始终保持解可行的情况下，力图向最优目标靠近， 每一步都产生另一个可行解以代替原来的解，使目标函数值得以改进，一直继续到不能再改进目标函数值为止。Gillet和Miller于1974年提出的 sweejpff法，Christofides Mingozzi和Toth的算法以及 Fisher和Jaikumar的算法都属于两阶段法。一般第一阶段常用构造算法，在第二阶段常用的改进技术有2- opt( Lin, 1965)， 3- opt( LinKernighan, 1973)和 Or-opt(Or, 1976)交换法，这是一种在解的邻域中搜索，对初始解进行某种程度优化的算法，以改进初始解。一些基于数学规划的算法也属于两阶段法，把问题直接描述成一个数学规划问题，根据其模型的特殊构形，应用一定的技术( 如分解 )进行划分，进而求解己被广泛研究过的子问题(FisheryJaikumar,1981) 。在两阶段法求解过程中，常常采用交互式优化技术，把人的主观能动作用结合到问题的求解过程中，其主要思想是：有经验的决策者具有对结果和参数的某种判断