A Multi-objective Version of the Lin-Kernighan Heuristic for the Traveling Salesman Problem

Authors

  • Emerson Bezerra de Carvalho Universidade Federal do Rio Grande do Norte
  • Elizabeth Ferreira Gouvêa Goldbarg Departamento de Informática e Matemática Aplicada, Universidade Federal do Rio Grande do Norte http://orcid.org/0000-0002-2265-4692
  • Marco Cesar Goldbarg Universidade Federal do Rio Grande do Norte

DOI:

https://doi.org/10.22456/2175-2745.76452

Keywords:

multi-objective traveling salesman, multi-objective lin and kernighan, local search

Abstract

The Lin and Kernighan’s algorithm for the single objective Traveling Salesman Problem (TSP) is one of the most efficient heuristics for the symmetric case. Although many algorithms for the TSP were extended to the multi-objective version of the problem (MTSP), the Lin and Kernighan’s algorithm was still not fully explored. Works that applied the Lin and Kernighan’s algorithm for the MTSP were driven to weighted sum versions of the problem. We investigate the LK from a Pareto dominance perspective. The multi-objective LK was implemented within two local search schemes and applied to 2 to 4-objective instances. The results  showed that the proposed algorithmic variants obtained better results than a state-of-the-art algorithm.

Downloads

Download data is not yet available.

Author Biographies

Emerson Bezerra de Carvalho, Universidade Federal do Rio Grande do Norte

Emerson B. de Carvalho obteve seu título de mestre em sistemas e computação pelo Programa de Pós-graduação em Sistemas e Computação da Universidade Federal do Rio Grande do Norte. Seus interesses de pesquisa são problemas multiobjetivo e meta-heurísticas.

Elizabeth Ferreira Gouvêa Goldbarg, Departamento de Informática e Matemática Aplicada, Universidade Federal do Rio Grande do Norte

Elizabeth F. G. Goldbarg é professora do Departamento de Informática e Matemática Aplicada da Universidade Federal do Rio Grande do Norte. Seus principais interesses de pesquisa são problemas de otimização combinatória, meta-heurísticas e programação multiobjetivo

Marco Cesar Goldbarg, Universidade Federal do Rio Grande do Norte

Marco C. Goldbarg é professor titular do Departamento de Informática e Matemática Aplicada da Universidade Federal do Rio Grande do Norte. Seus interesses de pesquisa são problemas de roteamento de veículos, programação matemática e meta-heurísticas.

References

LIN, S.; KERNIGHAN, B. W. An effective heuristic algorithm for the traveling-salesman problem. Operations Research, v. 21, n. 2, p. 498–516, 1973.

GUTIN, G.; PUNNEN, A. P. The Traveling Salesman Problem and Its Variations. 1. ed. Berlin, Germany: Springer Science & Business Media, 2007. v. 12. (Combinatorial Optimization, v. 12).

HELSGAUN, K. An effective implementation of the lin–kernighan traveling salesman heuristic. European Journal of Operational Research, v. 126, n. 1, p. 106 – 130, 2000.

APPLEGATE, D.; COOK, W.; ROHE, A. Chained lin-kernighan for large traveling salesman problems. INFORMS Journal on Computing, v. 15, n. 1, p. 82–92, 2003.

MARINAKIS, Y.; MARINAKI, M.; DOUNIAS, G. Honey bees mating optimization algorithm for the euclidean traveling salesman problem. Information Sciences, v. 181, n. 20, p. 4684–4698, 2011.

JASZKIEWICZ, A.; ZIELNIEWICZ, P. Pareto memetic algorithm with path relinking for bi-objective traveling salesperson problem. European Journal of Operational Research, v. 193, n. 3, p. 885–890, 2009.

LUST,T.;TEGHEM,J.Two-phase pareto local search for the biobjective traveling salesman problem. Journal of Heuristics, v. 16, n. 3, p. 475–510, 2010.

LUST, T.; JASZKIEWICZ, A. Speed-up techniques for solving large-scale biobjective tsp. Computers & Operations Research, v. 37, n. 3, p. 521–533, 2010.

PAQUETE,L.;CHIARANDINI,M.;STUTZLE, T. Pareto local optimum sets in the biobjective traveling salesman problem: An experimental study. In: GANDIBLEUX, X. et al. (Ed.). Metaheuristics for Multiobjective Optimisation. 1. ed. Berlin, Germany: Springer, 2004, (Lecture Notes in Economics and Mathematical Systems, v. 535). cap. 7, p. 177–199.

ANGEL,E.;BAMPIS,E.;GOURVES,L.Adynasearch neighborhood for the bicriteria traveling salesman problem. In: GANDIBLEUX, X. et al. (Ed.). Metaheuristics for Multiobjective Optimisation. Berlin, Germany: Springer, 2004, (Lecture Notes in Economics and Mathematical Systems, v. 535). cap. 5, p. 153–176.

EHRGOTT, M. Vilfredo pareto and multi-objective optimization. Documenta Mathematica, extra volume ISMP, n. 1, p. 447–453, 2012.

LUST, T.; TEGHEM, J. The multiobjective traveling salesman problem: a survey and a new approach. In: COELLO, C. A. C.; DHAENENS, C.; JOURDAN, L. (Ed.). Advances in Multi-objective Nature Inspired Computing. 1. ed. Berlin, Germany: Springer, 2010, v. 272. cap. 6, p. 119–141.

KARP, R. M. Reducibility among combinatorial problems. In: MILLER, R. E.; THATCHER, J. W. (Ed.). Complexity of Computer Computations. 1. ed. New York, USA: Plenum Press, 1972, (The IBM Research Symposia Series, v. 1). cap. 8, p. 85–103.

EHRGOTT, M. Approximation algorithms for combinatorial multicriteria optimization problems. International Transactions in Operational Research, v. 7, n. 1, p. 5–31, 2000.

FISCHER, R.; RICHTER, K. Solving a multiobjective traveling salesman problem by dynamic programming. Mathematische Operationsforschung und Statistik. Series Optimization, v. 13, n. 2, p. 247–252, 1982.

FLORIOS, K.; MAVROTAS, G. Generation of the exact pareto set in multi-objective traveling salesman and set covering problems. Applied Mathematics and Computation, v. 237, n. 1, p. 1–19, 2014.

ANGEL,E.;BAMPIS,E.;GOURVES,L. Approximating the pareto curve with local search for the bicriteria tsp (1, 2) problem. Theoretical Computer Science, v. 310, n. 1, p. 135–146, 2004.

DUBOIS-LACOSTE,J.;LOPEZ-IBANEZ,M.; STUTZLE,T.Anytimeparetolocalsearch.EuropeanJournal of Operational Research, v. 243, n. 2, p. 369–385, 2015.

HANSEN, M. P. Use of substitute scalarizing functions to guide a local search based heuristic: The case of motsp. Journal of Heuristics, v. 6, n. 3, p. 419–431, 2000.

PAQUETE, L.; STu ̈TZLE, T. A two-phase local search for the biobjective traveling salesman problem. In: FONSECA, C. M. et al. (Ed.). Evolutionary Multi-Criterion Optimization. Berlin, Germany: Springer, 2003. (Lecture Notes in Computer Science, v. 2632).

ELAOUD, S.; TEGHEM, J.; LOUKIL, T. Multiple crossover genetic algorithm for the multiobjective traveling salesman problem. Electronic Notes in Discrete Mathematics, v. 36, n. 1, p. 939–946, 2010.

JASZKIEWICZ, A. Genetic local search for multi-objective combinatorial optimization. European Journal of Operational Research, v. 137, n. 1, p. 50–71, 2002.

PENG, W.; ZHANG, Q.; LI, H. Comparison between moea/d and nsga-ii on the multi-objective travelling salesman problem. In: Multi-objective Memetic Algorithms. 1. ed. Berlin, Germany: Springer, 2009, (Studies in Computational Intelligence, v. 171). cap. 14, p. 309–324.

SAMANLIOGLU, F.; FERRELL, W. G.; KURZ, M. E. A memetic random-key genetic algorithm for a symmetric multi-objective traveling salesman problem. Computers & Industrial Engineering, v. 55, n. 2, p. 439–449, 2008.

CHENG, J. et al. Multi-objective ant colony optimization based on decomposition for bi-objective traveling salesman problems. Soft Computing, v. 16, n. 4, p. 597–614, 2012.

ZHOU,A.;GAO,F.;ZHANG,G.A decomposition Transactions on Evolutionary Computation, v. 11, n. 6, p. 712–731, 2007.

PAQUETE,L.;STUTZLE,T.Designand analysis of stochastic local search for the multiobjective traveling salesman problem. Computers & Operations Research, v. 36, n. 9, p. 2619–2631, 2009.

BEAN, J. C. Genetic algorithms and random keys for sequencing and optimization. ORSA Journal on Computing, v. 6, n. 2, p. 154–160, 1994.

BOWMAN, V. J. On the relationship of the tchebycheff norm and the efficient frontier of multiple-criteria objectives. In: FANDEL, G.; TROCKEL, W. (Ed.). Multiple Criteria Decision Making. 1. ed. Berlin, Germany: Springer, 1976, (Lecture Notes in Economics and Mathematical Systems, v. 30). cap. 5, p. 76–86.

DEB, K. et al. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, v. 6, n. 2, p. 182–197, 2002.

ZHANG, Q.; LI, H. Moea/d: A multiobjective evolutionary algorithm based on decomposition. IEEE Algorithms for Multiobjective Combinatorial Optimization: Methods and Analysis. 2006.

JOHNSON, D. S.; MCGEOCH, L. A. Experimental analysis of heuristics for the stsp. In: GUTIN, G.; PUNNEN, A. P. (Ed.). The Traveling Salesman Problem and Its Variations. Berlin, Germany: Springer, 2007, (Combinatorial Optimization, v. 19). cap. 10, p. 369–443.

HAMACHER, H. W.; RUHE, G. On spanning tree problems with multiple objectives. Annals of Operations Research, v. 52, n. 4, p. 209–230, 1994.

LUST, T. New Metaheuristics for Solving MOCO Problems: Application to the Knapsack Problem, the Traveling Salesman Problem and IMRT Optimization. Tese (Doutorado) — Faculte ́ Polytechnique de Mons, Mons, Belgium, 2010.

PAQUETE,L.;STUTZLE,T.Stochastic Local Search based estimation of distribution algorithm for multiobjective traveling salesman problems. Computers & Mathematics with Applications, v. 66, n. 10, p. 1857–1868, 2013.

HEIDELBERG, R.-K.-U. TSPLIB. http://comopt.ifi.uni- heidelberg.de/software/TSPLIB95/.

ZITZLER, E.; THIELE, L. Multiobjective optimization using evolutionary algorithms - a comparative case study. In: EIBEN, A. et al. (Ed.). Parallel Problem Solving from Nature (PPSN V). Berlin, Germany: Springer, 1998. (Lecture Notes in Computer Science, v. 1498).

ZITZLER, E. et al. Performance assessment of multiobjective optimizers: An analysis and review. IEEE Transactions on Evolutionary Computation, v. 7, n. 2, p. 117–132, 2003.

BADER, J.; ZITZLER, E. Hype: An algorithm for fast hypervolume-based many-objective optimization. Evolutionary Computation, v. 19, n. 1, p. 45–76, 2011.

KNOWLES, J.; THIELE, L.; ZITZLER, E. A Tutorial on the Performance Assessment of Stochastic Multiobjective Optimizers. Zurich, Switzerland, 2006.

Downloads

Published

2018-02-18

How to Cite

de Carvalho, E. B., Goldbarg, E. F. G., & Goldbarg, M. C. (2018). A Multi-objective Version of the Lin-Kernighan Heuristic for the Traveling Salesman Problem. Revista De Informática Teórica E Aplicada, 25(1), 48–66. https://doi.org/10.22456/2175-2745.76452

Issue

Section

Regular Papers

Most read articles by the same author(s)