cs.NENov 11, 2026

A Multi-Parent Edge Assembly Crossover Driven Hybrid Genetic Algorithm for the Hamiltonian p-Median Problem

Authors: Junkai Huang, Pengfei He, Jin-Kao Hao, Xin Yao

Organizations: School of Automation and Key Laboratory of Measurement and Control of Complex Systems of Engineering, Ministry of Education, Southeast University, Nanjing 210096, China · School of Data Science, Lingnan University, Hong Kong SAR, China · LERIA, Université d’Angers, 2 Boulevard Lavoisier, 49045 Angers, France

Abstract

The Hamiltonian p-median problem seeks to partition the vertices of a graph into exactly pp disjoint cycles while minimizing their total cost. This paper presents a hybrid genetic algorithm incorporating a multi-parent edge assembly crossover operator. The crossover combines a base solution with multiple donor solutions in a single recombination operation, thereby expanding the space of available edge exchanges. It uses virtual copies of the base solution to establish edge balance, together with an auxiliary directed graph and a budgeted search to construct valid AB-cycles. Extensive experiments on 215 benchmark instances across four sets show that the proposed algorithm improves the best-known solution values for 34 instances and matches those for another 168. Additional experiments indicate that a moderate number of parents provides beneficial diversity, whereas excessive parent counts, particularly when pp is large, lead to excessive population dispersion and hinder convergence.

Figures & tables

Explore similar work

Jul 30, 2026

The edge-based contiguous p-median problem: exact formulations and strengthening inequalities

This paper introduces the edge-based contiguous p-median (ECpM) problem, which partitions the roads in a network into a given number of compact and contiguous territories. We develop two binary programming formulations that minimize the total network distance from each road to its assigned center node. The first uses an exponential number of cut-set contiguity (CSC) constraints and is solved with a branch-and-cut (B&C) algorithm that checks incumbent solutions for contiguity and adds violated CSC constraints as needed. The second is a compact formulation that imposes a stronger form of contiguity through shortest-path contiguity (SPC) constraints. These constraints are added up front, and the formulation is solved directly with an off-the-shelf solver. Despite this stronger requirement, we show that SPC-based ECpM has the same optimal objective value as ECpM with general contiguity and even the relaxed edge-based p-median (EpM). As a result, the SPC constraints preserve at least one optimal EpM solution and can therefore strengthen the EpM formulation. We also establish three structural properties of ECpM solutions and use them to derive three families of inequalities that further strengthen these formulations. Computational experiments on 84 instances from 14 real-world road networks show that adding the SPC constraints to EpM enables all instances to be solved to optimality and reduces solution times. In contrast, EpM without these constraints and CSC-based ECpM reach the time limit on six and eight instances, respectively. The proposed inequalities reduce both counts to one and further reduce solution times.
Apr 5, 2026

Parent Selection Mechanisms in Elitist Crossover-Based Algorithms

Parent selection methods are widely used in evolutionary computation to accelerate the optimization process, yet their theoretical benefits are still poorly understood. In this paper, we address this gap by proposing a parent selection strategy for the (μ+1)(μ+1) genetic algorithm (GA) that prioritizes the selection of maximally distant parents for crossover. We show that, with an appropriately chosen population size, the resulting algorithm solves the Jumpk_k problem in O(k4knlog⁡(n))O(k4^kn\log(n)) expected time. This bound is significantly smaller than the best known bound of O(nμlog⁡(μ)+nlog⁡(n)+nk−1)O(nμ\log(μ)+n\log(n)+n^{k-1}) for any (μ+1)(μ+1)~GA using no explicit diversity-preserving mechanism and a constant crossover probability. To establish this result, we introduce a novel diversity metric that captures both the maximum distance between pairs of individuals in the population and the number of pairs achieving this distance. The main novelty of our analysis is that it relies on crossover as a mechanism for creating and maintaining diversity throughout the run, rather than using crossover only in the final step to combine already diversified individuals. The insights provided by our analysis contribute to a deeper theoretical understanding of the role of crossover in the population dynamics of genetic algorithms.
Jun 16, 2026

Evolutionary Algorithms and Multi-Objective Minimum Spanning Trees with Limited Distinct Weight Values

Evolutionary algorithms have been used for a wide range of multi-objective combinatorial optimization problems. Despite practical success, theoretical results on the runtime of evolutionary algorithms for multi-objective combinatorial problems are rather limited. One classical problem that has been investigated is the multi-objective minimum spanning tree problem for which runtime bounds have been obtained to compute all extremal corner points of the Pareto front. With this paper, we provide some more detailed insights into the structure of the Pareto front when the edge weights take on a small number of distinct values. Based on these insights, we derive new runtime results for evolutionary multi-objective algorithms and complement our theoretical results with experimental investigations.