文档介绍：目录
摘要 4
第一章绪论 7
7
7
第二章车辆路径问题的研究综述 9
9
9<br 10
第三章组合优化及现代启发式算法 13
组合优化问题 13
NP完全问题 13
14
14
现代启发式算法 14
第四章开放式车辆路径问题模型以及算法 19
问题的提出 19
OVRP数学模型的构建 20
OVRP中应用的蚁群优化算法 20
23
问题的构造 23
局部搜索 24
信息素更新 25
算法的后优化过程 26
实验和结果 26
算法的测试问题 26
算法中各类参数的设置 27
28
小结 30
第五章有时间窗的车辆路径问题的模型及算法 31
问题的提出 31
问题的描述及数学模型 31
33
自然编码遗传算法理论研究 33
染色体结构 36
遗传操作 37
遗传算法的计算结果 41
41
遗传算法的计算时间的比较 43
本章小结 43
第六章带时间窗和随机旅行时间车辆路径问题模型及算法 44
44
VRPSTW数学模型构建 44
45
VRPSTW带修正随机规划模型 48
VRPSTW的禁忌搜索算法 50
期望值求解和概率检查 50
52
邻域结构 52
禁忌对象和禁忌表 53
禁忌搜索算法的特赦标准 53
禁忌搜索算法的流程 53
实验结果 55
55
56
实验结果 56
小结 58
第七章结论 59
研究结论 59
进一步研究方向 59
参考文献: 60
致谢 63
摘要
在有关于物流配送的各种研究中,车辆路径问题是其中的运筹学和组合优化领域的研究前沿和热点问题。车辆路径问题主要是针对一系列已知需求量的客户,而后对行车的路线进行适当的组织以使得车辆在不违反任何约束条件的基础上提供服务,通过研究使得优化后的路线实现总成本最小的目的。通过对这一类问题进行有效的解决可以在很大程度上使得车辆的利用率得以提高,配送成本得以降低,同时还能有效提高配送时间的准确率,最终实现对物流服务水平进行提升的目的。实践证明车辆路径问题是一个典型的NP难题,如果只是采用传统的方法,要想得到问题的最优解或者是满意解就显得比较的困难,因此采用现代启发式算法来对这些问题进行求解是现代专家学者想要解决这类问题的关键。本文也就是以车辆路径问题作为主要的研究对象,综合利用了各种组合优化和现代启发式算法等工具,对三类比较常见而又重要的车辆路径问题模型极其优化算法进行了系统的研究。
,而后通过对哈密尔顿巡回式的车辆路径问题进行求解。文章首先给出了这类问题的数学模型,而后在这个数学模型的基础上,提出了求解开放式车辆路径问题的蚁群优化算法,通过进一步分析该蚂蚁算法的主体是一个在超立方框架下执行的MAX-MIN蚂蚁系统,该算法还在局部优化方面采用的是禁忌搜索算法,同时该算法还集成了一个后优化过程来进一步优化最优解。最后的时候,在标准测试问题的基础之上,系统的对算法的性能和求解质量进行了研究。
,而后在此基础之上提出了解决该问题的遗传算法。因为基于自然数解码的遗传算法具有一定的全局搜索能力,可以极大的跳出局部最优解,从而对有时间窗的车辆路径问题进行很好的解决。
,笔者首先就通过对标准车辆路径问题的拓展,引入新的边约束条件:时间窗、随机旅行时间和服务时间。而后根据优化标准的差异性,确定了该类问题的机会约束规划模型以及带修正随机规划模型。本文解决该类问题采用的就是建立在随机模拟的基础之上的禁忌搜索算法。而后通过基于随机产生的测试问题通过实验检验算法的有效性。