车辆路径问题.doc

《车辆路径问题.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

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

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

3、型车辆路径问题(Mixed/HeterogeneousFleetVehicleRoutingProblem，MFVRP/HFVRP)。(4)时间窗约束：包括硬时间窗(HardTimewindows)和软时间窗(SoftTimewindows)约束。引出带时间窗(包括硬时间窗和软时间窗)的车辆路径问题(VehicleRoutingProblemwithTimewindows，VRPTW)。(5)相容性约束：引出相容性约束车辆路径问题(VehicleRoutingProblemwithCompatibilityConstraints，VRPCC)。(6)

4、随机需求：引出随机需求车辆路径问题(VehicleRoutingProblemwithStochasticDemand，VRPSD)。(7)开路：引出开路车辆路径问题(OpenVehicleRoutingProblem)。(8)多运输中心：引出多运输中心的车辆路径问题(Multi-DepotVehicleRoutingProblem)。(9)回程运输：引出带回程运输的车辆路径问题(VehicleRoutingProblemwithBackhauls)。(10)最后时间期限：引出带最后时间期限的车辆路径问题(VehicleRoutingProblemw

5、ithTimeDeadlines)。(11)车速随时间变化：引出车速随时间变化的车辆路径问题(Time-DependentVehicleRoutingProblem)。二、CVRP问题描述及其数学模型CVRP的描述：设某中心车场有k辆车，每辆配送车的最大载重量Q，需要对n个客户(节点)进行运输配送，每辆车从中心车场出发给若干个客户送货，最终回到中心车场，客户点i的货物需求量是qi(i=1,2,…,n)，且qi

6、定义变量如下:建立此问题的数学模型：minz=cijxijk(2.2)约束条件：yki=1(i=0,1,…,n)(2.3)xijk=ykj(j=0,1,…,nk=1,2,…,m)(2.4)xjik=ykj(j=0,1,…,nk=1,2,…,m)(2.5)qiykiQ(k=1,2,…,m)(2.6)三、车辆路径问题算法综述目前，求解车辆路径问题的方法非常多，基本上可以分为精确算法和启发式算法2大类。3.1精确算法精确算法是指可求出其最优解的算法，主要运用线性规划、整数规划、非线性规划等数学规划技术来描述物流系统的数量关系，以便求得最优决策。精确算法主要

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

8、2启发式算法由于车辆路径优化问题是NP难题，高效的精确算法存在的可能性不大(除非P=NP)，所以寻找近似算法