Exact and heuristic algorithms for the Hamiltonian p-median problem

Gunes Erdogan, Gilbert Laporte, Antonio M. Rodriguez Chia

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)
232 Downloads (Pure)

Abstract

This paper presents an exact algorithm, a constructive heuristic algorithm, and a metaheuristic for the Hamiltonian p-Median Problem (HpMP). The exact algorithm is a branch-and-cut algorithm based on an enhanced p-median based formulation, which is proved to dominate an existing p-median based formulation. The constructive heuristic is a giant tour heuristic, based on a dynamic programming formulation to optimally split a given sequence of vertices into cycles. The metaheuristic is an iterated local search algorithm using 2-exchange and 1-opt operators. Computational results show that the branch-and-cut algorithm outperforms the existing exact solution methods.
Original languageEnglish
Pages (from-to)280-289
Number of pages10
JournalEuropean Journal of Operational Research
Volume253
Issue number2
Early online date12 Feb 2016
DOIs
Publication statusPublished - 1 Sep 2016

Keywords

  • Hamiltonian
  • p-median
  • Branch-and-cut
  • Metaheuristic

Fingerprint Dive into the research topics of 'Exact and heuristic algorithms for the Hamiltonian p-median problem'. Together they form a unique fingerprint.

Cite this