Applying Two-Stage Ant Colony Optimization to Solve the Large Scale Vehicle Routing Problem

概要

論文の詳細を見る
The vehicle routing problem (VRP) is an important problem in the field of logistics management. As an NP-hard problem, the VRP real world sized instances cannot be solved to optimality within reasonable times. This research aims to develop a two-stage ant colony optimization (TACO) algorithm, which possesses a two-stage solution construction rule, to solve the large scale vehicle routing problem (LSVRP). In the first stage of the solution construction rule, the VRP is decomposed into several sub-problems (traveling salesman problem). Then each sub-problem is solved by an improved ant colony system (ACS) in the second stage of the construction rule. The performance of TACO is tested by 14 VRP and 20 LSVRP benchmark instances and compared with other meta-heuristic approaches in the literature. The computational results show that our TACO can obtain good solutions for large scale VRP instances and its performance is competitive with other well-known meta-heuristic algorithms.