改进的ALNS算法求解MDVRPTW问题
Improved ALNS algorithm for solving multi-depots vehicle routing problem with time windows
李琳 1赵雄 1郑学东2
作者信息
- 1. 沈阳航空航天大学 理学院,沈阳 110136
- 2. 沈阳航空航天大学计算机学院,沈阳 110136
- 折叠
摘要
研究了带时间窗多车场车辆路径问题(multi-depots vehicle routing problem with time windows,MDVRPTW),建立MDVRPTW模型,设计了结合混合高斯模型(Gaussian mixture model,GMM)聚类算法的自适应大邻域搜索(adaptive large neighborhood search,ALNS)算法.通过在邻域变换前将客户集进行分类,优化初始解,提高算法运算效率.算法使用6种不同变换因子,采用得分系统对变换因子进行评价,使算法能够在迭代的不同阶段自适应地选择合适的变换因子.分析了参数设置值的合理性,设计了3组仿真实验,实验结果验证了算法的高效性.
Abstract
The multi-depots vehicle routing problem with time windows(MDVRPTW)was studied.The MDVRPTW model was designed,and an adaptive large neighborhood search algorithm combined with the Gaussian mixture model(GMM)clustering algorithm was proposed.By classifying the cus-tomer set before the neighborhood transformation,the initial solution was optimized,and the algo-rithm efficiency was improved.Six different transformation factors were used.A scoring system was used to enable the algorithm to select appropriate transformation factor adaptively at different stages of the iteration.The rationality of parameter was analyzed and three simulation experiments were de-signed.The experimental results verifies the efficiency of the algorithm.
关键词
多车场车辆路径问题/时间窗/改进的ALNS算法/GMM聚类算法/邻域变换Key words
MDVRP/time windows/improved ALNS algorithm/GMM clustering algorithm/neigh-borhood transformation引用本文复制引用
基金项目
国家自然科学基金(61972266)
国家自然科学基金(61403260)
辽宁省自然科学基金(2020-MS-233)
辽宁省兴辽英才计划(XLYC2002017)
出版年
2024
国家科技期刊平台
NSTL
万方数据