物流配送车辆路径问题.pptx

➢CVRP是NP-难的，并且是旅行商问题（TSP）的 一般化。在TSP中，要求确定一条经过图G中所有 顶点的、费用最小的回路（哈密顿回路），当 CVRP中的C≥∑di和K=1时就为此情形。
15
2.2.2 带路程长度的VRP（DistanceConstrained and Capacitated VRP，DCVRP ）
• 车辆是自备还是外租，完成任务后是否返回；
• 车辆的装载能力;
• 车辆使用费;
• 可用于进行货物装卸的设备.
5. 驾驶员（driver）
• 给驾驶员安排取送货任务时，必须符合工作时间 方面的有关规定。
Hale Waihona Puke 6. 路径编排中的限制条件
• 车辆的当前负载不能超过车辆的装载量；
• 客户只要求送货、取货、或取送货兼有；
➢在一些测试算例中，顶点与给定坐标的平面上的点 相对应，且弧的费用cij被定义为对应于顶点i和j的两 点间的欧氏距离。
cij xi x j 2 yi y j 2 yj
j (xj, yj)
yi xj
i (xi, yi)
xi
12
➢在配送中心备有相同类型的车辆，每辆的装载 能力为C。每一条线路上的送货任务只由一辆 车承担。
2
车辆路径问题的特点
1. 道路网（road network） • 弧表示路段，点表示道路交叉点、配送中心和
客户。 • 弧的权cij表示其距离或行驶时间。
3
2. 客户（customer）
• 用图上的小圆点表示；
• 需运送或收取的货物量（需求量）di (或di和pi )； • 要求提供服务的时间段，即时间窗（time window
➢总费用一般包括所使用的车辆数（即回路数）和车 辆行驶费用两项。通常都认为，多用一辆车所带来 的固定费用的增加，总是超过其因总行驶距离缩短 所带来的节省，因此，一般把最小化车辆使用数作 为第一优化目标，最小化行驶费用作为第二目标。
14
➢当备有的车辆类型不是同一种时，即有不同的装 载能力Ck，k =1,…,K，则就为经常考虑的另一种 变形。
8
当不要求车辆完成任务后返回原出发点，或 者是若要求返回原出发点，则沿原去程路线 返回时（即车辆的行驶路线是开放式的）， 称之为开放式车辆路径问题（Open VRP， OVRP）。
9
根据所包含的约束条件，问题又可进一步分 类。以闭合式VRP为例，可归纳如下：
DCVRP
路程长度
VRPPD
装载能力 取送作业
）
• 在客户点所花费的服务时间si； • 能用于服务该客户的车辆集合。
3. 配送中心（车场）（distribution center，depot）
– 用图上的小方点表示；
– 车辆行驶路线开始并终止于配送中心或某一个客 户点；
– 其特征由所配备的车辆种类和数量、以及所能处
理的货物总量来描述。
4
4. 车辆（vehicle）
特点
既有车辆装载能力限制，又有最大路程长度限 制。
描述
➢每矩条 阵弧 与对 长应 度着 矩一阵个相非一负致的，长即度cij =tij，tij。一般地，费用 ➢每条线路上各弧的总长度不能超过线路的最大长
CVRP
时间窗
VRPTW
回程运输
VRPBTW
VRPB
VRPPDTW
10
2.2.1 带装载能力的VRP（ Capacitated VRP，CVRP）
问题的特点
是VRP中的最基本型式。 所有客户都属于要送货的或要取货的，其需求量
预先知道，且不能被分割。 车辆类型相同且都停放在一个配送中心。 对车辆只有装载能力限制。 问题的目标是最小化服务所有客户的总费用（即
所需要的车辆数及其车辆行驶距离或行驶时间） 。
问题的描述（可描述为如下的图论问题） 11
➢设G = (V, A)为一个完备图，其中V = {0,…,n}为顶点 集，A是弧集。顶点i = 1,…,n表示客户，而顶点0表 示配送中心。有时配送中心用顶点n +1来表示。
➢每条弧对应着一个非负的费用cij，表示从点i到点j的 行驶费用。
• 在客户所要求的时间窗和驾驶员的工作时间内提 供服务；
• 访问客户的顺序要求。
5
7. 行驶距离和行驶时间 • 必须知道客户点与客户点之间，配送中心与客户
点之间的行驶距离和行驶时间。 8. 目标（objectives） • 最小化总运输成本，其大小取决于所需要的车辆
数（或线路数）、总行驶距离（时间）； • 最小化与客户的不完全服务等有关的惩罚值； • 均衡各线路上的行驶时间和车辆载重量。
➢一般描述是：对一系列给定的客户点，确定配送 车辆行驶路线，使其从配送中心出发，有序地对 它们进行服务，并在满足一定的约束条件下（如 车辆载重量、客户需求量、服务时间限制等）， 使总运输成本达到最小（如使用车辆数最少、车 辆行驶总距离最短等）。
➢一般把最小化车辆使用数作为第一优化目标，而 最小化车辆行驶距离作为第二优化目标。
第二章 物流配送车辆路径问题
2.1 问题的描述及各组成部分特点 2.2 车辆路径问题的分类 2.3 车辆路径问题的研究现状和发展趋势
1
2.1 问题的描述及各组成部分特点
➢配送活动中的配送车辆行驶线路优化确定问题， 是近二十多年来国际运筹学界的研究热点之一。
➢运筹学界将此类问题统称之为车辆路径问题（ Vehicle Routing Problem, VRP），或车辆调度问 题（Vehicle Scheduling Problem, VSP）。
➢每个客户 i 有一个已知的需要送往交付的非负 需求量di，假设di < C。服务所有客户至少所需 要的车辆数
K min
di
C
13
➢CVRP是求一个具有最小总费用的由K条简单回路组 成的集合（每个回路对应于一条配送车辆行驶线路 ），并满足 (1) 每个回路从配送中心出发并返回配送中心； (2) 每个客户点只在一条回路上； (3) 一条回路上各客户点的需求量之和不超过车 辆装载能力C。
6
2.2 车辆路径问题的分类
根据配送车辆完成配送任务后是否必须返回 原出发点以及返回的形式，可将问题分为闭 合式和开放式两大类。
在不需严格区分的场合，统称VRP。
7
当车辆完成运输任务后必须返回原出发点时 （即车辆的行驶路线是闭合式的），称之为 闭合式车辆路径问题（Closed VRP），通常 简称为车辆路径问题（VRP）。