改进的ALNS算法求解MDVRPTW问题  

Improved ALNS algorithm for solving multi-depots vehicle routing problem with time windows

作　　者：李琳 赵雄 郑学东 LI Lin;ZHAO Xiong;ZHENG Xuedong(College of Science,Shenyang Aerospace University,Shenyang 110136,China;College of Computer Science,Shenyang Aerospace University,Shenyang 110136,China)

机构地区：[1]沈阳航空航天大学理学院,沈阳110136 [2]沈阳航空航天大学计算机学院,沈阳110136

出　　处：《沈阳航空航天大学学报》2024年第2期86-96,共11页Journal of Shenyang Aerospace University

基　　金：国家自然科学基金(项目编号:61972266,61403260);辽宁省自然科学基金(项目编号:2020-MS-233);辽宁省兴辽英才计划(项目编号:XLYC2002017)。

摘　　要：研究了带时间窗多车场车辆路径问题(multi-depots vehicle routing problem with time windows,MDVRPTW),建立MDVRPTW模型,设计了结合混合高斯模型(Gaussian mixture model,GMM)聚类算法的自适应大邻域搜索(adaptive large neighborhood search,ALNS)算法。通过在邻域变换前将客户集进行分类,优化初始解,提高算法运算效率。算法使用6种不同变换因子,采用得分系统对变换因子进行评价,使算法能够在迭代的不同阶段自适应地选择合适的变换因子。分析了参数设置值的合理性,设计了3组仿真实验,实验结果验证了算法的高效性。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 customer set before the neighborhood transformation,the initial solution was optimized,and the algorithm 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 designed.The experimental results verifies the efficiency of the algorithm.

关 键 词：多车场车辆路径问题 时间窗 改进的ALNS算法 GMM聚类算法 邻域变换 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]