当前位置:文档之家› 配送路线选择与车辆调度

配送路线选择与车辆调度


1)
21
反复进行第二和第四步,直至没有可连接的用户时为止,得满意方案如表 6-5。
表 6-5 满意方案 (单位:公里)
B0
1)
B1
1) 5
B2
2
7
B3
1)
3
8
18
B4
1)
14 8
5
7
B5
1)
9 10 10 13 17 B6 1)
11 10 10 14 22 24 B7 1) 1)
满意配送方案的配送路线为:B0—B1—B5—B7—B6—B4—B3—B2—B0,总行
此模型用精确算法求解更加困难,下面仍 用节约法求解此类问题的满意解。求解的过 程与例6-1基本相同,只是在方案改进的过程
中,寻找具有最大节约量的用户i、j时,增
加了考虑车辆载重量和可调度车辆数的约束, 而且,车辆调度时优先使用载重量大的车辆。
26
例:由配送中心B0向12个用户Bj (j=1,2,…12)送货,
12
对于旅行商问题,通常构造成一个网络图,相应的数学模型为:
min z
cij xij
ij
n
xij 1
i1
n
xij 1
j1
X
( xij )

1
xij
0
j 0,1, n
i 0,1, n S
路段(i, j)在线路上; 否则。
第六章 配送路线选择与车辆调度
主要内容:
配送路线安排与车辆调度问题及节约法原 理;
单中心配送路线选择与车辆调度; 多中心配送路线选择与车辆调度;
货车配载 。
1
第一节 配送路线安排与车辆调度问题
及节约法原理
一、配送路线安排与车辆调度问题
配送路线安排与车辆优化调度问题常被分为车
辆路线安排问题(Vehicle Routing Problem,
(6.1)
9
图 6-2 是节约法的基本原理图,其中图(a)方案为配送中心对两个用户 分别单独派车送货,两辆车送货总行程为:
Sa 2d0,i 2d0, j
将图(a)方案变成图(b)方案,改变后只需用一辆车送货,送货总行程为:
Sb d 0,i d 0, j di, j
改变后的方案比原方案节约运输里程:
条件(1)保证用户点 i、j 不是内点。所谓“内点” 是指不与配送中心直接连接的点。
如果最大节约量有两个或两个以上相同时,可随机取 一个。
按此条件,在初始方案表 6—3 中寻得具有最大节约 量的一对用户为 i=6、j=7,其节约量为 24 公里。
19
第三步,按 tij 的定义和公式(6.4)修正 tij 的值。 连接 B6与B7 ,即令 t6,7 1 ,由公式(6.4)得:
程 54 公里。
22
二、多车非满载配送路线安排与车辆调度
问题描述:一个配送中心 B0 向 n 个用户 B j ( j 1,2, , n) 配 送货物,用户 Bj 的需求量为 b j ;配送中心配有配送车辆 m 量,按载重量分为 p 种类型,每种类型记为 l(l 1,2, , p) , 每 种 车 的 数 量 为 wl 辆 、 载 重 量 为 ql , 且

j
xijk
yki

X (xijk ) S

xijk
1
or
0
k i 1,2, , n i 0,1, , n k j 0,1, , n k i 0,1, , n k
i, j 0,1, , n k
(6.5)
式中,S 为支路消去约束,即消去构成不完整线路的25解。
为了克服精确优化方法的不足,人们提出了许 多能获得“满意”解的启发式算法。启发式算法 是一种基于直观或经验构造的算法,它运用一些 经验法则,并通过模仿人的跟踪校正过程来求得 系统的满意解。
启发式算法中最具有代表性的是由Clarke和 Wright提出的节约法(Saving Method)。
7
节约法的基本原理:
简记VRP)和车辆调度问题(Vehicle
Scheduling Problem,简记VSP),前者仅从空
间位置考虑车辆路线的安排和车辆调度,后者则
要考虑时间要求。显然VSP问题比VRP 问题讨论
的范围宽,或者说,VSP问题是有时间约束的VRP
问题。本书主要讨论VRP问题。
2
VRP问题的描述
VRP问题一般可描述为:对一系列装货点或 (和)卸货点,组织适当合理的行车路线,使车 辆有序地通过它们,在满足一定的约束(如货物 需求量、发送量,车辆容量、数目限制、车辆行 驶里程限制等)条件下,达到一定的目标(如最 短路程、最小费用、最短时间、最少车辆等)。
3
VRP问题的分类
VRP问题又根据不同标准分为:车辆满载问题 (一个用户的货运量大于一辆车的容量,完成任 务需要多辆车)与非满载问题(一个用户的货运 量不大于一辆车的容量,完成任务只需要一辆 车)、单车场问题(一个货场或一个配送中心) 与多车场问题(多个货场或多个配送中心)、单 车型(所有车辆容量相同)与多车型问题(车辆 容量不全相同),以及优化目标的单目标与多目 标问题。
例 6-1 表 6-1 所列为一个配送中心 B0 和 7 个用户
Bj ( j 1, 2...,7) 8 个点任意两点之间的距离,用一辆
货车装载 7 个用户所需的货物,从配送中心出发 巡回给 7 个用户送货,然后回到配送中心,求行 程最短的送货路线。
14
表 6-1 里程表 (单位:公里)
B0
8
B1
1 yki 0
1 xijk 0
用户i由车辆k配送; 否则。
车辆k从i点行驶到j点; 否则。
可建立该问题的数学模型如下:
24
min Z
cij xijk


i
qi yki qk


yki 1
k
yki 1 or 0


xijk ykj
i

Bi Bi-1
Bj
Bi
Bj+1 Bi-1

Bj
Bj+1


B0
B0
(a)
(b)
图 6-1 配送方案改进
8
假定运输网络中的任意两点之间都有路径可以连通,且最短距离已 知。如果配送中心有更大的车辆,即一辆车能完成四个用户的送货,这 时可将图 6-1(a)的配送方案改变成图 6-1(b)的方案,配送路线为
tij 0 表示 i、j 点不连接,即不在同一巡回路线中;
t0 j 2 表示用户点 j 与配送中心 B。连接两次,即由一辆车单
独给用户 Bj 送货。 根据以上定义,应有以下等式成立:
j-1
7
tij tij 2
i0
i j1
j 1,2, 7
(6.4)
按节约量公式(6.2)计算任意两用户之间的节约量,列于表 6-2。
B0 Bi1 Bi B j B j1 B0 ,车辆行驶的总里程为:
Sb d 0,i1 d i1,i d i, j d j, j1 d j1,0
显然,改变后的方案与改变前相比,车辆行驶总里程的节约量为:
Si, j d0,i d0, j di, j
4
二、VRP问题精确求解方法的局限性
1. VRP问题求解思路 VRP问题的求解方法一般相当复杂,通常的 做法是应用相关技术将问题分解或者转化为 一个或多个已经研究过的基本问题(如旅行 商问题、指派问题、运输问题、最短路问题、 最小费用流问题、中国邮递员问题等),再 使用相对比较成熟的基本理论和方法进行求 解。
t0,6 1 t0,7 1
得改进方案如表 6-4,改进后的方案比原方案节约行 程 24 公里。
20
表 6-4 改进方案 (单位:公里)
B0
2) B1
2) 5 B2
2) 2 7 B3
2) 3 8 18 B4
2) 14 8 5 7 B5
1) 9 10 10 13 17 B6
1) 11 10 10 14 22 24 B7
各点之间的运输里程和各用户的需求量见表6-1。表6-2为 可供调度的车辆数目及其载重量。
表6-1 各点之间里程表(单位:公里) 表6-2 可供调度的汽车
bj
(吨)
B0
配送车种类
1.2 9 B1 1.7 14 5 B2
可供调度台数
1.5 21 12 7 B3
1.4 23 22 17 10 B4
1.7 22 21 16 21 19 B5
B0
2) B1
2) 5
B2
2) 2
7
B3
2) 3
8
18
B4
2) 14
8
5
7
B5
2) 9
10
10
13
17
B6
2) 11
10
10
14
22
24
B7
18
第二步,满足下述条件,在初始方案表中寻找具有最 大节约量的用户点 i、j:
(1) t0i、t0 j 0 i j;
(2) Bi、B j 尚未连接在同一巡回路线上;
(6.3)
式中,xij 为路段(i,j)是否在配送路线上的决策变量;S 为支路
消去约束,即消去构成不完整线路的解。
求解时令 cii M (i 1, n) ,M 为相当大的正数。
13
由于旅行商问题是典型的 NP 难题,难以用 精确算法求解,一般采用启发式方法。下面举例 说明用节约法求解单车非满载车辆配送路线安排 问题的计算过程。
相关主题