VRPTW及其扩展问题的蚂蚁算法研究

VIP免费
3.0 陈辉 2024-11-19 12 4 1.37MB 128 页 15积分
侵权投诉
第一章 绪论
1
第一章 绪 论
§1.1 引言
从全社会的利益出发，最有效地利用各种资源，提高资源的利用率，选取利
用资源的最优方式是当今经济工作研究的重要任务。在工业、农业、商业、交通
运输、工程设计以及国防建设中，人们经常遇到一些要求对现有资源、设备进行
统一分配、全面安排、合理调度或最优设计等问题。如何从众多的以不同方式分
配和利用资源的可能方案之中，利用最新的科学技术手段选取出最经济、最合理
的一个可行方案，从而进行最优决策就要用到运筹学及经营管理等领域中的方法
和技术。运筹学是系统工程学的主要组成部分，其主要任务是对各种事务或活动
中出现的问题进行系统的分析和评价，要求达到人力物力省、质量高、利润大等
指标。
物流管理学是近二十年来在国外兴起的一门新科学，研究的是如何实现物流
管理合理化以及获取最大的经济利润，同样要用到系统工程中的许多原理和解决
问题的手段。随着时代的不断进步和发展，物流业在国民经济中的地位越来越重
要，直接影响和制约着社会经济的发展。实现物流的系统化、现代化、社会化和
合理化，不断提高物流效益，无论对于企业还是社会都是至关重要的。特别是国
际贸易往来的不断扩大、市场经济的快速发展、市场竞争的日趋激烈使得物流服
务业得到了很大的发展。
现代物流被称为企业的“第三利润来源”，其本质是企业通过提高物流管理的
水平和效率可大大节约物流成本。物流最早是在美国形成的，我国是在 80 年代才
接触“物流”这个概念的，其原意为“后勤”，是二次世界大战时军队为维持战争
需要的一种后勤保障系统。后来把“Logistics”一词转用于物资的流通中，这时，
物流就不单纯是考虑从生产者到消费者的“货物配送”问题，而且还要考虑到从
供应商到生产者对原材料的采购，以及生产者本身在产品制造过程中的运输、保
管和信息等各方面，全面地、综合性地提高经济效益和效率的问题。因此，现代
物流是以满足消费者的需求为目标，把制造、运输、销售等市场情况统一起来思
考的一种战略措施。近年来，物流在我国的兴起引起了业界极大的关注，目前已
成为运输界、物流相关企业的的热门话题。
车辆路径问题（Vehicle Routing Problem，简记 VRP）是物流配送优化中关键
的一环[1]，是提高物流经济效益、实现物流科学化所必不可少的，是管理科学的一
个重要研究课题，其优化技术是现代物流配送的一项关键技术。该问题自被提出，
VRPTW 及其扩展问题的蚂蚁算法研究
2
便很快引起运筹学、应用数学、物流科学、计算机应用等学科的专家与运输计划
制定者和管理者的极大重视，成为运筹学与组合优化领域的前沿与研究热点问题。
各学科专家对该问题进行了大量的理论研究及实验分析，取得了很大进展。本文
主要就是研究车辆路径问题中一种比较常用比较重要的问题――带时间窗的车辆
路径问题。下面先简单介绍车辆路径问题的几种类型：
VRP 一般可描述如下[2]：在约束条件下，设计从一个或多个初始点出发，到
多个不同位置的城市或客户的最优送货或路径分配，即要设计一个费用最小的路
线集：
(1) 每个城市或客户只被一辆车访问一次；
(2) 所有车辆从起点出发再回到起点；
(3) 一些约束被满足；
最通常的约束包括：
(1) 容量限制：对每个城市 i都有一个需求量 di，则任何车辆路径上总重
量不能超过车辆的负载能力；有容量限制的 VRP 称为 CVRP。
(2) 任何路线上城市的数目不小于某常数 q（这是(1)在di=1 以及 D=q时
的一个特例）；
(3) 总时间长限制：任何的路径长度不能超过某一常数 L，这个长度包括
城市间的旅行时间和在城市的停留时间。有时间或路长限制的 VRP
称为 DVRP；
(4) 时间窗：城市 i必须在时间段[bi,ei]中被访问，允许在城市 i停留。有
时间窗限制的 VRP 称为 VRPTW。
(5) 两个城市的优先关系：城市 i必须在 j之前被访问；
当然，上述约束可能还不够完善，许多问题结合到实际中约束可能更复杂，
因此，可根据不同情况要求具体分析。
§1.2 车辆路径问题的基本问题
§1.2.1 TSP
旅行商问题（Traveling Salesman Problem，简称 TSP）[3]，又称货郎担问题，
是运筹学中一个著名的问题，它的提法是：有一货物推销员从城市 1出发到城市 2、
3、4…、n去推销货物，最后回到城市 1，问应怎样选择一条总行程最短的路线？
（各城市间距离 cij 为已知）。TSP 是运筹学一个非常经典的离散系统优化问题，很
多问题本质上都可以归结为 TSP 来求解，如：计算机线路问题、数据聚类问题、
第一章 绪论
3
工作排序问题等，VRP 也是以 TSP 为其子问题的。
TSP 在图论意义下又常常被称为最小 Hamilton 圈问题（Minimum Hamiltonian
Cycle Problem），为构造其数学模型：
记G=( V,E)为赋权图，V={1,2,…,n}为顶点集，E为边集，各顶点间的距离
cij 已知（cij>0, cii=∞,i,j∈
V
）。设
则经典 TSP 问题的数学模型为：
这里，|S|为集合 S中所含图 G的顶点数。约束（1）（2）意味着对每个点来
说，仅有一条边进和一条边出；约束（3）则保证了没有任何子回路解的产生。于
是满足约束（1）（2）（3）的解构成了一条 Hamilton 回路。
TSP 已被证明是 NP－难题，NP ( Non-deterministic Polynomial )问题即不确定
性多项式算法问题。目前人们普遍认为，NP－难题不能用任何已知的多项式算法
求解，因此，不少人猜测任何 NP－难题都没有多项式算法，但至今无人证明。这
样一种认识的实际意义在于，许多人相信难计算是这一类问题的固有性质，因此
它们不可能用有效算法求解，而所有能进行精确求解的算法，在最坏情况下都需
要指数级的时间。由于现实中这些问题在许多领域都有着广泛的应用，因而寻找
其实际而有效的算法就显得颇为重要了。遗憾的是，计算复杂性理论给予我们的
结论是，这种可能性尚属未知。尽管有指数级的算法可作精确求解，但随着它们
在大规模问题上的失效（组合爆炸），人们退而求其次，转向寻找近似算法或启发
式算法。经过几十年的努力，取得了相当的进展。
其他
在回路路径上若
0
),(1 ji
xij
 
 
 
10
)3(,1
)2(,1
)1(,1
..
1
1
1 1
，
ij
Si Sj
ij
n
i
ij
n
j
ij
n
i
n
j
ijij
x
VSSx
Vjx
Vix
ts
xcMinZ
VRPTW 及其扩展问题的蚂蚁算法研究
4
§1.2.2 VRP
通常意义下的 VRP 的提法为：已知有一批客户，每个客户点的位置坐标和货
物需求已知，车辆的负载能力一定，每辆车都从起点(depot)出发，完成若干客户点
的运送任务后再回到起点。假设每个客户被而且只被访问一次，每辆车所访问的
城市的需求总和不能超过车辆的负载能力。问题是使所有客户需求都得到满足，
且总旅行成本最小。
为构造数学模型，记 G= (V, E)为赋权图，V={1, 2,
…
, n}为顶点集，E为边集，
各顶点间的（距离）权值为 cij (cij>0, cii=∞,i, j
∈
V)，每辆车的载重量为 D，各客
户点的需求为 di(i
∈
V)，并定义变量如下：
则VRP 的数学模型如下：
s.t.
这里，｜
S
｜为集合 S中所含图 G的顶点个数，约束（1）为车辆负载限制，约
束（2）则保证每辆车对每个客户只能访问一次，约束（3）、（4）、（5）则是为了
保证能形成回路。
同样，作为一个 NP-难题，VRP 的求解也是有着一定难度的。自被提出以来，
已经有相当多的各学科的专家和学者对其进行了大量的研究并提出了许多解决方
法[4]-[9]，为今后的进一步探讨打下了基础。
其它
完成的顾客需求由车辆点
,0
,1 ki
yki
其它
行驶到点从点车辆
,0
,1 jik
xijk
 
kVjiyx
VSSx
kViyx
kVjyx
Viy
kDyd
kiijk
ji SS
ijk
j
kiijk
i
kjijk
k
ki
i
kii
,,,)1,0(,
)5(,1
)4(,,
)3(,,
)2(,1
)1(,
,
i j k
ijkij xcMinZ
第一章 绪论
5
§1.2.3 VRPTW
带时间窗的车辆路径问题（Vehicle Routing Problem with Time Windows，简记
VRPTW ）[10]就是在 VRP 基础上增加了时间窗约束，即给定每个客户一个时间范
围，车辆对客户的服务时间必须在这个范围内开始，如果车辆在客户允许的服务
最早开始时间以前到达，则必须等待。以上提法是大多数文献中最常见的，也是
国内外研究最多的。
而事实上，时间窗问题其实又有硬时间窗和软时间窗之分，硬时间窗就是如
果不能在客户要求的时间范围内开始对其进行服务，则得到的解为不可行解；软
时间窗是指如果不能在客户要求的时间内对其进行服务，可以放宽时间窗的要求，
但要给予一定的惩罚。在以往的文献中，提到的时间窗问题如果没有特别说明通
常都是指硬时间窗的车辆路径问题，即服务开始的时间必须在时间窗口内。
国内对 VRPTW 的研究主要是集中在遗传算法，李军（2001）[1]提出了一种
VRPTW 的描述及其数学模型，如下所示：
某一配送中心拥有 K辆车，容量分别为 qk(k=1,
…
,K)，有 L个客户点，其需求
为gi(i=1,
…，
L)，V={1, 2,
…
, L}为顶点集，时间窗口[ETi,LTi]，ETi 为任务 i的允许
最早开始时间，LTi 为任务 i的允许最迟开始时间，cij 表示从点 i到点 j的运输成本，
它的含义可以是距离、费用、时间等。si表示车辆到达任务点 i的时间，PE表示在
ETi之前到达为任务点 i等待的单位时间成本，
PL表示在 LTi之后到达任务点 i的单
位时间的罚金成本。若车辆在 ETi之前到达点 i，则增加机会成本 PE×（si
－
ETi），
若车辆在 LTi之后到达，则增加罚金成本 PL×（LTi
－
si）。从上述描述中可知，该
问题是车辆数固定的车辆路径问题，也就是说，根据不同的问题 VRPTW 有多种
不同类型。本文将研究的是车辆数不固定的 VRPTW，因此将根据下面李军给出的
模型对其进行改进，研究多目标的 VRPTW。上述描述中的数学模型如下所示：
s.t.
i j k i i
iiLiiEijkij LTsPsETPxcMinZ )0,max()0,max(
VRPTW 及其扩展问题的蚂蚁算法研究
6
本文在实现了这种通常意义的 VRPTW 的基础上又给出了软时间窗车辆路径
问题的算法设计并实现具体实例求解，从而进一步丰富和扩展了带时间窗车辆路
径问题的类型和应用。
由VRPTW 的提法中可知，时间窗只是给出了顾客的可容忍时间区间而没能
考虑到顾客的希望服务时间。事实上，在许多实际应用中，尽管要求顾客提供固
定的时间服务窗口，顾客却希望尽可能在希望的时间得到服务，我们称这一希望
的时间为约定时间（due-time）。在这种情况下，顾客的偏好信息可表达为满足服
务时间意义上的凸模糊数，当在模糊时间上进行调度时，我们感兴趣的不仅是通
常对于所有顾客可行的服务时间，而且是在努力使服务时间尽可能接近每个顾客
的约定时间意义上的合理服务时间。鉴于这种问题，Cheng 和Gen（1995）提出了
模糊车辆路径问题 FVRP（Fuzzy Vehicle Routing Problem，FVRP）[11]，它是基于
模糊约定时间的概念，其中模糊约定时间的隶属函数符合服务时间的满意度。
其模糊约定时间可由下图表示：
完全满意
不满意 较满意 不满意
eitiuilit
图1.1 模糊约定时间
Fig.1.1 Fuzzy due time
由于 FVRP 在时间窗的限制上又增加了模糊数学的概念，目前在国内外的文
献中还很少有人研究，这也是本文将着重研究的另一类时间窗车辆路径问题。
还有一些动态以及限制车辆数等带时间窗车辆路径问题[12]-[14]，这里不做研究。
§1.3 主要方法技术
有关 VRP 的研究早在 20 世纪 80 年代以前就有了很多文献研究。Gilbert
Laporte[2]在他的文献中总结了多种用于求解 VRP 的算法。可是，带时间约束的车
辆路径问题只在 80 年代后才开始受到重视。最早对 VRPTW 的算法研究是 1986
年Solomon[11]的启发式算法研究，1987 年Kolen[16]等最早提出最优化算法。1987
年Solomon 较系统地将 VRP 的启发式算法推广应用到 VRPTW，通过最坏情形的
分析指出求解 VRPTW 从根本上比求解 VRP 更难[17]。
第一章 绪论
7
VRP 发展到现在，求解算法已非常丰富。许多学者对这些方法的分类进行了
研究和归纳，基本上可分为精确算法和启发式算法两大类。VRP 的精确算法大体
可归成 3大类：树搜索法、动态规划、整数线性规划。各算法中还包括许多方法，
下面先来看一下这几种用于求解 VRP 的精确算法。
§1.3.1 精确算法（Exact Algorithm）
树搜索法（Direct Tree Search Methods）
分支定界法是一种应用范围比较广的搜索算法，它通过有效的约束界限来控
制搜索进程，使之能向着状态空间树上有最优解的分支推进，以便尽快找出一个
最优解。分支定界搜索的关键在于约束界限的选取，由不同的约束界限可形成不
同的分支定界法[18]。其中以分派问题为界的方法比较常用，即通过求解相应的分
派问题得到一个下界，以此下界为约束界限进行分支定界搜索。另外，k度数算法
也是一种树搜索法[19]，并已被应用到 VRP 的求解中。有时，是通过求解问题的下
界与分支定界法相结合使用的。
动态规划（Dynamic Programming）
该方法最初是用来求解有固定的 m辆车的 VRP，用 c(S)表示通过顶点 1和V\{1}
的子集 S中的所有点的车辆路径的费用（长度）；fk(U)表示使用 k辆车运输到 V\{1}
的子集 U的可行最小费用。则最小费用可通过下面的递归方程得到：
解出的费用为 fm(V\{1})，最优解即上式中的最优子集 U*。显然，对于所有 k
和V\{1}的任何子集 U都必须计算 fk(U)，那么，对于绝大多数问题来说计算的量
都太大了。虽然后来有人将这一方法加以改进，但通常除了很小规模的问题外，
一般不采用这种方法。
整数线性规划（Integer Linear Programming）
用于求解 VRP 的整数线性规划方法有割平面法、列生成法等，割平面法的基
本思想是通过求解由约束构成的 LP 问题，然后增加不等式约束产生割平面，逐步
收敛到最优解。列生成法用于求解紧约束时间窗的车辆路径问题效果较好。
精确算法的计算量一般随问题的增大呈指数增长，因此在实际中应用范围并
不广泛。人们就寻找求解该类问题的近似算法或启发式算法，本文将在下面的章
节中介绍几种比较经典的启发式算法。用于求解 VRPTW 的精确算法同 VRP 类似，
下面主要介绍启发式算法。
)1(*)](*)\([
)1()(
)(
1
}1\{* min kUcUUf
kUc
Uf
k
VUU
k
VRPTW 及其扩展问题的蚂蚁算法研究
8
§1.3.2 启发式算法
启发式源自英文单词 heuristics，启发式算法意为通过对过去经验的归纳推理
以及实验分析来解决问题的方法，即借助于某种直观推断或试探的方法，它要求
分析人员从与研究问题有关而较基本的模型及算法中寻求其间的联系，从中得到
启发，去发现适于解决该问题的思路和途径。启发式算法求解问题是通过迭代过
程实现的，理论上并不收敛于最优解，因此，它强调的是得到满意解。有时决策
者不会去追求最优性和最优解，之所以这样是因为：很多问题不存在最优解，这
时，对目标的满意性常比最优性更能准确的描述人们的选择行为；对有些问题得
到它的最优解所花的代价太大；从实际决策的需要出发，有时要求解具有过高的
精度没有意义。启发式算法能够比较快地得到满意解，这对解决 NP-难题来说有着
不可估量的作用[20]。
衡量一个启发式算法的优劣主要有以下几个评价标准：
(1) 解的质量：对启发式算法产生的解进行测度可通过目标函数值与最优值的
近似性和算法产生可行解的能力两个方面来进行。即 C/C*≤ε来衡量，C为启发式
解的目标值，C*为最优解的目标值，ε则为最坏情况（worst case behavior）下启发
式解与最优解的目标值之比的上界。由于该上界在许多情况下都是问题规模的某
种函数形式，往往随着问题规模的增长而增长，因而失去了作为近似算法所应具
有的控制精度作用。这也是该类算法只能称为启发式算法而不能严格地冠以“近
似算法” 这个名称的原因所在。
(2) 运行时间和所需存贮量：启发式算法的好坏与其所需的存贮量大小及问题
的运行时间长短密切相关，可应用概率分析、经验分析和对最坏情形下的分析等
方法对其进行测度。
(3) 实现的难度：指编码的复杂程度及对数据的需求情况。
(4) 灵活性：指算法能否容易地处理模型、约束和目标函数的变化。一个好的
启发式算法应具有适应性广和比较灵活的特点。
(5) 可靠性：启发式算法应具有进行灵敏度分析和产生解的界值的能力，可使
用户能利用得到的信息确定所得的解与最优解的接近程度。
(6) 简洁性：算法应该能够用简洁明了的语言陈述出来，而且易于分析。
启发式算法通常又分为传统启发式（Classic Heuristics）算法和现代启发式算
法（Metaheuristics），有的文献也称其为亚启发式算法或进化型算法。VRPTW 作
为一个 NP-难题，设计高效的精确算法非常困难，为此，人们主要把精力花在构造
高质量的启发式算法上。
第一章 绪论
9
§1.3.2.1 传统启发式算法
线路构造启发式算法
该类算法思想是，根据一些准则，每一次将一个不在线路上的点增加进线路
直到所有的点都被安排进线路为止。算法的每一步，把当前的线路构形（很可能
是不可行的）跟另外的构形（也可能是不可行的）进行比较并加以改进，后者或
是根据某个判别函数（例如总费用）会产生最大限度的节约的构形，或是以最小
代价把一个不在当前构形上的需求对象插入进来的构形，最后得到一个较好的可
行构形。像比较著名的 Clarke&Wright 算法、最近邻算法、插入式算法等都属于该
类算法。
通常，线路构造有两种实现方法，即序列方法和平行方法。序列方法是指每
一次构造一条路线，而平行算法则是同时构造多条路线。
Clarke&Wright 算法（Clarke&Wright Savings Heuristic）
Clarke&Wright 又称节约算法，最早由 Clarke 等[21]提出用于求解 VRP。节约算
法的第一步是定义关于边的节约值，如下图所示：
i j i j
O O
图1.2 路线合并后的成本节约
Fig.1.2 Saving cost by merging routes
如将边(i , j)上的节约值定义为： ，其中 cij 表示边(i , j)
上的成本。当μ＝1时，则 sij 表示将单独对点 i和j分别配送的两条路线改为由一
辆车来完成点 i和j配送后所降低的成本。
节约算法是将每条只含一个配送点的 n条路线作为初始解，其中，每条路线
中第一个和最后一个配送点分别称为路线的起点和终点。考察一条路线的起点与
令一条路线的终点相连合并成一条新的路线。如果合并后的路线满足约束条件，
则说这样的合并是可行的，并将合并的节约值定义为连接这两条路线的边的节约
值。选择节约值最大的可行合并进行一次路线的合并。当不存在可行合并时，算
法结束。
节约算法用于求解 VRPTW，Solomon 建议在选择路线合并时对等待时间进行
适当限制。设要合并的两条路线的连接边为(i , j)，w’j表示在点 j的等待时间，则
0,
ijojoiij cccs
VRPTW 及其扩展问题的蚂蚁算法研究
10
当w’j>W（W为参数）时不选择该路线合并。
最近邻算法（Nearest Neighbor Heuristic）
最近邻算法是一种序列构造路线法，算法从一条只含一个配送点的路线出发
（通常取这个点为“距离”站点最近的点），在未分配点中筛选出可加入点（可加
入点即作为一条路线的终点仍然保持路线的可行性的未分配点）并从可加入点中
选取一个点作为当前路线的终点，使得路线的成本最小。如此不断对路线进行扩
充，直到路线不存在可加入点为止。这时，如果所有点均已分配，则算法结束；
否则，生成一条新的初始路线，重复前面的路线扩充程序。
需要说明的是，前面提到的“距离”未必指实际的距离，而是距离和时间等
因素的函数。可根据不同的问题有不同的定义，如针对 VRPTW 问题，Solomon
将其定义为：
ijijijij vTdc 321
，其中 i为当前路线的终点，j为未分配点，
)( iijij sbbT
表示从点 i出发到开始对 j服务的时间差，
)( ijiijij tsblv
表
示在 i与j之间的时间余地，
01 321321
、、，＝＋＋
。
插入式算法（Insertion Heuristic）
插入式算法的流程与最近邻算法相似，也是从初始路线出发，序列构造路线，
并在不存在可行插入时新增一条初始路线。插入式算法的关键是选择最合适的未
分配点在路线中进行最佳位置的插入。
插入式算法可按插入规则的不同而分为若干类，常见的有以下几种：最近插
入（Nearest Insertion）、最小插入（Cheapest Insertion）、任意插入（Arbitrary Insertion）、
最远插入（Farthest Insertion）等，具体实施时可将出发点取遍 V中各点，从而得
到n个解，然后取最好的一个。
扫除算法（Sweep Heuristic）
扫除算法最早由 Gillett 和Miller 在1974 年提出[22]，是一种“先分组后路线”
（cluster-first-route-second）的算法。1987 年，Solomon 将其推广应用到 VRPTW
的路线构造。所谓分组，即指分配给每辆车一组点，一种简单的分组方法是将以
车站为原点的坐标平面划分为多个扇形区域，并初步将每个扇形区域的点分派给
一辆车。所谓的路线，是指在每个区域内，采用扫除算法选择未分配点，然后应
用插入式算法扩充路线。如果在进行了一次分组－路线的线路构造后还存在未分
配点，则再进入上述程序，直到所有点均已分配为止。
两阶段法（Two-phase Algorithm）
学者们通过对构造性算法的研究发现，对其求得的解可以进一步改进，为此
提出了两阶段法。第一阶段得到一可行解，第二阶段通过对点的调整，在始终保
持可行解的情况下力图向最优目标靠近，每一步都产生另一可行解代替原来的解，
摘要：

第一章绪论1第一章绪论§1.1引言从全社会的利益出发，最有效地利用各种资源，提高资源的利用率，选取利用资源的最优方式是当今经济工作研究的重要任务。在工业、农业、商业、交通运输、工程设计以及国防建设中，人们经常遇到一些要求对现有资源、设备进行统一分配、全面安排、合理调度或最优设计等问题。如何从众多的以不同方式分配和利用资源的可能方案之中，利用最新的科学技术手段选取出最经济、最合理的一个可行方案，从而进行最优决策就要用到运筹学及经营管理等领域中的方法和技术。运筹学是系统工程学的主要组成部分，其主要任务是对各种事务或活动中出现的问题进行系统的分析和评价，要求达到人力物力省、质量高、利润大等指标。物流...

展开>> 收起<<
VRPTW及其扩展问题的蚂蚁算法研究.pdf

共128页,预览10页

还剩页未读， 继续阅读

相关推荐

更多
立即下载
作者：陈辉 分类：高等教育资料 价格：15积分 属性：128 页 大小：1.37MB 格式：PDF 时间：2024-11-19

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

推荐作者

热门标签

/ 128
评分 收藏
分享
立即下载 VIP免费下载
客服
关注