Multi-objective covering salesman problem: a decomposition approach using grey wolf optimization

In this study, the basic grey wolf optimization (GWO) algorithm ismodified along with K-bit exchange, K-opt operation, and integrated with the structure of multi-objective evolutionary algorithm with decomposition approach (MOEA/D) to solve multi-objective covering salesman problem(MOCSP). The algorithm is named a multi-objective evolutionary algorithm with decomposition using GreyWolf optimization (MOEA/D-GWO). The K-opt operation with K = 3 and K = 4 is used to generate the initial solution set. The GWO algorithm is modified with a set of newly introduced perturbation rules. A two-stage updating mechanism has been introduced to improve the quality of a potential solution. The first sage of the process is done by the modified GWO algorithm, and in the second stage, a perturbation technique using K-bits exchange operation is applied. The MOEA/D-GWO algorithm is a two-phase algorithm where in the first phase, the clustering/grouping of cities is done, and in the next phase one city from each cluster/group is selected to search pareto-optimal Hamiltonian cycles in such a way that each cycle maintains the pre-define covering distance. Here, for the first time a heuristic approach is proposed forMOCSP. Different sizes of standard benchmark MOCSP test instances are used to test the performance of the MOEA/D-GWO algorithm. The instances are generated from TSPLIB. Different traditional multi-objective optimization algorithms, like NSGA-II, SPEA2, MOEA/D, MR-ABCWCD, SMPSO, SR4-MOEA/D for MOOP, have been modified according toMOCSP and implemented to compare the efficiency of the proposed approach. Nine standard well-known performance metrics/indicators have been used to analyse the performance of the MOEA/D-GWO algorithm for MOCSP. Different sizes bi-objective instances are generated from TSPLIB, for the illustration and testing the performance of the algorithm. Detailed problem generation approach is also discussed. From all the numerical studies, it is concluded that the proposed algorithm is efficient enough to deal with the MOCSPs.

Automated summary

In this study, the basic Grey Wolf Optimization (GWO) algorithm is modified and integrated with the Multi-Objective Evolutionary Algorithm with Decomposition (MOEA/D) to solve the Multi-Objective Covering Salesman Problem (MOCSP). A two-phase algorithm is proposed, which involves clustering the cities and then selecting cities from each cluster to search for Pareto-optimal Hamiltonian cycles. The algorithm is tested on different benchmark instances and compared with other traditional multi-objective optimization algorithms. The results show that the proposed algorithm is efficient in dealing with MOCSP.