论文部分内容阅读
物流产业是国民经济发展的第三重要源泉,特别是进入21世纪以来,大力提倡发展现代物流产业,而车辆路径问题是现代物流的关键环节,对车辆路径问题的研究具有重要的理论及经济意义。1959年Dantzing和Ramser首次提出车辆路径问题(Vehicle Routing Problem, VRP),自提出以来,VRP问题一直是众多专家在运筹学、应用数学及计算机应用等学科领域的研究热点。根据约束条件的不同可以将VRP问题划分为多个调度问题。研究最早的是非对称TSP问题(Asymmetric Traveling Salesman Problem, ATSP);研究较多是的带容量约束车辆路径问题(Capacitated Vehicle Routing Problem, CVRP);研究中与实际结合紧密的是带软时间窗约束车辆路径问题(Vehicle Routing Problem with Soft Time Windows, VRPSTW)。VRP问题已经被证明具有NP-hard属性,在应用和理论上都有较高的研究意义。传统的精确算法不能对大规模的此类问题求解,因此需要用智能算法求得较优解。种群增量学习算法(Population-based Incremental Learning Algorithm, PBIL)是分布估计算法(Estimation of Distribution Algorithms,EDA)的一种,其特有的概率模型可以引导算法在优质解空间中的细致搜索。本文主要用种群增量学习算法对ATSP、CVRP、VRPSTW问题进行求解。(1)针对ATSP问题,提出了一种新的PBIL算法,将传统PBIL算法中的二进制编码方式改进为十进制的编码方式,减少编码的转换过程,设计新的学习概率矩阵更新方式,提高了算法的搜索效率。(2)针对带容量约束的问题,改进(1)中PBIL算法里的学习概率矩阵更新方式,使得全局搜索更加精确有效,和局部算法相结合,增强了算法的鲁棒性。(3)针对软时间窗问题,将(2)PBIL算法中融入均匀分布和轮盘赌两种选择方式,并加入2-opt和Insert局部搜索,将概率矩阵设计为三维,平衡全局搜索和局部搜索,提高算法的有效性和高效性。本文最后都用仿真实验和算法比较的方式,证明了上述所提出算法的有效性。