TWO META-HEURISTICS FOR SOLVING THE MULTI-VEHICLE MULTI-COVERING TOUR PROBLEM WITH A CONSTRAINT ON THE NUMBER OF VERTICES

Abstract

In this work we deal with a generalized variant of the multi-vehicle covering tour problem (m-CTP). The m-CTP consists of minimizing the total routing cost and
satisfying the entire demand of all customers without the restriction of visiting all of them such that each vertex not included in any route is covered. In the m CTP, we need only to visit a subset of customers to full the total demands where a restriction on the length of each route and the number of vertices that it contains are considered. This paper tackles, a generalized variant of the m-CTP called the multi-vehicle multi-covering Tour Problem (mm-CTP) where a vertex must be covered several times instead of once. We study a particular case of the mm-CTP where only the restriction on the number of vertices in each route is considered and the constraint on the length is relaxed (mm-CTP-p). A hybrid metaheuristic combining Genetic Algorithm (GA)and Variable Neighborhood Descent method (VND) as well as a General Variable Neighborhood Search algorithm (GVNS) were developed to solve the problem. Computational experiments showed that our proposed approaches are competitive with the Evolutionary Local Search (ELS) and Genetic Algorithm (GA) methods proposed in the literature.