Scholarlink

<p>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. <CitationRef CitationID="CR8">2002</CitationRef>) 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

On multi-objective multi-coverage covering salesman problem

  • 期刊论文

  • 发表日期：

    2025年10月31日

查看全文
  • Amiya Biswas,
  • Erfan Babaee Tirkolaee,
  • Lakshmi Narayan De,
  • Vincent F. Yu,
  • Tandra Pal

摘要

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.