arXiv:2611.15219 · v1

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

首次提交 2026-11-11 17:14

版本更新 2026-11-11 17:14

雷达观测 2026-11-13 11:11

摘要

The Hamiltonian \textit{p}-median problem seeks to partition the vertices of a graph into exactly $p$ 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 $p$ is large, lead to excessive population dispersion and hinder convergence.