Title: Maximal covering salesman problems with average travelling cost constrains

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.

DOI: 10.1504/IJMOR.2020.109693

International Journal of Mathematics in Operational Research, 2020 Vol.17 No.2, pp.153 - 169

Accepted: 09 Jun 2019
Published online: 21 Sep 2020 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article