On multi-objective covering salesman problem

摘要

Most of the Covering Salesman Problems (CSPs) addressed in the literature are considered full coverage. However, in real-life emergency situations like earthquake, flood, endemic and rural health care supply chain, full coverage of the cities may not always be possible due to various reasons like insufficient supply, limited time frame, insufficient manpower and damage of routes. In this study, we formulate a multi-objective CSP (MOCSP) restricting the number of nodes visited in a tour within a given range, so that a given percentage of nodes is at least covered. The objectives are maximization of coverage and minimization of tour length. Due to conflicting nature of the objectives, the problem is posed as a multi-objective optimization problem (MOOP). To solve the problem, the metaheuristic Non-dominated Sorting Genetic Algorithm-II (NSGA-II) is used with some modifications. The chromosome is designed to represent a tour with number of visited nodes within a given range. For the purpose of implementation, a one-dimensional array of variable length is used. New crossover and mutation operators are designed which are suitable for the problem and the corresponding chromosome representation. For simulation purpose, 19 benchmark test problems of Traveling Salesman Problem (TSP) from TSPLIB (Reinelt in ORSA J Comp 3:376–384) are used, where the number of nodes (i.e., cities) varies between 52 and 818. For each test problem, 12 instances are generated taking different values of problem parameters. Then, the set of optimal solutions are obtained for each instance, and the results are analyzed. A comparison of results for six test problems shows that our algorithm produces the best-known solutions for small and medium sized problems. However, for large sized problems, our algorithm produces better quality solutions in some cases only.