کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
479243 | 1445977 | 2016 | 10 صفحه PDF | دانلود رایگان |
• 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.
Journal: European Journal of Operational Research - Volume 253, Issue 2, 1 September 2016, Pages 280–289