Can I read Exact Algorithms and Heuristics for Capacitated Covering Salesman Problems on EtoBox?

Exact Algorithms and Heuristics for Capacitated Covering Salesman Problems by Maziero, Lucas Porto; Usberti, Fábio Luiz; Cavellucci, Celso is a scholarly article available to read on EtoBox.

What is Exact Algorithms and Heuristics for Capacitated Covering Salesman Problems about?

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

Author

Maziero, Lucas Porto; Usberti, Fábio Luiz; Cavellucci, Celso

Published

2024

Language

EN