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

VIP免费
3.0 陈辉 2024-11-19 9 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]。
摘要：

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

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

共128页,预览10页

还剩页未读， 继续阅读

相关推荐

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

开通VIP享超值会员特权

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

作者详情

相关内容

更多

推荐作者

热门标签

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