Authors: Mostafa Dastmardi; Mohammad Mohammadi; Bahman Naderi
Addresses: Department of Quality Management, Iran Polymer and Petrochemical Institute, Tehran, Iran ' Department of Industrial Engineering, Faculty of Engineering, Kharazmi University, Tehran, Iran ' Department of Industrial Engineering, Faculty of Engineering, Kharazmi University, Tehran, Iran
Abstract: We study the maximal covering salesman problem with the average travelling cost constraints (MCSPATCC) where the objective is to find a subset of customers with their tour so that the number of covered demand points is maximised. This paper presents a mathematical model to select a profitable subset of demand points to be covered. We also propose an effective heuristic algorithm with three elimination methods to remove unprofitable demand points. The proposed algorithm is based on the genetic algorithm (GA) hybridised with different local search strategies to solve this problem. Parameters of the algorithm are analysed for calibration by the Taguchi method. Extensive computational experiments, on a set of standard problems, have indicated the effectiveness of our algorithm.
Keywords: maximum covering; genetic algorithm; covering salesman problem.
International Journal of Mathematics in Operational Research, 2020 Vol.17 No.2, pp.153 - 169
Accepted: 09 Jun 2019
Published online: 21 Sep 2020 *