The Hamiltonian p-median problem (HpMP) generalizes the classical traveling salesperson (TSP) and the Hamiltonian cycle problems. The HpMP aims to find a collection of p non-intersecting cycles that span all the vertices of a given edge-weighted graph G=(V,E,w) while minimizing the sum of the costs of the cycles. This paper introduces a memetic algorithm (MA) with explicit diversity management for the upper-bounded HpMP (UB-HpMP), where upper-bounded means that each cycle in the solution cannot exceed a maximum number of vertices. This MA approaches the problem as a set-partitioning problem, where each cluster of the partition contains the vertices of each cycle. Moreover, it uses a novel crossover operator based on the Hungarian algorithm, exploits the Lin–Kernighan heuristic, a state-of-the-art algorithm for the TSP, and uses best-non-penalized (BNP) selection to explicitly manage the population’s diversity. The proposed MA is tested against state-of-the-art algorithms and classical techniques, including those with and without implicit diversity management, as well as an open-source heuristic solver. The computational experimentation results show that explicit diversity management has advantages over other techniques.
Cornejo-Acosta et al. (Sat,) studied this question.