求解多车场车辆路径问题的分散搜索算法

作者：张军; 唐加福; 潘震东

来源：系统工程, 2009, 27(06): 83-90.

• 多车场车辆路径问题
• 分散搜索算法
• 2-交换
• 2-交换*
• 最坏移出-预测插入启发式

提出了一种求解多车场车辆路径问题(Multi-depot Vehicle Routing Problem,MDVRP)的分散搜索算法(Scatter Search,SS)。该算法基于顾客信息进行编码,采用扫描算法(Sweep algorithm)与最优划分过程产生待选解集;通过启发式规则选择不同解包含的弧来生成新解;并由2-交换、2-交换*及最坏移出-预测插入启发式三种局部搜索策略构成迭代下降算法对解进行改进。通过采用文献中随机生成的小规模数据及MDVRP的Benchmark问题对算法进行测试,验证了算法的有效性。

• 单位
  东北大学; 流程工业综合自动化国家重点实验室