专题2车辆路径问题.pdfVIP

专题2车辆路径问题

主要内容

n什么是VRP

nVRP背景及应用

nVRP问题定义

nVRP问题的分类

nVRP问题数学模型

nVRP算法类型及简要介绍

n近年来关于VRP的研究

专题2车辆路径问题

一、什么是VRP

VRP（VehicleRoutingProblem）

车辆路径问题

当不考虑时间要求，仅根据空间位置安排

线路时，称为车辆路径问题。

专题2车辆路径问题

二、VRP的背景及应用

车辆路径问题是由G.Dantzig和J.Ramser

于1959年首先提出来的,很快引起运筹学、

管理学、计算机应用、组合数学、图论

等学科的专家学者的高度重视。

其研究结果在运输系统、物流配送系统、

快递收发系统中都已得到广泛应用。

专题2车辆路径问题

三、VRP问题定义

对一系列发货点或收货点，组织适当的

行车路线，使车辆有序地通过它们，在

满足一定的约束条件(如货物需求量、发

送量、交发货时间、车辆容量限制、行

驶里程限制、时间限制等)下，达到一

定的目标(如路程最短、费用最小、时间

尽量少、使用车辆尽量少等)。

专题2车辆路径问题

四、VRP问题的分类

n按任务特征分类

装货问题(PurePickUp)、卸货问题

(PureDelivery)及装卸混合问题

(CombinedPickUpandDelivery)

n按任务性质分类

有对弧服务问题(如中国邮递员问题)

和对点服务问题(如旅行商问题)

以及混合服务问题(如交通车路线安排问

题)

n按车辆载货状况分类

专题2车辆路径问题

有满载问题和非满载问题

n按车场数目分类

有单车场问题和多车场问题

n按车辆类型分类

有单车型问题和多车型问题

n按车辆对车场的所属关系分类

有车辆开放问题(车辆可不返回车场)和车

辆封闭问题(车辆必须返回车场)

n按已知信息的特征分类

有确定性VRP和不确定性VRP,其中不确定性

VRP可进一步分为随机VRP(SVRP)和模糊

VRP(FVRP)

专题2车辆路径问题

n按优化目标数来分类

有单目标问题和多目标问题

n按约束条件分类

1.有距离约束的VRP问题(Distance

ConstrainedVehicleRoutingProblem)

2.有能力约束的VRP问题(Vehicle

RoutingProblemwithCapacity

Restriction)

3.对称问题和非对称问题

4.三角不等式问题

专题2车辆路径问题

n按约束条件分类

5.有等需求问题(EqualDemand)和非等需

求问题(UnequalDemand)

6.有时间窗的VRP问题(VehicleRouting

ProblemwithTimeWindow)

该问题中还包括柔性时间窗约束和刚性

时间窗约束

专题2车辆路径问题

五、VRP问题的数学模型

(1)问题

从一个配送中心出发，向多个客户点送货，然

后在同一天内返回到该配送中心，要安排一个

满意的运行路线。

(2)已知条件

1.配送中心拥有的车辆台数m及每辆车的载重量（吨位）

为

2.需求点数为n及每个点的需货量为

3.配送中心到各需求点的费用及各需求点之间的费用为