求解车辆路径问题的改进扰动机制的ILS算法

Iterated Local Search Algorithm with Improved Perturbation Mechanism for Vehicle Routing Problem

针对车辆路径问题,提出一种改进的迭代局部搜索(ILS)算法。该算法基于破坏再重建(Ruin and Recreate)的思想,设计了一种新的扰动机制。扰动过程包含破坏和重建两个阶段,即先使用一种兼顾随机性和相关性的破坏方法对解进行破坏,并引入扰动因子控制解的破坏强度,然后再随机选择基本贪婪插入和改进贪婪插入算法完成解的修复。利用国际标准测试案例对常规扰动机制和改进后的扰动机制进行了测试,并与量子进化算法、蜂群算法进行了比较,实验结果表明改进后的ILS算法更加有效。

This paper proposed an iterated local search（ILS）algorithm with a new perturbation mechanism for vehicle routing problem.The perturbation mechanism is based on ruin and recreating principle,which includes destroying and repair procedures.The best local neighborhood solution is firstly destroyed by a method which takes randomness and correlation into account.In the destroying process,aperturbation factor is also introduced into the perturbation mechanism to control the strength of destroying.And then the destroyed solution is repaired by randomly selecting basic greedy insertion and regret greedy insertion algorithms.The experiments on the benchmark instances prove that the developed algorithm is more effective when compared with quantum evolutionary algorithm and artificial bee colony.