A Hybrid Algorithm Based on Ant Colony Optimization and Differential Evolution for Vehicle Routing Problem

The vehicle problem (VRP) is a typical optimization problem in logistics and transportation. The objective function is to find the shortest route distances visited by all vehicles originating from a central deport to travel customers, and the sum of deliveries of each vehicle should meet the capacity constraint. This problem belongs to NP hard problems, so it is not easy to resolve it with common methods. Ant colony optimization (ACO) has shown prominent performance for many practical applications. However, it is inclined to premature convergence. The paper offers a hybrid ACO&DE algorithm, which hybridizes ant colony optimization (ACO) with differential evolution (DE) for the VRP. The main feature of the ACO&DE can make full use of advantages of the ACO and DE algorithm to make up for its own weakness, i.e., the ACO has fast construction mechanism, and the DE can extend the search scope of the ACO. Moreover, to make the DE suitable for solving the VRP, both strategies of mutation operator and crossover operator have been redesigned to implement the discrete DE directly. In addition, to increase the solution diversity by expanding the search space, we present a new selection strategy with probabilistic mechanism to determine new target vectors in the next iteration. Meanwhile, 2-opt heuristic and 2-exchange neighborhood is embedded in the ACO&DE to improve the local search performance. The results have shown that the proposed ACO&DE algorithm is competitive with existing optimal methods in solving the VRP, and thus can be further extended in variants of the VRP and other logistics transportation fields.