A Combined Metaheuristic Algorithm for the Vehicle Routing Problem and its Open Version

The Open Vehicle Routing Problem (OVRP) is one of the most important extensions of the Vehicle Routing Problem (VRP) that has many applications in the industry and services. In VRP, a set of customers with a specified demand of goods is given, where a fleet of identical capacitated vehicles is located. The ‘‘traveling costs’’ between the depot and all the customers, and between each pair of customers are also defined. In OVRP against VRP, the vehicles are not required to return to the depot after completing service. Since VRP and OVRP belong to the NPhard problems, in this work, an efficient hybrid elite ant system called EACO is proposed for solving them. In this algorithm, a modified tabu search, a new state transition rule, and a modified pheromone-updating rule are used for more improved solutions. As a result of these modifications, the proposed algorithm is not trapped at the local optimum and discovers different parts of the solution space. The computational results of 14 standard benchmark instances for VRP and OVRP show that EACO finds the best known solutions for most of the instances, and it is comparable in terms of solution quality to the best performing published metaheuristics in the literature.