A Hybrid Ant Colony System approach for solving Capacitated Vehicle Routing Problems with Time Windows

The Capacitated Vehicle Routing Problem with Time Windows represents a common problem. First, the problem is defined mathematically and an example of such a problem is shown. In short, the problem itself is a mixture of the Traveling Salesman Problem and the Bin Packing Problem. A possible solution to the problem is demonstrated, as well as the fitness criteria of the problem. The Ant Colony System algorithm is used to solve the problem. A modification of the original Ant Colony System Meta-heuristic is introduced. The heuristics used to improve the basic ACS algorithm are the Savings heuristic, Wait heuristic and the Route Size heuristic. Also, a few local search methods are used, such as 2*opt and Route Elimination local search. Finally, the result of applying the algorithm to a problem instance is discussed.