内容发布更新时间 : 2024/5/9 20:05:48星期一 下面是文章的全部内容请认真阅读。

精品文档

车辆路径问题(VRP)一般定义为：对一系列装货点和卸货点，组织适当的行车线路，使车辆有序地通过它们，在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等)下，达到一定问题的目标(如路程最短、费用最少、时间尽量少、使用车辆数尽量少等)。

目前有关VRP的研究已经可以表示（如图1）为：给定一个或多个中心点（中心仓库，central depot）、一个车辆集合和一个顾客集合，车辆和顾客各有自己的属性，每辆车都有容量，所装载货物不能超过它的容量。起初车辆都在中心点，顾客在空间任意分布，车把货物从车库运送到每一个顾客（或从每个顾客处把货物运到车库），要求满足顾客的需求，车辆最后返回车库，每个顾客只能被服务一次，怎样才能使运输费用最小。而顾客的需求或已知、或随机、或以时间规律变化。

图1 VRP示意图

一、在VRP中，最常见的约束条件有:

(1) 容量约束：任意车辆路径的总重量不能超过该车辆的能力负

精品文档

精品文档

荷。引出带容量约束的车辆路径问题(CapacitatedVehicle Routing Problem，CVRP)。

(2) 优先约束：引出优先约束车辆路径问题(VehicleRouting Problem with precedence Constraints，VRPPC)。

(3) 车型约束：引出多车型车辆路径问题(Mixed/Heterogeneous Fleet 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) 随机需求：引出随机需求车辆路径问题(VehicleRouting 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) 车速随时间变化：引出车速随时间变化的车辆路径问题(Time-Dependent Vehicle Routing Problem)。 二、CVRP问题描述及其数学模型

CVRP的描述：设某中心车场有k辆车，每辆配送车的最大载重量Q，需要对n个客户(节点)进行运输配送，每辆车从中心车场出发给若干个客户送货，最终回到中心车场，客户点i的货物需求量是qi (i=1,2,…,n)，且qi

定义变量如下:

建立此问题的数学模型：

minz = ? ?? cijxijk (2.2)

i约束条件：

jk ? yki =1 (i=0,1,…,n ) (2.3) k ? xijk=ykj (j=0,1,…,n k=1,2,…,m) (2.4) i xjik=ykj (j=0,1,…,n k=1,2,…,m) (2.5)

i qiyki?Q (k=1,2,…,m) (2.6)

i??三、车辆路径问题算法综述

目前，求解车辆路径问题的方法非常多，基本上可以分为精确算

精品文档