Exact and heuristic algorithms for the Hamiltonian p-median problem

•We provide three algorithms for the Hamiltonian p-median problem.•The first algorithm is an exact branch-and-cut algorithm.•The others are a constructive heuristic and an iterated local search metaheuristic.•The exact algorithm can solve 100-vertex instances.•The ILS metaheuristic solves the proble...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2016-09, Vol.253 (2), p.280-289
Main Authors: Erdoğan, Güneş, Laporte, Gilbert, Rodríguez Chía, Antonio M.
Format: Article
Language:English
Subjects:
Algorithms
Branch-and-cut
Construction
Dynamic programming
Exact solutions
Formulations
Hamiltonian
Heuristic
Heuristic methods
Mathematical analysis
Mathematical problems
Metaheuristic
Optimization
p-median
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:•We provide three algorithms for the Hamiltonian p-median problem.•The first algorithm is an exact branch-and-cut algorithm.•The others are a constructive heuristic and an iterated local search metaheuristic.•The exact algorithm can solve 100-vertex instances.•The ILS metaheuristic solves the problem to near-optimality. 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.
ISSN:0377-2217
1872-6860
DOI:10.1016/j.ejor.2016.02.012