A Modified Ant Colony System Hybridized with Insert and Swap Heuristic Algorithms for the Vehicle Routing Problem with Time Windows

The vehicle routing problem with time windows (VRPTW) is one of the most well-known combinatorial problems in the transportation domain. Because this problem belongs to NP-Hard problems¡ many researchers have presented meta-heuristics for it. In this paper¡ aimed at the disadvantages existed in the current Ant Colony System (ACS)¡ a modification of this algorithm called HACS is proposed for solving VRPTW. To improve the performance of ACS¡ two neighborhood search in the name of insert and swap algorithms are used. This new algorithm can avoid premature convergence and exploit more strong solutions. Finally¡ the effectiveness of the HACS on solving a number of the Solomon’s 56 VRPTW is validated by comparing the computational results with those previously presented in the literature. The results show that not only the proposed HACS algorithm can find good solutions but also seven best known solutions of the benchmark problem are also found by the proposed method.