基于模拟退火在VRP法的启发式算法中的应用

雩风三日

基于模拟退火在VRP法的启发式算法中的应用
2 V2 w4 `3 W/ ~; m2 E( }! u
! Z9 @3 [0 e1 d2 U& V5 d9 X    VRP问题在现实生活中应用广泛，很多领域的问题都可以抽象成VRP问题进行解决，其研究和应用一直是热点。
    本文首先详细介绍了VRP问题的分类，常见的约束条件及基本的研究技术和方法。给出了几个基本VRP问题的介绍及其数学模型。
    模拟退火算法(SA)相对于其它智能算法在求解VRP问题时具有收敛速度快且能找到全局最优解的优点。因此本文详细介绍了模拟退火算法的数学模型及其寻优方法，证明了模拟退火算法可以找到全局最优解，研究了模拟退火算法优缺点。基于模拟退火算法给出了固定车辆数单目标VRP问题的M工ATLAB语言算法。
    本文对一个中心仓库的不确定车辆数的有时间窗的闭合VRP问题结合案例进行了研究，给出了两种求解方法。第一种方法，利用优先处理时间窗口策略大大简化了VRP问题，接着结合图形，通过排列组合给出了所有可能的VRP路径，其中最短VRP路径即为所求。第二种方法，首先把VRP转化成图论语言，构造了图G;其次通过时间窗口限制，利用图论染色算法对G进行染色，得到了图G的最大独立
  d7 n" ~; M5 Y9 T集，其中独立集集阶最大数为K，则K即为VRP问题最小车辆数。接着，固定最小车辆数K，给出了基于图论贪心搜索算法的固定车辆数单目标VRP问题算法，并结合该案例给出了求解结果。
    本文对多中心仓库确定车辆数的闭合VRP问题结合案例进行了研究。主要研究成果即分两个阶段实现了问题求解。第一个阶段实现了将多目标问题转化为单目标问题，给出了圆域扩充算法;第二阶段求解了多车辆数的单目标VRP问题。求解分为四个过程:第一过程，首先，研究了基于模拟退火算法的最短TSP路径算法。第二过程，首先利用该算法给出了中心仓库3的最短TSP路径。接着基于TSP最短路径，给出了客户集相对中心仓库分布均匀且中心仓库较集中的基于模拟退火的启发式算法，并进行了求解，给出了中心仓库3的较优VRP路径。第三过程，首先利用基于模拟退火算法的最短TSP路径算法求解了中心仓库1的最短TSP路径，接着给出了基于扫描法的多车辆数单目标VRP问题启发式算法，并进行了求解，给出了中心仓库1的较优VRP路径。第四过程，首先利用基于模拟退火算法的最短TSP路径算法求解了中心仓库2的最短TSP路径，接着对该VRP进行了转化，分别转化为上述两种情况，并利用相应的算法进行了求解，最后取VRP路径短者为中心仓库2的较优VRP路径。

关键词:VRP问题;模拟退火算法;染色算法;贪心算法;扫描法