On multi-objective multi-coverage covering salesman problem

In most of the covering salesman problems (CSPs) addressed in the literature, the customer nodes are considered to attain 1-coverage. However, such consideration makes the system vulnerable. One way to make the system robust is to consider more than 1-coverage for all nodes/customers. However, the same coverage value of more than one for all nodes/customers is not realistic as well as cost effective. In this study, we divide the nodes in different groups based on their requirements of coverage. The coverage is more for a node of higher importance (or priority) compared to others. The nodes of the same group have the same coverage requirement. Some real-world scenarios where such a system is mostly suitable includes border surveillance, supply chain in disaster management, and missile defense systems. The aim of this study is to formulate and solve a multi-objective CSP for multiple values of coverage considering the two conflicting objectives, maximization of overall coverage and minimization of tour length. We name the problem as multi-objective multi-coverage CSP (MOMC-CSP). To solve the proposed MOMC-CSP, we modify the general framework of the non-dominated sorting genetic algorithm (NSGA-II) (Deb et al. 2002) to adapt it suitable for the problem. For implementation purpose, we use a one-dimensional array of variable length to represent a chromosome that needs less memory as well as less computation time compared to a fixed length chromosome. Accordingly, we design the genetic operators compatible to the problem and the chromosome representation. To show the effectiveness of the proposed model, exhaustive experiments are performed on a number of numerical examples of different sizes from the TSP library varying the number of nodes from100 to 666. Finally, some future research directions are provided.