文档介绍：⑧硕士学位论文 MASTER’S THESIS VRP based on theSimulated annealing algorithm SubmiRed inPartialFulfillment of theRequirement For theMaster's Degree inOperations Research and By Postgraduate Program School ofMathematics and Statistics Central China Normal University Supervisor:Zhaodongfang Academic Title:Professor Signa ⑧硕士学位论文 MASTER’S THESIS 华中师范大学学位论文原创性声明和使用授权说明原创性声明本人郑重声明:所呈交的学位论文,是本人在导师指导下,独立进行研究工作所取得的研究成果。除文中已经标明引用的内容外,本论文不包含任何其他个人或集体己经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体,均己在文中以明确方式标明。本声明的法律结果由本人承担。作者签氢呆泰、手日期:幻I;、使用学位论文的规定,即:研究生在校攻读学位期间论文工作的知识产权单位属华中师范大学。学校有权保留并向国家有关部门或机构送交论文的复印件和电子版,允许学位论文被查阅和借阅; 学校可以公布学位论文的全部或部分内容,可以允许采用影印、缩印或其它复制手段保存、汇编学位论文。(保密的学位论文在解密后遵守此规定) 保密论文注释:本学位论文属于保密,在——年解密后适用本授权书。非保密论文注释:本学位论文不属于保密范围,适用本授权书。作者签名:呆熬手作者签名:芥拳:曼r 日期:幻I,年箩月n日糊虢粑黪日期泓≥仃月懒本人已经认真阅读“CALIS高校学位论文全文数据库发布章程”,同意将本人的学位论文提交“CALIS高校学位论文全文数据库”中全文发布,并可按“章程”中的规定享受相作者签名: 日期:绷多年箩月2二日嘲知l>年p硼⑧硕士学位论文 MASTER’S THESIS 摘要 VRP问题在现实生活中应用广泛,很多领域的问题都可以抽象成VRP问题进行解决,其研究和应用一直是热点。本文首先详细介绍了VRP问题的分类,常见的约束条件及基本的研究技术和方法。给出了几个基本VRP问题的介绍及其数学模型。模拟退火算法(SA)相对于其它智能算法在求解VRP问题时具有收敛速度快且能找到全局最优解的优点。因此本文详细介绍了模拟退火算法的数学模型及其寻优方法,证明了模拟退火算法可以找到全局最优解,研究了模拟退火算法优缺点。基于模拟退火算法给出了固定车辆数单目标VRP问题的MATLAB语言算法。本文对一个中心仓库的不确定车辆数的有时间窗的闭合Ⅵ姆问题结合案例进行了研究,给出了两种求解方法。第一种方法,利用优先处理时间窗口策略大大简化了VRP问题,接着结合图形,通过排列组合给出了所有可能的VRP路径,其中最短VRP路径即为所求。第二种方法,首先把VRP转化成图论语言,构造了图G; 其次通过时间窗口限制,利用图论染色算法对g进行染色,得到了图g的最大独立集,其中独立集集阶最大数为K,则K即为VRP问题最小车辆数。接着,固定最小车辆数K,给出了基于图论贪心搜索算法的固定车辆数单目标VRP问题算法,并结合该案例给出了求解结果。本文对多中心仓库确定车辆数的闭合VRP问题结合案例进行了研究。主要研究成果即分两个阶段实现了问题求解。第一个阶段实现了将多目标问题转化为单目标问题,给出了圆域扩充算法;第二阶段求解了多车辆数的单目标VRP问题。求解分为四个过程:第一过程,首先,研究了基于模拟退火算法的最短TSP路径算法。第二过程,首先利用该算法给出了中。tS,仓库3的最短TSP路径。接着基于TSP最短路径,给出了客户集相对中心仓库分布均匀且中心仓库较集中的基于模拟退火的启发式算法,并进行了求解,给出了中心仓库3的较优VRP路径。第三过程,首先利用基于模拟退火算法的最短TSP路径算法求解了中心仓库1的最短TSP路径,接着给出了基于扫描法的多车辆数单目标VRP问题启发式算法,并进行了求解,给出了中心仓库1的较优VRP路径。第四过程,首先利用基于模拟退火算法的最短TSP路径算法求解了中心仓库2的最短TSP路径,接着对该VRP进行了转化,分别转化为上述两种情况,并利用相应的算法进行了求解,最后取VRP路径短者为中心仓库2的较优Ⅵ强路径。关键词:VRP问题;模拟退火算法;染色算法;贪心算法;扫描法 Abstract VRP iswidely used problems ca