论文摘要
车辆路径问题是一个经典的组合优化问题,最早由著名学者Dantzig和Ramser于1959年提出。由于该问题将理论研究和实际应用紧密地联系在一起,因此自提出以来就引起了包括计算机科学、运筹学、组合数学、管理学等多个学科专家学者的高度重视。到目前为止,用于求解车辆路径问题的方法已可划分为三类,即精确优化方法、传统启发式方法、现代启发式算法即智能优化算法。国内外研究者目前基本都集中在对智能优化算法的研究上。遗传算法是一种模拟自然界生物进化过程的智能搜索算法,作为一种有效的全局优化工具,它具有简单通用、稳健性强和适合于并行分布处理等特点,以及自组织性、自适应性和自学习性等智能特性,可用于解决组合优化、机器学习、自适应控制等智能问题。本文采用遗传算法来求解车辆路径问题,主要的研究工作和创新如下:1)通过对大量相关文献进行分析、总结和提炼,对车辆路径问题的起源和发展、研究及应用的价值以及研究现状进行了概述;阐明了论文研究的背景及意义、选题的理由及本文的主要工作;并指出了目前车辆路径问题研究中存在的不足,为本文的研究做了铺垫。2)讨论了遗传算法的基本优化原理、算法结构和设计过程;分析了遗传算法的特点以及它的不足之处和优化策略;针对遗传算法在进化过程中,由于种群多样性降低而导致过早收敛的缺点,设计了一个双重改进的遗传算法DIGA:借鉴免疫算法通过抗体浓度抑制以保持种群多样性的优势,在遗传算法中引入个体浓度控制操作;借鉴模拟退火算法的个体选择方法,改进了遗传算法的选择策略,使算法能够以一定的概率跳出局部最优的状态;在遗传算法中引入“精英保留”策略,保证算法的全局收敛性。3)分析了车辆路径问题所包含的各类约束条件;总结了求解车辆路径问题的几类方法及其特点;重点研究了车辆数和容量均受限的多目标车辆路径问题,为其建立了相应的数学模型,并将改进的遗传算法DIGA用于求解该问题,给出了算法的结构和详细设计过程。4)从实验的角度分析了DIGA算法求解车辆路径问题的性能:①选用目前国内外通用的经典测试库中的若干测例,进行实验测试和分析,验证算法的有效性和良好的性能;②选用一些权威期刊文献中提供的测试数据进行实验,将本文的实验结果与其他文献上的实验结果进行比较和分析,验证了算法的搜索效率和解的质量。结论部分总结了全文的主要工作和创新之处,分析了研究中的不足,并对未来的研究作了展望。