面向城市物流配送的车辆路径优化算法研究

作     者：马振鹏 焦晗暘 张哲 刘成 姜博 汪霖 

作者机构：西北大学信息科学与技术学院/新型网络智能信息服务国家地方联合工程研究中心 生成式人工智能与混合现实陕西省高等学校重点实验室 

出 版 物：《系统仿真学报》 (Journal of System Simulation)

年 卷 期：2024年

核心收录：

学科分类：12[管理学] 02[经济学] 0202[经济学-应用经济学] 1202[管理学-工商管理] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 020205[经济学-产业经济学] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：陕西省重点研发计划项目(2024GX-YBXM-149) 国家自然科学基金(42271140) 

主　　题：带时间窗的车辆路径问题 遗传算法 K-means聚类 大规模邻域搜索算法 

摘      要：针对现有优化算法求解带时间窗的车辆路径问题（vehicle routing problem with time windows， VRPTW）时存在易陷入局部最优解和收敛速度慢等问题，提出了一种基于K均值聚类和改进大规模邻域搜索算法（K-means clustering algorithm and improved large neighborhood search algorithm， K-means-ILNSA）的车辆路径优化算法。首先，采用先聚类后优化的策略，利用K-means算法对待配送客户进行分组，以提高优化效率。其次，采用遗传算法对聚类产生的每组客户进行单独优化，以初步规划配送路径。最后，引入大规模邻域搜索（large neighborhood search， LNS）算法对配送路径进一步优化，以有效避免算法陷入局部最优解。实验结果表明，所提算法能够有效解决带时间窗的车辆路径问题，其生成的车辆总路程短，优化求解效率高。