Efficient heuristics for Median Cycle Problems

J Renaud, F F Boctor and G Laporte ()
Additional contact information
J Renaud: Centre de recherche sur les technologies de l'organisation réseau, Université Laval
F F Boctor: Centre de recherche sur les technologies de l'organisation réseau, Université Laval
G Laporte: Canada Research Chair in Distribution Management, HEC Montréal

Journal of the Operational Research Society, 2004, vol. 55, issue 2, 179-186

Abstract: Abstract This article proposes a number of efficient heuristics for two versions of the Median Cycle Problem. In both versions, the aim is to construct a simple cycle containing a subset of the vertices of a mixed graph. In the first version, the objective is to minimize the cost of the cycle and the cost of assigning vertices not on the cycle to the nearest vertex on the cycle. In the second version, the objective is to minimize the cost of the cycle subject to an upper bound on the total assignment cost. Two heuristics are developed. The first, called the multistart greedy add heuristic, is composed of two main phases. In the first phase, a cycle composed of a limited number of randomly chosen vertices is constructed and augmented by iteratively adding the vertex yielding the largest cost reduction until either no further reduction is possible (for the first version) or the assignment cost is below the upper bound (for the second version). The second phase applies a number of improvement routines. The second heuristic is a random keys evolutionary algorithm. Computational results on a number of benchmark test instances show that the proposed heuristics are highly efficient for both versions of the problem, and superior to the only other available heuristic for these two versions of the problem.

Keywords: Median Cycle Problem; greedy add heuristic; evolutionary algorithm (search for similar items in EconPapers)
Date: 2004
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://link.springer.com/10.1057/palgrave.jors.2601672 Abstract (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:pal:jorsoc:v:55:y:2004:i:2:d:10.1057_palgrave.jors.2601672

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

DOI: 10.1057/palgrave.jors.2601672

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().