An Effective Imperialist Competitive Algorithm for Solving the Open Vehicle Routing Problem

The Open Vehicle Routing Problem (OVRP) is an important generalized version of the Vehicle Routing Problem (VRP) that has received a lot of attention because of its numerous applications in industrial and service problems. Its objective is to minimize the total distance traveled by a fleet of vehicles that start from a depot and deliver goods to customers. It is to be noted that the vehicles do not have to return to the depot after delivery. This paper has proposed an effective Imperialist Competitive Algorithm (ICA) as a new meta-heuristic algorithm for the solution of this problem. The proposed algorithm has been tested on 22 OVRP cases from the literature involving 50 to 480 customers. Computational results have shown that to solve the OVRP, ICA competes satisfactorily with other meta-heuristic algorithms in results; nine best known solutions of the benchmark problem have also been found by the proposed method.