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.
Similar content being viewed by others
References
Moreno Pérez J, Moreno-Vega M and Rodríguez Martín I (2002). Variable neighbourhood tabu search and its application to the median cycle problem. European Journal of Operational Research, 2004, to appear.
Labbé M, Laporte G, Rodríguez Martín I and Salazar González JJ (2001). The Ring star problem: polyhedral analysis and exact algorithm. Unpublished manuscript.
Labbé M, Laporte G, Rodríguez Martín I and Salazar González JJ (2001). The median cycle problem. Unpublished manuscript.
Gourdin E, Labbé M and Yaman H (2002). Telecommunication and location. In: Drezner Z and Hamacher H (eds). Facility Location: Applications and Theory. Springer, Berlin, pp 275–305.
Klincewicz J (1998). Hub location in backbone/tributary network design: a review. Location Sci 6: 307–335.
Labbé M and Laporte G (1986). Maximizing user convenience and postal service efficiency in post box location. Belgian J Opns Res Stat Comput Sci 26: 21–35.
Bauer P (1997). The circuit polytope: facets. Math Opns Res 22: 110–145.
Laporte G (1988). Location-routing problems. In: Golden BL and Assad AA (eds). Vehicle Routing: Methods and Studies. North-Holland, Amsterdam, pp 163–197.
Volgenant T and Jonker R (1987). On some generalizations of the traveling salesman problem. J Opl Res Soc 38: 1073–1079.
Gendreau M, Laporte G and Semet F (1998). The selective traveling salesman problem. Networks 32: 263–273.
Fischetti M, Salazar González JJ and Toth P (1998). Solving the orienteering problem through branch-and-cut. INFORMS J Comput 10: 133–148.
Balas E (1989). The prize collecting traveling salesman problem. Networks 19: 621–636.
Gendreau M, Laporte G and Semet F (1997). The covering tour problem. Opns Res 45: 568–576.
Labbé M, Laporte G and Rodríguez Martín I (1998). Path, tree and cycle location. In: Crainic T and Laporte G (eds). Fleet Management and Logistics. Kluwer, Boston, pp 187–204.
Feremans C, Labbé M and Laporte G (2003). Generalized network design problems. Eur J Opl Res, to appear.
Renaud J, Boctor F and Laporte G (1996). Fast composite heuristic for the symmetric traveling salesman problem. ORSA J Comput 3: 134–143.
Lin S and Kernighan BW (1973). An effective heuristic algorithm for the traveling salesman problem. Opns Res 20: 498–516.
Helsgaum K (2000). Effective implementation of the Lin–Kerninghan traveling salesman heuristic. Eur J Opl Res 126: 106–130.
Bean J (1994). Genetic algorithms and random keys for sequencing and optimization. ORSA J Comput 6: 154–160.
Reinelt G (1991). TSPLIB—a traveling salesman problem library. ORSA J Comput 3: 376–384.
Acknowledgements
This work was partially supported by the Canadian Natural Sciences and Engineering Research Council (NSERC) under Grants OPG0039682, OPG0036509 and OPG0172633. This support is gratefully acknowledged. Thanks are also due to Keld Helsgaum who provided us with his Lin–Kernighan code and to Juan José Salazar González and Inmaculada Rodríguez Martín who provided their solutions of the TSPLIB instances. Finally, we thank two referees for their valuable comments.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Renaud, J., Boctor, F. & Laporte, G. Efficient heuristics for Median Cycle Problems. J Oper Res Soc 55, 179–186 (2004). https://doi.org/10.1057/palgrave.jors.2601672
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/palgrave.jors.2601672