车辆路径问题地启发式算法研究

《车辆路径问题地启发式算法研究》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、目录摘要4第一章绪论71.1研究背景71.2研究意义7第二章车辆路径问题的研究综述92.1车辆路径问题描述92.2车辆路径问题分类92.3国内外对车辆路径问题的研究动态和水平10第三章组合优化及现代启发式算法133.1组合优化问题133.2NP完全问题133.3启发式算法143.3.1传统启发式算法143.3.2现代启发式算法14第四章开放式车辆路径问题模型以及算法194.1问题的提出194.2OVRP数学模型的构建204.3OVRP中应用的蚁群优化算法204.3.1算法的信息初始化234.3.2问题的构造234.3.3局部搜索244.3.4信息素更新254.3.5算法的后优化过程264.4实

2、验和结果264.4.1算法的测试问题264.4.2算法中各类参数的设置274.4.3算法的实验结果284.5小结30第五章有时间窗的车辆路径问题的模型及算法315.1问题的提出315.2问题的描述及数学模型315.3遗传算法求解VRPTW335.3.1自然编码遗传算法理论研究335.3.2染色体结构365.3.4遗传操作375.4遗传算法的计算结果415.4.1遗传算法与其他启发式算法的比较415.4.2遗传算法的计算时间的比较435.5本章小结43第六章带时间窗和随机旅行时间车辆路径问题模型及算法446.1问题的提出446.2VRPSTW数学模型构建44636.2.1VRPSTW机会约束规划

3、模型456.2.2VRPSTW带修正随机规划模型486.3VRPSTW的禁忌搜索算法506.3.1期望值求解和概率检查506.3.2解的评价526.3.4邻域结构526.3.5禁忌对象和禁忌表536.3.6禁忌搜索算法的特赦标准536.3.7禁忌搜索算法的流程536.4实验结果556.4.1测试问题556.4.2参数的设置566.4.3实验结果566.5小结58第七章结论597.1研究结论597.2进一步研究方向59参考文献：60致谢636363摘要在有关于物流配送的各种研究中，车辆路径问题是其中的运筹学和组合优化领域的研究前沿和热点问题。车辆路径问题主要是针对一系列已知需求量的客户，而后对行

4、车的路线进行适当的组织以使得车辆在不违反任何约束条件的基础上提供服务，通过研究使得优化后的路线实现总成本最小的目的。通过对这一类问题进行有效的解决可以在很大程度上使得车辆的利用率得以提高，配送成本得以降低，同时还能有效提高配送时间的准确率，最终实现对物流服务水平进行提升的目的。实践证明车辆路径问题是一个典型的NP难题，如果只是采用传统的方法，要想得到问题的最优解或者是满意解就显得比较的困难，因此采用现代启发式算法来对这些问题进行求解是现代专家学者想要解决这类问题的关键。本文也就是以车辆路径问题作为主要的研究对象，综合利用了各种组合优化和现代启发式算法等工具，对三类比较常见而又重要的车辆路径问题

5、模型极其优化算法进行了系统的研究。1.针对开放式车辆路径问题对于这一类问题的解决笔者主要采用的是通过假设将标准车辆路径问题的路线进行松弛成为哈密尔顿巡回，而后通过对哈密尔顿巡回式的车辆路径问题进行求解。文章首先给出了这类问题的数学模型，而后在这个数学模型的基础上，提出了求解开放式车辆路径问题的蚁群优化算法,通过进一步分析该蚂蚁算法的主体是一个在超立方框架下执行的MAX-MIN蚂蚁系统，该算法还在局部优化方面采用的是禁忌搜索算法，同时该算法还集成了一个后优化过程来进一步优化最优解。最后的时候，在标准测试问题的基础之上，系统的对算法的性能和求解质量进行了研究。2.针对研究了带时间窗的车辆路径问题对

6、于这类问题笔者首先进行了数学建模，而后在此基础之上提出了解决该问题的遗传算法。因为基于自然数解码的遗传算法具有一定的全局搜索能力，可以极大的跳出局部最优解，从而对有时间窗的车辆路径问题进行很好的解决。3.针对带时间窗和随机旅行时间车辆路径问题进行了研究，笔者首先就通过对标准车辆路径问题的拓展，引入新的边约束条件：时间窗、随机旅行时间和服务时间。而后根据优化标准的差异性，确定了该类问题的机会约束规划模型以及带修正随机规划模型。本文解决该类问题采用的就是建立在随机模拟的基础之上的禁忌搜索算法。而后通过基于随机产生的测试问题通过实验检验算法的有效性。关键字：车辆路径遗传算法禁忌搜索算法随机规划模型研

7、究意义63AbstractOnthelogisticsanddistributionofthevariousresearch,vehicleroutingproblemisoneoftheoperationalresearchandcombinatorialoptimizationofresearchinthefieldoffrontierandhotissue.Thevehiclerouting