Effective Set Covering Approach for Vehicle Routing Based on Artificial Immune

摘要

In this paper, a heuristic algorithm to solve the Vehicle Routing Problem (VRP) is proposed based on the Artificial Immune System (AIS). By introducing the route covering methodology, a new encoding and heuristic structure are developed. Routes are constructed primarily by the cluster-first-route-second method, with the network renewal mechanism to generate initial antibodies and the bi-learning with balanced-opportunity approach to expand antibody population. The concentric-circle builder is to identify different customer clusters to further form routes. Upon the elite strategy (AB) and (R), worse antibodies are deleted and routes keep diversified in the pool. By further solving the set covering model, the VRP solution is improved along with increasing route choices. Further, the route combination phase is developed to add promising routes, and it brings the final optimal VRP solution by selecting optimal routes from the final route pool. Finally, experiment tests are carried out to illustrate the effectiveness of the proposed heuristic.