《车辆路径问题求解算法分析综述》2000字

车辆路径问题求解算法分析综述1.1算法概述车辆路径问题一般会有多个约束条件叠加，这会增加问题求解的复杂程度，所以此类问题属于NP难题，针对车辆路径问题的求解算法从早期的精确算法逐渐发展到大规模的智能优化算法。根据目前的研究成果，求解此类问题的方法总体上可分为精确算法和启发式算法，具体如图2-1所示REF_Ref25478\r\h[1]。图2-1VRP问题的常用求解算法精确算法精确算法可以在有限的计算步骤内求出问题的最优解，但计算时间会随着问题规模的增加以指数速度上升，所以只适用于规模较小的问题。由于实际问题具有系统性与复杂性，尤其是针对车辆路径问题等NP难题而言，使用精确算法所产生的成本可能是无法接受甚至不现实的，不适合大多数的配送模型。传统启发式算法为了在可接受的计算成本范围内进行复杂问题的求解，学者引入了启发式算法。此类方法要求研究人员通过经验总结、实验分析等方式对求解过程进行引导，使得可以在较短时间内找到可接受的满意解。传统启发式算法需要针对具体问题模型设计相应的算法，通常用来解决组合优化问题，具有计算速度快、程序较为简单等优点。但是由于搜索范围的局限性，该方法无法保证求得最优解。同时，传统启发式算法是通过局部搜索技术找到满意解的，容易陷入局部最优。亚启发式算法亚启发式算法又称元启发式算法，通过全局搜索获取满意解，找到全局最优解的概率更高。此类算法是以自然界或人类社会中的一些智能现象为基础产生的，例如遗传算法源于自然界中生物的遗传、自然选择等进化规律，蚁群算法源于蚂蚁在觅食过程中的群体行为，粒子群算法源于鸟群的捕食行为，模拟退火算法源于热力学中固体的退火过程。1.2遗传算法算法原理遗传算法是一种可以实现全局优化的自适应概率搜索算法，主要启于生物进化中“适者生存”的规律，即自然环境中适应能力越高的群体往往会产生更加优秀的后代。通过模拟个体交叉和染色体基因突变等现象产生候选解，然后按照一定原则从中选择较优的个体，不断重复上述操作，直至得到达到终止条件的满意解。算法组成要素编码：将优化问题的解转变成位串的形式，便于解的表达和计算。主要方式有二进制编码、格雷编码、序列编码和大字符集编码等。适应度函数：是个体优劣的唯一评价指标，应结合求解问题的要求设定。该值越大说明相应个体的质量越好，则被遗传到下一代群体的概率更高。遗传算子：包括选择算子、交叉算子和变异算子。选择算子是根据个体的适应度，按照一定规则选择性能优良的父代，常用方法包括轮盘赌选择、超比例选择、种马进化算法、锦标赛选择等；交叉算子是将群体中挑选出的个体随机搭配成对，通过互换个体间的部分染色体进而产生新个体，常用的交叉方法包括单点交叉、多点交叉、均匀交叉、洗牌交叉等；变异算子是按照变异概率更改个体数据串中的部分值，由此可减少种群规模较小导致的近亲繁殖的情况。变异概率对算法性能的影响很大，该值过高会趋向于随机搜索，过低会导致近亲繁殖等问题，难以找到满意解。控制参数：包括初始种群的个数、交叉概率、变异概率及遗传操作的终止条件等。其中，终止条件主要包括：算法进化代数达到预定值；遗传搜索找到较为理想的目标值；个体的适应度函数值趋于稳定，即种群难以继续优化。算法步骤遗传算法步骤如图2-2所示。图2-2遗传算法步骤算法优点并行计算，全局搜索能力强。遗传算法是对由多个体组成的群体进行操作处理，即可以同时使用多个搜索点的信息，在一次搜索循环中可以覆盖到较大规模的个体，在全局搜索方面有明显的优势，适合复杂性问题。适用范围广。遗传算法通过适应度函数即可得到进一步的搜索方向和搜索范围，而且对目标函数的限制条件极少，因此该算法适合于目标函数无法求导或导数不存在的优化问题及优化组合问题。具有很好的灵活性。遗传算法的选择、交叉、变异操作可通过参数设定进行控制的，对操作算子进行优化，可以引导种群会产生更多优良的个体。算法缺点容易陷入局部最优，出现“早熟”现象。遗传算法是通过交叉操作和变异操作产生新个体的，但在算法后期，优势个体可能占据大部分种群、交叉操作难以产生新个体；此时变异操作又受到变异概率的限制，则会出现过早收敛的情况，导致算法的最终解并非满意解。无法保证每次都收敛到相同的解。由于遗传算法会受到随机概率的影响，所以无法保证算法解的良好收敛性。1.3模拟退火算法算法原理模拟退火算法源自于固体退火现象，首先在高温下进行粗略搜索，可以快速进入“热平衡”状态，然后随着温度逐渐减低，各状态出现概率的差距逐渐扩大，搜索精度提高，使收敛到全局最小点。该算法的优势就是具有概率突跳特性，即能够以一定概率接受差解，在得到局部最优解后可以继续寻优，最终实现全局最优。算法步骤该算法使用Metropolis准则判断是否接受新解，即当新解优于原解时，选择接受新解；当新解劣于原解时，以概率exp(−∆fTi图2-3模拟退火算法步骤算法特点局部搜索能力强。模拟退火