两阶段算法求解多车场车辆路径问题

来源：信息与控制杂志2020年第6期北京时间：

作者：李洋, 胡蓉, 钱斌, 金怀平

摘要：提出了一种两阶段算法（TSA）用于求解多车场车辆路径问题（MDVRP）.两阶段算法的第1阶段为分解阶段.多车场问题具有更大的可行解区域，为有效控制问题的求解规模并合理引导算法在优质解区域搜索，在该阶段提出了一种融合最近邻算法的混合高斯聚类算法（HGMA），将多车场车辆路径问题分解为一系列单个车场车辆问题.两阶段算法的第2阶段为问题求解阶段.在该阶段提出了一种增强蚁群算法（EACO）求解分解后的各子问题，进而获得原问题的解.在增强蚁群算法中引入了信息素挥发系数控制因子进一步动态调节信息素挥发系数，从而有效地控制了信息素的挥发，提高了算法的全局搜索能力，并且设计了基于多种变邻域操作的两阶段变邻域局部搜索（TVNS）来增强算法的局部搜索能力.在不同规模问题上的仿真和对比实验验证了所提两阶段算法的有效性.

关键词：车辆路径问题(VRP), 多车场, 混合高斯模型, 最大期望算法, 最近邻算法, 增强蚁群算法