Chemical reaction optimization with unified tabu search for the vehicle routing problem

This study proposes a new approach combining the chemical reaction optimization framework with the unified tabu search (UTS) heuristic to solve the capacitated vehicle routing problem (CVRP). The CVRP is one of the most well-studied problems not only because of its real-life applications but also due to the fact that the CVRP could be used to evaluate the efficiency of new algorithms and optimization methods. Chemical reaction optimization (CRO) is a new optimization framework mimicking the nature of chemical reactions. The CRO method has proved to be very effective for solving NP-hard optimization problems such as the quadratic assignment problem, neural network training, the knapsack problem, and the traveling salesman problem. We also present the design of elementary chemical reaction operations, the adaptation of the UTS algorithm to educate solutions in these operations. Finally, a thorough testing against well-known benchmark problems has been conducted. Experimental results show that the proposed algorithm is efficient and highly competitive in comparison with several prominent algorithms for this problem. The presented methodology may be a fine approach for developing similar algorithms to address other routing variants.