中国工程论文网
代写工程论文
当前位置:工程论文网 > 工程硕士论文 > 物流工程硕士论文 > 基于蚁群算法的物流快递车辆动态调度研究

基于蚁群算法的物流快递车辆动态调度研究

时间:2018-05-08 22:21来源:www.e-lunwen.com 作者:lgg 点击:
本文是一篇物流工程硕士论文,物流工程是管理与技术的交叉学科,它与交通运输工程、管理科学与工程、工业工程、计算机技术、机械工程、环境工程、建筑与土木工程等领域相关
本文是一篇物流工程硕士论文,物流工程是管理与技术的交叉学科,它与交通运输工程、管理科学与工程、工业工程、计算机技术、机械工程、环境工程、建筑与土木工程等领域密切相关。(以上内容来自百度百科)今天为大家推荐一篇物流工程硕士论文,供大家参考。
 
1 绪论
 
1.1 研究背景和意义
1.1.1 研究背景
快递是指快递公司通过公路、铁路和航空等交通运输方式,快速投递货物到客户手中,它是一种门到门的物流活动。近年来,我国快递业发展的内外部环境不断优化,得益于电子商务发展迅猛,加之国家出台了一系列市场规范政策,诸如改革税制、产业联动、完善相关法律法规体系等。据国家统计局发布数据,2016年上半年全国快递企业业务收入达到 1195.7 亿元,同比增长 33.2%,快递包裹量达 84.6 亿件,同比增长 43.3%,快递业务发展迅速。中国的快递业在高速增长的同时,一系列问题不容回避。比如低价竞争、快递车辆违规上路、快件安全存隐患、受到快递企业运输能力的限制,持续增长的快递运输需求得不到及时满足等等。其中日益增长的客户需求同有限的运输能力之间的矛盾成为亟待解决的焦点问题。车辆调度问题(VRP)作为运输管理中的主要问题,因此得到专家学者们的普遍关注,一度成为研究热点。快递企业需要对车辆行驶路径进行合理的规划以提高服务质量,降低运输成本。纵观国内外车辆调度问题的研究,现已证明 VRP 问题是典型的 NP-hard 问题,求解该问题通常使用精确算法和启发式算法。众多学术研究中,数学模型的建立和应用场景的设置多为单配送中心(或多配送中心)和多客户点之间寻求最优路径,而针对更具实际的在有障碍域的工作环境中寻找一条从转运中心到各客户点的最优车辆路径的研究甚少。本文将有障碍域的快递车辆调度问题定义为VRPOA(即 Vehicle Routing Problem with Obstacle Area)。
...........
 
1.2 问题描述和主要内容
 
1.2.1 问题描述
本文研究的是 VRPOA 问题,从路径规划算法出发,旨在集合改进蚁群算法和Dijkstra 算法,找寻一条从转运中心到各客户点的规避障碍域的最优车辆路径。因此,需要考虑以下几个问题:(1)初始最优车辆路径。从蚁群算法解决 TSP 问题出发,以此拓展为以车辆载重量为约束条件、以车辆总行驶距离为目标的快递车辆路径规划问题的求解。如何提高算法的搜索效率和精准度?(2)模型的构建需要确定的目标和约束条件,需要考虑哪些前提条件,即提出假设。(3)如何利用 MAKLINK 图论建立有障碍域的路径规划的二维空间。(4)如何确定需要局部调优的点。(5)包括改进蚁群算法的程序设计、Dijkstra 算法的程序设计都是研究的重点和难点。
 
1.2.2 主要内容
在梳理和总结国内外基于车辆调度问题的精确算法和各类启发式算法的相关理论研究的基础上,本文针对更具实际的应用场景,研究基于蚁群算法的二维路径规划算法解决有障碍域的工作环境中快递车辆调度问题。文章包含六个部分,涵盖的主要内容如下:第 1 章绪论。首先阐述了研究的背景和问题,明确了本文的研究意义以及研究方法,对文章的主要内容和结构框架进行了论述,并指出本文的创新点。第 2 章国内外的相关研究。通过对国内外已有的基于车辆调度问题的精确算法和各类启发式算法的相关理论研究进行梳理和总结,分析其成熟完善之处,并且指出其不足,寻找突破口,找到自己的研究思路。第 3 章设计有障碍域的快递车辆调度问题的模型。包括对本文定义的 VRPOA问题的界定,确定目标函数为快递车辆总行驶路径最短,确定车辆载重量限制、每个客户的需求都能得到满足等约束条件,对问题提出假设和进行符号说明。第 4 章阐述基于蚁群算法的二维路径规划算法求解 VRPOA 问题策略。在这一章中,主要探讨算法所涉及的路径规划算法、MAKLINK 图论理论、Dijkstra 算法和蚁群算法,对这些基本理论做了详细介绍,综合各个算法设计了解决 VRPOA 问题的策略,并通过实例分析基于蚁群算法的二维路径规划算法求解两点间路径规划的过程。第 5 章通过仿真分析验证本文探究的基于蚁群算法的二维路径规划算法解决 VRPOA 问题的有效性和可行性。第 6 章结论与展望。归纳总结全文的内容,并指出研究的局限和不足,以及对未来的研究展望。
........
 
2 国内外的相关研究
 
2.1 车辆路径问题的研究
2.1.1 VRP 的定义
Dautzig 和 Ramser 于 1959[1]年提出了车辆优化调度问题,即 VehicleRouting Problem(简称 VRP)。VRP 问题一般定义为:对车辆行驶路径进行规划,使其从配送中心出发,依次通过所有的客户点(客户点已经确定),最后返回配送中心,满足的约束条件是取送货时间(时间窗)、车辆载重量限制等,所需要达到的目标通常是车辆行驶路径最短、总的成本费用最小、客户满意度高和所用车辆数最少等。VRP 问题的示意图如图 2. 1 所示。VRP 的构成要素一般归为以下几个方面:目标函数(Objective Function)、约束条件(Restrictions)、物流中心(Logistics Center)、车辆(Vehicle)、运输网络(Transport Network)、客户(Customer)以及货物(Freight)。具体要素展开可以分为以下 10 类[2]:(1)按物流中心的数量分,单物流中心问题和多物流中心问题。(2)按车辆载货状况分,满载、非满载以及满载和非满载混合问题。满载问题指完成全部取送货任务至少需要一辆车辆,因为客户的需求量大于车辆额定载重量,所以运输车辆需要满载行驶;非满载问题指完成多项取送货任务可共用一辆车辆,因为客户的需求量小于车辆额定载重量,所以车辆通常需要非满载行驶;满载和非满载混合问题指一些客户的需求量大于车辆额定载重量,一些客户的需求量小于车辆额定载重量,所以部分车辆需要满载行驶,部分车辆需要非满载行驶。
...........
 
2.2 蚁群算法的研究
蚁群算法(Ant Colony Algorithm,ACA),又称蚂蚁算法,是由意大利学者Marco Dorigo[42]于 20 世纪 90 年代初提出的一种新的模拟进化算法,模拟蚂蚁群体的觅食行为,用来在图中寻找优化路径的机率型算法。蚂蚁觅食是一种群体性行为,它们是靠群体的力量来寻找食物。单只蚂蚁一边寻找食物源,一边在其走过的路径上释放一种叫做信息素的物质。其他的蚂蚁走过同样的路径时,会感知到路径上残留的信息素,同时也释放信息素。由于信息素是一种挥发性物质,随着时间的推移,路径上的信息素会逐渐挥发掉,信息素浓度降低。久而久之,较短路径上的信息素浓度会越来越高,蚂蚁也会倾向于选择这条较短路径,这就是一种正反馈机制。最后,蚂蚁群体能够找到一条从蚁巢到食物的最短路径。模拟蚂蚁觅食行为的蚁群算法一经提出,便备受学者关注。蚁群算法以其分布并行式计算、启发式搜索方式等特点,在各个领域中取得了广泛的应用,解决了许多组合优化方面的问题。针对其可能陷入局部最优的特点,不少专家和学者提出了许多改进的方法,并将其他算法(遗传算法、粒子群算法)与蚁群算法相结合,对蚂蚁数量 m、信息素重要程度因子α、启发函数重要程度因子β、信息素挥发因子θ、蚂蚁信息素释放总量 Q 等参数进行优化选择,取得了不错的效果。本节着重阐述蚁群算法的国内外研究进展及其改进算法,最后探讨这一群体智能算法的未来研究和应用方向。
..........
 
3 有障碍域的快递车辆调度问题模型..........25
3.1 问题描述.............25
3.2 假设和符号说明...........25
3.3 模型构建.............26
3.4 本章小结.............27
4 基于蚁群算法的快递车辆调度问题模型求解....28
4.1 路径规划算法.....28
4.2 蚁群算法.............29
4.3 2-opt 算法..........39
4.4 MAKLINK 图论理论........40
4.5 Dijkstra 算法....40
4.6 综合算法设计和求解策略.....42
4.7 实例分析.............44
4.8 本章小结.............45
5 应用实例仿真实验........46
5.1 实验设计.............46
5.2 结果分析.............47
5.3 本章小结.............51
 
5 应用实例仿真实验
 
5.1 实验设计
本文参考国际通用的 Benchmark Problems 构建了测试实例,验证算法解决VRPOA 问题的有效性和可行性。测试用例:25 个客户点,每个客户点的需求量和坐标已知,如表 5. 1 所示;二维空间中转运中心到各客户点之间的四块障碍域的范围已知(即坐标已知),如表 5. 2 所示。在100 × 100的二维坐标轴的上绘制的散点图如图 5. 1 所示;在100 × 100的二维坐标轴的上绘制的障碍域如图 5. 2 所示;在满足车辆载重量限制情况下(标准车辆载重量 VW=10),找到从转运中心出发,避开这些障碍域的最佳的车辆指派(安排车辆数量和规划车辆行车路线,以使车辆行驶总路径最短)。
..........
 
结论
 
针对车辆路径规划问题,这一典型的 NP-hard 问题,国内外相关研究比较深入,关于此问题的求解算法也渐趋成熟,可分为精确算法和启发式算法两个大类。而多数学术研究中应用场景的设置多为单配送中心(或多配送中心)和多客户点之间寻求最优路径,针对更具实际的在有障碍域的工作环境中寻找一条从转运中心到各客户点的最优车辆路径的研究甚少。本文针对此问题,深入研究了基于蚁群算法的二维路径规划算法,将改进蚁群算法与 Dijkstra 算法相结合,实例分析验证了算法的可行性和有效性。对于本文主要完成的研究工作总结如下:
(1)挖掘研究问题。通过阅读大量文献,对车辆路径问题的定义、分类、复杂度、求解算法做了详尽的总结,发现车辆路径问题的理论型研究已渐趋成熟,而考虑实际应用场景的应用型研究还有待拓展。本文以此为出发点,探究 VRPOA问题,即在有障碍域的工作环境中寻找一条从转运中心到各客户点的最优车辆路径。
(2)确定研究方法。通过文献阅读的积累,发现求解车辆路径问题这一类NP-hard 问题需要使用智能启发式方法。相比 20 世纪 70~90 年代产生的诸如模拟退火算法、禁忌搜索算法、遗传算法和神经网络算法等,蚁群算法自 1991 年被提出以来,经过二十多年的研究发展,成为求解离散优化问题的有效工具,且优势明显。MAKLINK 图论可以构造二维路径规划的可行空间,而 Dijkstra 算法是解决有向图中最短路径问题的有效算法,可以用于局部车辆路径调优。
(3)得出研究结论。针对快递车辆路径问题,构建了以行驶总距离最短为目标的单目标数学模型,设计了算法和求解策略,实验过程中,首先使用改进蚁群算法找到初始全局最优路径,其次利用 MAKLINK 图论建立有障碍域的二维路径规划的空间模型,找出可行解,最后使用 Dijkstra 算法进行局部优化产生最终的路径规划图。实验证明本文提出的基于蚁群算法的二维路径规划算法对于求解VRPOA 问题行之有效。
..........
参考文献(略)
(责任编辑:gufeng)
顶一下
(0)
0%
踩一下
(0)
0%
------分隔线----------------------------
发表评论
请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
评价:
栏目列表
点击提交代写需求
点击提交代写需求
点击提交代写需求
推荐内容