  This paper introduces the Capacitated Covering Salesman Problem (CCSP),
approaching the notion of service by coverage in capacitated vehicle routing
problems. In CCSP, locations where vehicles can transit are provided, some of
which have customers with demands. The objective is to service customers
through a fleet of vehicles based in a depot, minimizing the total distance
traversed by the vehicles. CCSP is unique in the sense that customers, to be
serviced, do not need to be visited by a vehicle. Instead, they can be serviced
if they are within a coverage area of the vehicle. This assumption is motivated
by applications in which some customers are unreachable (e.g., forbidden access
to vehicles) or visiting every customer is impractical. In this work,
optimization methodologies are proposed for the CCSP based on ILP (Integer
Linear Programming) and BRKGA (Biased Random-Key Genetic Algorithm)
metaheuristic. Computational experiments conducted on a benchmark of instances
for the CCSP evaluate the performance of the methodologies with respect to
primal bounds. Furthermore, our ILP formulation is extended in order to create
a novel MILP (Mixed Integer Linear Programming) for the Multi-Depot Covering
Tour Vehicle Routing Problem (MDCTVRP). Computational experiments show that the
extended MILP formulation outperformed the previous state-of-the-art exact
approach with respect to optimality gaps. In particular, optimal solutions were
obtained for several previously unsolved instances.
