Title: An improved hybrid genetic algorithm to solve the multi-vehicle covering tour problem with restriction on the number of vertices

Authors: Manel Kammoun

Addresses: Department of Quantitative Methods, Faculty of Economics and Management, MODILS, Sfax University, Sfax, Tunisia

Abstract: In this paper, we address the multi-vehicle covering tour problem where only the restriction on the number of vertices in each route (m-CTP-p). The objective of the m-CTP is to minimise the total routing cost and fulfill the demand of all customers such that each customer which is not included in any route must be covered. Each covered vertex must be within a given distance of at least a visited vertex and the number of vertices on a route does not exceed a pre-defined number p. We propose two approaches to solve this variant. First, we develop a genetic algorithm (GA) using an iterative improvement mechanism. Then, an effective hybrid genetic algorithm (HGA) is developed in addition to a local search heuristic based on variable neighborhood descent method to improve the solution. Extensive computational results based on benchmark instances on the m-CTP-p problem show the performance of our methods.

Keywords: covering; genetic algorithm; variable neighbourhood descent; VND; hybrid approach.

DOI: 10.1504/IJSSS.2023.132694

International Journal of Society Systems Science, 2023 Vol.14 No.3, pp.247 - 267

Received: 30 Jan 2021
Received in revised form: 29 Dec 2021
Accepted: 15 Apr 2022
Published online: 08 Aug 2023 *