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

Emerson Bezerra de Carvalho, Elizabeth Ferreira Gouvêa Goldbarg, Marco Cesar Goldbarg

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.

Keywords


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

Full Text:

PDF

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.




DOI: http://dx.doi.org/10.22456/2175-2745.76452

Copyright (c) 2018 Emerson Bezerra de Carvalho, Elizabeth Ferreira Gouvêa Goldbarg, Marco Cesar Goldbarg

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.