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

山东大学学报(工学版) ›› 2012, Vol. 42 ›› Issue (1): 72-80.

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

付连宁¹, 崔文², 曾华¹

1. 山东大学控制科学与工程学院, 山东济南 250061;
2. 山东大学现代物流研究中心, 山东济南 250061

收稿日期:2011-01-19 出版日期:2012-02-20 发布日期:2011-01-19
作者简介:付连宁(1986- ),女，山东青岛人，博士研究生，主要研究方向为智能交通和优化算法.Email:fulianning@126.com
基金资助:
山东大学研究生自主创新基金资助项目(31400070613065);山东大学优秀研究生科研创新基金资助项目(10000080398154)

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

FU Lian-ning¹, CUI Wen², ZENG Hua¹

1. School of Control Science and Engineering, Shandong University, Jinan 250061, China;
2. The Logistics Institute, Shandong University, Jinan 250061, China

Received:2011-01-19 Online:2012-02-20 Published:2011-01-19

摘要/Abstract

摘要：

为了提高并行节约算法的运算效率,需要运用合理的邻域选择策略和数据结构来降低算法的空间和时间复杂度。以车辆路径问题(vehicle routing problem, VRP)的数据规模和客户点的分布情况为切入点,综合考虑客户点的邻域范围与距离、规模、分布情况的关系,提出一种基于自适应思想的邻域选择策略,提高邻域选择的合理性,通过进一步优化数据存储结构降低存储空间。多组仿真测试证实,与其他邻域选择策略相比,自适应策略可以在保证运算质量的前提下,大幅度提高节约算法的运算速度,降低存储空间,且针对客户点较为集中的VRP具有明显的优势,其中rl5915表现最为突出,运算时间只需要其他邻域选择策略的50％左右。理论研究和实验结果证实自适应邻域选择策略可以有效提高节约算法的运算速率。

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

Abstract:

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.

Key words: saving algorithm, adaptive neighborhood selection, neighborhood, vehicle routing problem, performance evaluation

付连宁1, 崔文2, 曾华1. 并行节约算法的自适应邻域选择策略[J]. 山东大学学报(工学版), 2012, 42(1): 72-80.

FU Lian-ning1, CUI Wen2, ZENG Hua1 . The adaptive neighborhood selection strategy of the parallel Clarke-Wright algorithm[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2012, 42(1): 72-80.

参考文献

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

[1]	钟智彦,文志强, 张潇云,叶德刚. 基于半色调图像的邻域相似性描述子方法[J]. 山东大学学报(工学版), 2016, 46(3): 58-64.
[2]	梅清琳,张化祥. 基于全局距离和类别信息的邻域保持嵌入算法[J]. 山东大学学报(工学版), 2016, 46(1): 10-14.
[3]	吴克寿,陈玉明,曾志强. 基于邻域关系的决策表约简[J]. 山东大学学报(工学版), 2012, 42(2): 7-10.
[4]	曾华1,崔文2,付连宁1,吴耀华1*. Lin-Kernighan算法初始解的启发式构造策略[J]. 山东大学学报(工学版), 2012, 42(2): 30-35.
[5]	浦剑1 ,张军平1 ，黄华2 . 超分辨率算法研究综述[J]. 山东大学学报(工学版), 2009, 39(1): 27-32.