Novel Ant Colony Optimization Approaches To The Vehicle Routing Problem With Time Windows

The Vehicle Routing Problem with Time Windows (VRPTW) can be regarded as a mathematical model existing in many logistic systems. In this paper, we apply Ant Colony Optimization (ACO) in studying this problem. We set the number of vehicles as our primary objective function and the total travelling cost as our second one.In this paper, we improve the basic ant colony algorithm to be more fixed with our objectives. Our improvements mainly come from following four aspects. First, in order to reduce the search space, we propose the concept of domain and this concept is used throughout the whole paper. The method rules out certain cities that violate time con-strains of the problem. When the concept is carried out on the Solomon benchmark, the search space is reduced by28%on average. Second, we first apply Population Based Ant Colony Optimization (PACO) into VRPTW and find it beats all the ACO algorithms listed in this paper. Third, we also propose a new probability initialization method for PACO (PI-PACO). The method builds model for problem conditions and actual logistics and gives the initial pheromone. By experiments, we find it can not only improve two objective functions of VRPTW but also accelerate the convergence speed. At last, in or-der to further improve the solution quality, we hybridize local search and improve our initialization method to be better combined (hybrid PI-PACO). We apply the random selection method on search operators. One of the search operator is selected to gen-erate the according neighborhood of the solutions. When compared with ACO-based algorithms, our method performs better. It also shows advantages of solving clustered problems when compared with complex algorithms. Results show that our algorithm is quite competitive.