基于粒子群优化算法的配送车辆路径问题研究
VIP免费
I
目 录
摘要
ABSTRACT
第一章 绪论 .....................................................................................................................1
§1.1 研究的背景及意义...............................................................................................1
§1.2 研究的目的...........................................................................................................3
§1.3 研究的范围和假设...............................................................................................4
§1.4 本文研究的主要内容...........................................................................................4
第二章 车辆路径问题的分类及研究现状 .................................................................... 7
§2.1 车辆路径问题的分类及约束条件.......................................................................7
§2.2 车辆路径问题的研究现状.................................................................................. 8
§2.2.1 经典 VRP 的国内外研究现状 ......................................................................8
§2.2.2VRPTW 的国内外研究现状 ..........................................................................9
§2.2.3 动态 VRP 的国内外研究现状 ....................................................................10
§2.2.4 带能力约束的 VRP 研究现状 ....................................................................12
第三章 粒子群算法的基本原理和研究进展 .............................................................. 13
§3.1 引言.....................................................................................................................13
§3.2 粒子群算法.........................................................................................................14
§3.2.1 粒子群算法的基本原理..............................................................................14
§3.2.2 粒子群算法基本流程..................................................................................15
§3.2.3 基本粒子群算法的社会行为分析..............................................................16
§3.2.4 与其它进化算法的比较..............................................................................17
§3.3 基本 PSO 的改进算法 ....................................................................................... 18
§3.3.1 增加惯性权重和收敛因子..........................................................................18
§3.3.2 为粒子的状态量重新赋值..........................................................................19
§3.3.3 与进化计算结合..........................................................................................20
§3.3.4 使用新的位置和速度更新等式..................................................................21
§3.4 离散粒子群算法.................................................................................................22
§3.5 粒子群算法的应用.............................................................................................22
§3.6 粒子群算法的展望.............................................................................................23
第四章 引入模拟退火机制的并行粒子群算法求解 VRP ......................................... 25
§4.1 引言.....................................................................................................................25
§4.2 车辆路径问题的描述和数学模型.....................................................................25
§4.3 模拟退火算法.....................................................................................................26
§4.4 粒子群算法的并行与同步.................................................................................27
II
§4.4.1 基本粒子群算法..........................................................................................27
§4.4.2 并行粒子群算法的实施..............................................................................27
§4.5 引入模拟退火机制的并行粒子群算法的求解 VRP ........................................30
§4.5.1 编码设计......................................................................................................30
§4.5.2 惯性权重的处理..........................................................................................31
§4.5.3 约束的处理..................................................................................................31
§4.5.4 算法的设计..................................................................................................31
§4.6 实例分析.............................................................................................................32
§4.7 本章小结.............................................................................................................35
第五章 VRPTW 的并行粒子群算法求解 ...................................................................37
§5.1 引言.....................................................................................................................37
§5.2VRPTW 概述 .......................................................................................................37
§5.2.1 时间窗的定义..............................................................................................37
§5.2.2 关于时间窗的说明......................................................................................39
§5.2.3VRPTW 问题的结构 ....................................................................................39
§5.3VRPTW 的模型 ...................................................................................................40
§5.4VRPTW 的并行粒子群算法设计 .......................................................................42
§5.4.1 基本粒子群算法..........................................................................................42
§5.4.2 并行粒子群算法设计..................................................................................42
§5.4.3 初始解的产生..............................................................................................43
§5.4.4 车辆容量约束的处理..................................................................................44
§5.4.5 算法步骤......................................................................................................44
§5.5 实例分析.............................................................................................................44
§5.6 本章小结.............................................................................................................46
第六章 总结和展望...................................................................................................... 47
参考文献 .........................................................................................................................48
在读期间公开发表的论文 ............................................................................................ 57
致谢 .................................................................................................................................58
第一章 绪论
1
第一章 绪论
§1.1 研究的背景及意义
随着科学技术的进步和生产力的发展，顾客消费需求的日趋多样化和个性化、
市场竞争的日益加剧和企业内部环境的巨大变化都对企业提出了新的挑战，企业
需要不断地探索降低费用、增加利润的有效途径，才能保持持续的竞争优势。但
在后工业时代，企业在降低物化劳动成本和活劳动成本方面的潜力已经非常有限。
因此，作为经济领域的“黑暗大陆”和“第三方利润源泉”的物流，开始受到人
们的普遍重视。
物流(Logistic)是指物的流动，即物质资料从供给者向需要者的物理性移动，
是创造时间性、场所性价值的经济活动。现代物流是以满足消费者的需求为目标，
把制造、运输、销售等市场情况统一起来思考的一种战略措施，是研究物料流、
人员流、信息流和能量流的计划、调节和控制的科学。近年来，物流在我国的兴
起引起了业界极大的关注，目前已成为运输界、物流相关企业的热门话题。它在
21世纪具有广泛的前景。
在经济全球化和信息化的推动下，现代物流业已从为社会提供传统运输服务，
扩展到以现代科技、管理和信息技术为支柱的综合物流系统。目前，许多发达国
家和地区已形成了比较成熟的物流管理理念、先进的物流技术和高效的物流运营
系统。进入21世纪的中国，必将加快现代物流的发展，以此增强企业的竞争能力，
优化资源配置，提高经济运行质量，实现中国经济体制与经济增长方式的两个根
本性转变，从而推动中国经济的持续健康的发展[1,2]。
但是，作为目前飞速发展的行业，物流业己经成为企业发展过程中必须有效
管理的“瓶颈”。我国物流成本占GDP比重持续偏高，远高于发达国家。目前，发
达国家的物流成本占GDP的比重为10%左右，中等发达国家（如韩国）的比重占16%
左右，而我国却高达20%左右。另据一些国际组织统计，我国物流水平大约在
20%-30%，同时物流费用占生产成本的40%。而运输是物流决策中的关键所在。除
采购成本外，一般来说，运输成本比其他物流成本所占的比重都高。因此，优化
运输物流，降低运输成本，是企业尤其是物流配送企业提高企业竞争力的有效途
径之一[3]。
在物流配送系统中，物流中心的成立可以有效的简化配送程序与减少配送的
基于粒子群优化算法的配送车辆路径问题研究
2
频率，以i个供货商j个零售商为例，传统的配送模式是假设j个零售商的需求都由i
个供货商自行配送，则一共有i*j次的运送，如图1.1所示。假设零售商与供货商之
间通过一个物流中心来配送，则只需i+j次配送，如图1.2所示。这样即可减少(i*j-(i+j))
的配送次数，当供货商与零售商数目越多，节省的配送次数也就会越多。
图1.1 传统的配送模式
图1.2 以物流中心为主的配送模式
物流中心配送作业的重点是如何将车辆有效的使用并决定其最经济的行驶路
线图，使商品能在最短的时间内送到顾客的手中。国外将此类问题称之为Vehicle
Routing Problem，简称为VRP问题。该问题一般定义为:对一系列装货点(或)卸货点，
组织适当的行车线路，使车辆有序的通过他们，在满足一定的约束条件(如货物需
求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等)下，达
到一定的目标(如路程最短、费用最少、时间尽量少、使用车辆数尽量少等)。
由于消费者需求趋于多样化和竞争的日益加剧，对送货时间的要求日趋严格，
尤其是运送有时效性的商品，例如海鲜、花卉、蔬菜等讲究新鲜度的货物，除了
由于配送不及时会造成货物价值的大大降低，也会对客户满意度有很大影响。因
此，在配送运输上，时间因素显得越来越重要。带时间窗的车辆路径问题(Vehicle
第一章 绪论
3
Routing Problem with Time Windows,VRPTW)是指在VRP中加入配送车辆或顾客希
望服务或被服务的时间约束，目前对该问题的研究还比较少。
VRP和VRPTW是典型的NP-Hard问题，会随着结点的增加出现组合爆炸的现
象，因此求解的困难度及时效性会收到影响。粒子群算法具有快速寻优、多点搜
索的特点，已经被证明在求解组合优化等问题有很好的结果。因此应用粒子群算
法求解VRP和VRPTW是一个有效的途径。
§1.2 研究的目的
车辆路径问题是物流配送优化中关键的一环，是管理科学的一个重要研究课
题，其优化技术是现代物流配送的一项关键技术。该问题自被提出以来，便很快
引起运筹学、应用数学、物流科学、计算机应用等学科的专家与运输计划制定者
和管理者的极大重视，成为运筹学与组合优化领域的前沿与研究热点问题[4]。解决
此问题的传统方法为精确算法及启发式算法(Heuristic Algorithm)，但是在求解 VRP
这种随着规模的增大而成指数增长的问题时，往往求得的结果仅为近似最优解或
者要花费相当长的时间来求得最优解（详细内容请参考第二章）。因此在实际中
的应用范围有限。
粒子群算法[5,6](Particle Swarm Optimization,简称PSO)最早是由美国的社会心理
学家Kennedy和电气工程师Eberhart在1995年共同提出的一种模拟鸟群飞行的仿生
算法。粒子群优化算法是继蚂蚁算法之后又一种新的群体智能算法，它通过群体
中粒子间的合作与竞争产生的群体智能指导优化搜索，目前已经成为进化算法的
一个重要分支。与进化算法比较，PSO保留了基于种群的全局搜索策略，但是其采
用的速度—位移模型操作简单，避免了复杂的遗传操作，它特有的记忆使其可以
动态跟踪当前的搜索情况调整其搜索策略，是一种更高效的并行搜索算法。粒子
群算法有着个体数目少，计算简单，鲁棒性好等优点，在各类多维连续空间优化
问题上均取得非常好的效果。粒子群算法自提出以来，在国外得到了相关领域众
多学者的关注与研究。
粒子群算法不仅能在可接受的时间内求得满意的答案，在问题的扩充性方面也
颇具弹性。由于粒子群算法实行多点搜索，本身具有一定的并行性，易于实现并
行化操作。虽然粒子群算法的全局搜索能力较强，但是它的局部搜索能力较弱。
本文结合粒子群算法和其他启发式算法的优点，并利用粒子群算法的并行性，设
计出效率比较高的混合并行粒子群算法，将其应用在VRP的求解；设计一种多群
并行的粒子群算法，并引入记忆机制，将其应用在VRPTW的求解，以期在合理的
基于粒子群优化算法的配送车辆路径问题研究
4
时间内得到一个满意的路线规划。综上所述，本论文研究的目的可归纳如下:
(1) 构建以配送成本最小为目标的VRP和VRPTW问题的模型。
(2) 对粒子群算法进行改进，求解VRP和VRPTW问题，获得较优的可行解。
§1.3 研究的范围和假设
本论文研究仅针对具有普遍性的物流中心予以探讨，就研究范围与假设界定如
下：
(一)网络特性
无方向性且对称的网络
(二)物流中心的特性
(1)仅考虑区位已知的单一物流中心
(2)物流中心无缺货的可能
(3)物流中心对顾客的基本配送资料(需求量、地理位置、时间窗约束)为己知
(4)物流中心拥有一定数量（多辆）的配送车辆，且每辆车的容量一定
(三)模型的目标函数
(1)总运输成本最小化
(2)违反时间窗约束的惩罚成本最小化
§1.4 本文研究的主要内容
本文研究的内容主要是车辆路径问题和带时间窗的车辆路径问题以及改进粒
子群优化算法的算法设计与求解。分别对 VRP 中的经典 VRP 和VRPTW 展开分析
和讨论，并设计了两种问题的求解方案。
文中的算法是以粒子群算法思想为基础，对 VRP 设计了引入模拟退火机制的
并行粒子群算法，对 VRPTW 设计了多群并行的粒子群算法并分别予以软件实现。
通过仿真试验，给出测试的结果并对其进行分析和讨论。通过对计算结果的分析
和其他文献的比较，表明了本文算法的有效性和优越性。
对这些不同的 VRP 求解的方法主要有精确算法（如分枝定界法）、传统启发
式算法（如两阶段法）、现代启发式算法（如遗传算法）。本文对当前国内外不同
的VRP 研究进行综合并结合本文所要研究的主要内容，详细介绍经典 VRP 和
VRPTW 的国内外研究现状。
为了达到上述研究目的，本文首先收集了国内外学者专家对车辆路径和行程
摘要：
展开>>
收起<<
I目录摘要ABSTRACT第一章绪论.....................................................................................................................1§1.1研究的背景及意义...............................................................................................1§1.2研究的目的..................................................
相关推荐
作者：陈辉
分类：高等教育资料
价格：15积分
属性：58 页
大小：668.23KB
格式：PDF
时间：2024-11-19
