论文部分内容阅读
车辆路径规划是物流领域中重要问题之一。其本质是多约束条件多目标组合优化问题。第二代非支配排序遗传算法(Non-dominated Sorting Genetic Algorithm Ⅱ,NSGA-Ⅱ),近年来多被用于处理多目标车辆路径问题,但是NSGA-Ⅱ在面对三个及以上的目标优化问题时,算法收敛性和解的多样性效果不好,算法容易陷入局部最优。而目前物流领域车辆路径规划中涉及的约束条件和求解目标越来越复杂,基于NSGA-Ⅱ的车辆路径规划效果亟待提高。针对以上不足,本文探索基于非支配排序遗传算法的车辆路径规划改进方法,主要研究内容如下:(1)构建多目标车辆路径规划数学模型。该模型以车辆容量约束、单回路约束等因素为约束条件,以运输车辆数量、调度距离以及客户服务满意度水平三个因素为目标优化车辆路径;同时,分析了道路拥堵情况,提出了动态车辆路径规划模型,以及动态的车辆路径调整方法。(2)采用第三代非支配排序遗传算法(Non-dominated Sorting Genetic Algorithm Ⅲ,NSGA-Ⅲ)对多目标车辆路径问题求解。针对NSGA-Ⅱ在处理三个及以上目标时容易陷入局部最优,本文采用NSGA-Ⅲ算法对多目标车辆路径问题求解,提高多目标车辆路径规划的目标值。(3)提出一种新的算法混合第三代非支配排序遗传算法(Hybrid Non-dominated Sorting Genetic Algorithm Ⅲ,H-NSGA-Ⅲ)加快多目标车辆路径问题求解速率。H-NSGA-Ⅲ针对NSGA-Ⅲ算法收敛速率慢的问题,改进NSGA-Ⅲ算法提出了混合交叉算子、交叉概率和变异概率调整机制以提高算法收敛速率,从而提高求解车辆路径问题的效率。(4)提出了基于道路拥堵的动态车辆路径调整算法。针对车辆在按路径规划方案执行配送任务过程中,遇到将要配送的下一个客户路段拥堵的情况,提出了路径调整方法。(5)实验验证H-NSGA-Ⅲ算法的有效性和高效性。通过实验验证,H-NSGA-Ⅲ算法对比NSGA-Ⅲ算法、NSGA-Ⅱ算法,在车辆路径问题中,能够取得更好的目标值和提高算法的收敛速率,并分析了 H-NSGA-Ⅲ算法中提出的混合交叉算子,其性能优于单独用其中一种交叉算子的算法,从而证明了 H-NSGA-Ⅲ算法适用于解决多目标车辆路径问题。最后对大连中通物流进行仿真实验,分析得到的物流配送路径规划方案的可行性。