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

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

    Jul 30, 2026Zeyad Kassem, Behnam Jabbari-Marand, Adolfo R. EscobedoCombinatorial OptimizationInteger Linear Programming

  2. Parent Selection Mechanisms in Elitist Crossover-Based Algorithms

    Apr 5, 2026Andre Opris, Denis AntipovEvolutionary OptimizationGenetic Algorithms

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

    Jun 16, 2026Narges Tavassoli Kejani, Andrew M. Sutton, Frank NeumannMulti-Objective Evolutionary OptimizationRuntime Analysis of Evolutionary Algorithms