nach oben

Erschienen in:

2014 | OriginalPaper | Buchkapitel

10. An Evolutionary Algorithm with Path Relinking for a Bi-objective Multiple Traveling Salesman Problem with Profits

verfasst von : N. Labadie, J. Melechovsky, C. Prins

Erschienen in: Applications of Multi-Criteria and Game Theory Approaches

Verlag: Springer London

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This chapter deals with a bi-objective multiple traveling salesman problem with profits (BOMTSPP), generalizing the classical TSP with profits (TSPP). The TSPP is in fact a generic name for TSP problems taking into account the length of the tour and profits collected at customers. However, all these problems are not really bi-objective: the two criteria are aggregated into a single objective or one of them is replaced by a constraint. Our BOMTSPP aims at building m cycles covering a subset of potential customers so that the total collected profit is maximized and the overall traveling distance is minimized. This new problem generalizes the TSPP in two directions: a true bi-objective treatment and the construction of multiple tours. The proposed solution method is an effective evolutionary algorithm, reinforced by a post-optimization procedure based on path-relinking (PR).

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Route Selection and Consolidation in International Intermodal Freight Transportation

Nächstes Kapitel A Hybrid Simulation-based Duopoly Game Framework for Analysis of Supply Chain and Marketing Activities

Archetti C, Hertz A, Speranza MG (2007) Metaheuristics for the team orienteering problem. J Heur 13(1):49–76CrossRef

Basseur M, Seynhaeve F, Talbi EG (2005) Path relinking in pareto multi-objective genetic algorithms. In: Coello Coello CA, Hernndez Aguirre A, Zitzler E (eds) Evolutionary multi-criterion optimization. Thrid international conference, EMO 2005. Lecture notes in computer science, vol 3410. Springer Mexico, Guanajuato, pp 120–134.

Beausoleil R, Baldoquin G, Montejo R (2008) Multi-start and path relinking methods to deal with multi-objective knapsack problems. Ann Oper Res 157:105–133MathSciNetCrossRefMATH

Bérubé JF, Gendreau M, Potvin JY (2009a) An exact \( \varepsilon \)-constraint method for bi-objective combinatorial optimization problems: application to the traveling salesman problem with profits. Eur J Oper Res 194(1):39–50

Bérubé JF, Gendreau M, Potvin JY (2009b) A branch-and-cut algorithm for the undirected prize collecting traveling salesman problem. Networks 54:56–67MathSciNetCrossRefMATH

Bouly H, Dang DC, Moukrim A (2010) A memetic algorithm for the team orienteering problem. 4OR: Q J Oper Res 8(1):49–70CrossRefMATH

Boussier S, Feillet D, Gendreau M (2007) An exact algorithm for team orienteering problems. 4OR: Q J Oper Res 5(3):211–230MathSciNetCrossRefMATH

Chao IM, Golden BL, Wasil EA (1996) The team orienteering problem. Eur J Oper Res 88(3):464–474CrossRefMATH

Dantzig GB (1957) Discrete-variable extremum problems. Oper Res 5(2):266–288MathSciNetCrossRef

Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Trans Evo Comput 6(2):182–197CrossRef

Feillet D, Dejax P, Gendreau M (2005) Traveling salesman problems with profits. Transp Sci 39(2):188–205CrossRef

Glover F, Laguna M, Marti R (2000) Fundamentals of scatter search and path relinking. Cont Cyber 39:653–684MathSciNet

Jaszkiewicz A, Zielniewicz P (2009) Pareto memetic algorithm with path relinking for bi-objective traveling salesperson problem. Eur J Oper Res 193(3):885–890MathSciNetCrossRefMATH

Jozefowiez N, Glover F, Laguna M (2008) Multi-objective meta-heuristics for the traveling salesman problem with profits. J Math Mod Alg 7(2):177–195MathSciNetCrossRefMATH

Ke L, Archetti C, Feng Z (2008) Ants can solve the team orienteering problem. Comput Ind Eng 54(3):648–665CrossRef

Keller CP, Goodchild M (1988) The multi-objective vending problem: a generalization of the travelling salesman problem. Environ Plan B: Plan Des 15:447–460CrossRef

Konak A, Coit DW, Smith AE (2006) Multi-objective optimization using genetic algorithms: a tutorial. Reliab Eng Syst Saf 91(9):992–1007CrossRef

Labadi N, Prins C, Reghioui M (2008) Grasp with path relinking for the capacitated arc routing problem with time windows. In Fink A and Rothlauf F (eds) Advances in computational intelligence in transport, logistics, and supply chain management. Studies in computational intelligence, vol 144. Springer, Berlin, pp 111–135

Labadie N, Melechovsky J, Wolfler Calvo R (2010) An effective hybrid evolutionary local search for orienteering and team orienteering problem with time windows. In: Schaefer R et al (eds) Lecture Notes in Computer Science, vol 6239. Springer Berlin, Heidelberg, pp 219–228

Labadie N, Melechovsky J, Wolfler Calvo R (2011) Hybridized evolutionary local search algorithm for the team orienteering problem with time windows. J Heur 17(6):729–753CrossRefMATH

Labadie N, Mansini R, Melechovský J, Wolfler-Calvo R (2012) The team orienteering problem with time windows: an LP-based granular variable neighborhood search. Eur J Oper Res 220(1):15–27CrossRefMATH

Martí R, Laguna M, Campos V (2005) Scatter search vs. genetic algorithms. In: Ramesh Sharda, Stefan Vo, Csar Rego, Bahram Alidaee, Ramesh Sharda, and Stefan Voss (eds) Metaheuristic optimization via memory and evolution. Operations Research/Computer Science Interfaces Series, vol 30. Springer, New York, pp 263–282

Martí R, Campos V, Resende MGC, Duarte A (2011) Multi-objective grasp with path-relinking. Technical report, AT and T Labs Research

Montemanni R, Gambardella LM (2009) An ant colony system for team orienteering problem with time windows. Found Comput Dec Sci 34(4):287–306

Prins C (2004) A simple and effective evolutionary algorithm for the vehicle routing problem. Comput Oper Res 31(12):1985–2002MathSciNetCrossRefMATH

Reinelt G (1991) TSPLIB—A traveling salesman problem library. ORSA J Comput 3(4):376–384CrossRefMATH

Riera-Ledesma J, Salazar-González JJ (2005) The biobjective travelling purchaser problem. Eur J Oper Res 160(3):599–613CrossRefMATH

Schilde M, Doerner KF, Hartl RF, Kiechle G (2009) Metaheuristics for the bi-objective orienteering problem. Swarm Intell 3(3):179–201CrossRef

Tang H, Miller-Hooks E (2005) A tabu search heuristic for the team orienteering problem. Comput Oper Res 32(6):1379–1407CrossRef

Tricoire F, Romauch M, Doerner KF, Hartl RF (2010) Heuristics for the multi-period orienteering problem with multiple time windows. Comput Oper Res 37(2):351–367MathSciNetCrossRefMATH

Tsiligirides T (1984) Heuristic methods applied to orienteering. J Oper Res Soc 35(9):797–809

Vansteenwegen P, Souffriau W, Berghe GV, Oudheusden DV (2009a) In: Metaheuristics in the service industry. Lecture notes in economics and mathematical systems, chapter metaheuristics for tourist trip planning, vol 624. Springer Berlin, Heidelberg, pp 15–31

Vansteenwegen P, Souffriau W, Berghe GV, Oudheusden DV (2009b) Iterated local search for the team orienteering problem with time windows. Comput Oper Res 36(12):3281–3290

Vansteenwegen P, Souffriau W, Oudheusden DV (2011) The orienteering problem: a survey. Eur J Oper Res 209:1–10CrossRefMATH

Wang X, Golden BL, Wasil EA (2008) Using a genetic algorithm to solve the generalized orienteering problem. In: Golden B, Raghavan S, Wasil EA (eds) The vehicle routing problem: latest advances and new challenges. Springer, pp 263–274

Zitzler E (1999) Evolutionary algorithms for multi-objective optimization: methods and applications. Ph.D. thesis, Swiss Federal Institute of Technology, Zurich

Titel: An Evolutionary Algorithm with Path Relinking for a Bi-objective Multiple Traveling Salesman Problem with Profits
verfasst von: N. Labadie
J. Melechovsky
C. Prins
Verlag: Springer London
Buch: Applications of Multi-Criteria and Game Theory Approaches
Print ISBN: 978-1-4471-5294-1

Electronic ISBN: 978-1-4471-5295-8

Copyright-Jahr: 2014
DOI: https://doi.org/10.1007/978-1-4471-5295-8_10

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Premium Partner