并行节约算法的自适应邻域选择策略  

The adaptive neighborhood selection strategy of the parallel Clarke-Wright algorithm

作　　者：付连宁[1] 崔文[2] 曾华[1] 

机构地区：[1]山东大学控制科学与工程学院,山东济南250061 [2]山东大学现代物流研究中心,山东济南250061

出　　处：《山东大学学报（工学版）》2012年第1期72-80,共9页Journal of Shandong University（Engineering Science）

基　　金：山东大学研究生自主创新基金资助项目(31400070613065);山东大学优秀研究生科研创新基金资助项目(10000080398154)

摘　　要：为了提高并行节约算法的运算效率,需要运用合理的邻域选择策略和数据结构来降低算法的空间和时间复杂度。以车辆路径问题(vehicle routing problem,VRP)的数据规模和客户点的分布情况为切入点,综合考虑客户点的邻域范围与距离、规模、分布情况的关系,提出一种基于自适应思想的邻域选择策略,提高邻域选择的合理性,通过进一步优化数据存储结构降低存储空间。多组仿真测试证实,与其他邻域选择策略相比,自适应策略可以在保证运算质量的前提下,大幅度提高节约算法的运算速度,降低存储空间,且针对客户点较为集中的VRP具有明显的优势,其中rl5915表现最为突出,运算时间只需要其他邻域选择策略的50%左右。理论研究和实验结果证实自适应邻域选择策略可以有效提高节约算法的运算速率。In order to improve the operation efficiency of the parallel saving algorithm,the reasonable neighborhood selection strategy and data structure were used to reduce the space and time complexity of the algorithm.A new scheme of the adaptive neighborhood selection strategy was adopted to improve the rationality of neighborhood selection through optimizing the neighborhood radius and data structure,with the data dimensions and customer distribution condition of VRP as the breakthrough point with comprehensive consideration of the relationship among the neighborhood range of the customer,distance,dimensions and distribution.Comparing the proposed scheme with other non-adaptived schemes,the results showed that the former had obvious advantages on concentrated VRP by significantly reducing computation time and storage space while guaranteeing the operation quality.Taking the rl5915 as an example,its operation time was 50% less than other non-adaptived strategies.Theory research and experimental results showed that adaptive neighborhood selection strategy could improve the operation efficiency of the saving algorithm.

关 键 词：节约算法 自适应邻域选择策略 邻域 车辆路径问题 性能评价 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]