两级车辆路径问题的多起始点变邻域下降算法

作者：曾正洋; 许维胜; 徐志宇; 倪嘉呈

来源：同济大学学报(自然科学版), 2014, (10): 1530-1535.

• 两级车辆路径问题
• 多起始点方法
• 变邻域下降算法
• 分割算法 two-echelon vehicle routing problem
• multi-start methods
• variable neighborhood descent algorithm
• Split algorithm

两级车辆路径问题是指货物必须首先由中心仓库配送至中转站(第一级),再转运至需求点(第二级)的一种新型车辆路径问题.针对该问题特性,提出一种多起始点变邻域下降求解算法.首先由改进的Split算法循环分割由所有需求点组成的随机排列,直至出现可行的第二级配送方案,然后求解第一级问题,获得完整的初始可行解,再通过变邻域下降算法进一步改进.当变邻域下降算法无法改进时,采用多起始点技术重复上述过程,直至算法终止.实验结果表明,所提出的算法易于实现,且性能优于已有最好的两种启发式算法.

• 出版日期2014
• 单位同济大学