文档介绍：1
第四章求解VRPTW的启发式算法
问题的描述
求解算法
经典启发式算法
通用启发式算法
小结
2
问题的描述
VRPTW是CVRP的扩展。
客户i 的时间窗[ai, bi],希望在此时间段内得到服务。
装卸货物的服务时间为si。
配送中心的时间窗设为[a0, b0],通常令a0= 0。
时间窗的要求导致每条线路具有隐含的方向性和线路长度限制L =b0。
线路k 的长度可表示为:
其中wi 为在客户点i的等待时间,Nk 为线路k上的客户点集。
3
硬时间窗
车辆在时刻bi 之后到达客户点是不允许的,若在时刻ai之前到达,则等待。
软时间窗
允许车辆到达客户点的时间有所偏离时间窗,但要根据所带来的不方便程度支付一定的惩罚。
所允许的时间窗违反方式的不同,将形成不同类型的VRPSTW。有如下六种主要类型:
4
各图中,横轴表示时间,纵轴表示惩罚值
ai bi ai bi Wmax Pmax ai bi Pmax
(a) (b) (c)
ai bi Pmax Pmax ai bi Pmax Pmax ai bi Pmax
(d) (e) (f)
VRPSTW的主要类型
5
惩罚值的计算。令ti 表示车辆到达客户点i的时间,于是惩罚值P(ti)可以用时间窗偏离量的线性函数来表示。如对于类型(b):
其中,αi和βi为惩罚系数,分别表示在之前和之后开始服务时,每单位时间应支付的惩罚值。
6
求解算法
现已提出了各种各样的启发式算法,大多数是关于带硬时间窗的。最近几年关于软时间窗的文献逐年增多。
经典启发式算法(与CVRP类似)
线路构造法
线路改进法
混合启发式算法(构造法+改进法)
通用启发式算法
近年来对求解VRPTW的算法研究的核心是通用启发式算法,主要包括模拟退火、禁忌搜索、以及遗传算法等。
7
Taillard等1997年描述了一个求解带软时间窗的VRP的禁忌搜索算法:
采用了由Rochat等(1995)提出的自适应记忆概念。
以他们提出的用于求解VRP的分解和重构方法为基础。
通过对偏离时间窗实行高强度的惩罚,该算法也可以用于求解带硬时间窗的问题。
我国学者近年来陆续提出了一些各具特色的、求解带时间窗的VRP的启发式算法。
8
求解VRPSTW的改进遗传算法(2003)
提出采用基于车辆代号的符号编码方法。
客户号码: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
父代个体1: 1 1 2 1 2 1 2 3 3 2 3 3 4 3 3 4 4
父代个体2: 1 1 2 2 1 2 2 2 2 3 3 3 3 3 4 4 4
引入自适应机制来增强算法性能。
目的:避免发散和陷入局部最优点,并保护种群中“好”的个体,加快优化进程。
实现方法:动态地调整Pc和Pm,即对高适应值的解降低Pc和Pm的值,对低适应值的解提高Pc和Pm的值。
9
其中k1=, k2=, k3=1, k4=;
f0 为种群中的最大适应值;
f′表示交叉的两个个体中较大的适应值;
fˉ为种群的平均适应值;
f 是变异个体的适应值。
10
求解VRPSTW的一体化禁忌搜索算法(2007)
分层处理VRPSTW 的三个要最小化的目标:
所使用的车辆总数
总的时间窗偏离程度
车辆行驶总距离
该目标函数可以表示为:
对不可行解也进行检查分析,目标函数变为: