改进最近邻算法求解多车场车辆路径问题
李焱1
潘大志2
1.西华师范大学数学与信息学院 南充 6370092.西华师范大学数学与信息学院 南充 637009;最优化理论与应用四川省高校重点实验室 南充 637009
摘要：论文提出了一种改进最近邻算法用于求解多车场车辆路径问题(multi-depot vehicle routing problem,MD-VRP).为了求解问题解空间得到有效控制,融合最近邻算法与K-means算法的优势对客户进行较为合理的车场分配,将多车场车辆路径问题分解成多个单车场车辆路径子问题.在子问题的求解阶段,提出一种编解码规则,基于车辆装载量利用率得到提高,减少车场车辆路径长度,设计了全局优化策略,基于车辆内部客户访问顺序及车辆间客户改变导致路径长度变化,设计了局部优化策略,提出了随车辆服务客户数变化而变化的搜索策略,提高了算法的运行效率.在不同规模的问题和仿真实验上验证了所提算法的有效性.
关键词：车辆路径问题多车场最近邻算法K-均值算法
分类号：TP301.6(计算技术、计算机技术)
资助基金：国家自然科学基金(11871059)四川省教育厅自然科学基金项目(18ZA0469)西华师范大学英才科研基金项目(17YC385)
论文发表日期：2024-09-20
在线出版日期：2025-08-15（本平台首次上网日期，不代表文献的发表时间）
页数：6( 2634-2639 )
英文信息