改进最近邻算法求解多车场车辆路径问题  

Improved Nearest Neighbor Algorithm for Multi Depot Vehicle Routing Problem

作　　者：李焱 潘大志[1,2] LI Yan;PAN Dazhi(School of Mathematics&Information,Xihua Normal University,Nanchong 637009;Sichuan Provincial Key Laboratory of Optimization Theory and Application,Nanchong 637009)

机构地区：[1]西华师范大学数学与信息学院,南充637009 [2]最优化理论与应用四川省高校重点实验室,南充637009

出　　处：《计算机与数字工程》2024年第9期2634-2639,共6页Computer & Digital Engineering

基　　金：国家自然科学基金项目(编号:11871059);四川省教育厅自然科学基金项目(编号:18ZA0469);西华师范大学英才科研基金项目(编号:17YC385)资助。

摘　　要：论文提出了一种改进最近邻算法用于求解多车场车辆路径问题(multi-depot vehicle routing problem,MDVRP)。为了求解问题解空间得到有效控制,融合最近邻算法与K-means算法的优势对客户进行较为合理的车场分配,将多车场车辆路径问题分解成多个单车场车辆路径子问题。在子问题的求解阶段,提出一种编解码规则,基于车辆装载量利用率得到提高,减少车场车辆路径长度,设计了全局优化策略,基于车辆内部客户访问顺序及车辆间客户改变导致路径长度变化,设计了局部优化策略,提出了随车辆服务客户数变化而变化的搜索策略,提高了算法的运行效率。在不同规模的问题和仿真实验上验证了所提算法的有效性。In this paper,an improved nearest neighbor algorithm is proposed to solve the multi depot vehicle routing problem(MDVRP)In order to effectively control the solution space of the problem.This paper integrates the advantages of the nearest neighbor algorithm and K-means algorithm to allocate more reasonable parking lots for customers,and decomposes the multi parking lot vehicle routing problem into multiple single parking lot vehicle routing subproblems.In the solution phase of the subproblems,a coding and decoding rule is proposed.Based on the improved utilization of vehicle loading,the length of parking lot vehicle routing is reduced,and a global optimization strategy is designed.Based on the customer access sequence inside the vehicle and the change of path length caused by the change of customers between vehicles,a local optimization strategy is designed,and a search strategy that changes with the number of customers served by the vehicle is proposed,which improves the operation efficiency of the algorithm.The effectiveness of the proposed algorithm is verified on problems of different scales and simulation experiments.

关 键 词：车辆路径问题 多车场 最近邻算法 K-均值算法 

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