Skip to main content
Top

2014 | OriginalPaper | Chapter

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

Authors : N. Labadie, J. Melechovsky, C. Prins

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

Publisher: Springer London

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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).

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

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!

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!

Literature
go back to reference Archetti C, Hertz A, Speranza MG (2007) Metaheuristics for the team orienteering problem. J Heur 13(1):49–76CrossRef Archetti C, Hertz A, Speranza MG (2007) Metaheuristics for the team orienteering problem. J Heur 13(1):49–76CrossRef
go back to reference 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. 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.
go back to reference 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 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
go back to reference 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 (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
go back to reference 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 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
go back to reference Bouly H, Dang DC, Moukrim A (2010) A memetic algorithm for the team orienteering problem. 4OR: Q J Oper Res 8(1):49–70CrossRefMATH Bouly H, Dang DC, Moukrim A (2010) A memetic algorithm for the team orienteering problem. 4OR: Q J Oper Res 8(1):49–70CrossRefMATH
go back to reference Chao IM, Golden BL, Wasil EA (1996) The team orienteering problem. Eur J Oper Res 88(3):464–474CrossRefMATH Chao IM, Golden BL, Wasil EA (1996) The team orienteering problem. Eur J Oper Res 88(3):464–474CrossRefMATH
go back to reference 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 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
go back to reference Feillet D, Dejax P, Gendreau M (2005) Traveling salesman problems with profits. Transp Sci 39(2):188–205CrossRef Feillet D, Dejax P, Gendreau M (2005) Traveling salesman problems with profits. Transp Sci 39(2):188–205CrossRef
go back to reference Glover F, Laguna M, Marti R (2000) Fundamentals of scatter search and path relinking. Cont Cyber 39:653–684MathSciNet Glover F, Laguna M, Marti R (2000) Fundamentals of scatter search and path relinking. Cont Cyber 39:653–684MathSciNet
go back to reference 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 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
go back to reference 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 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
go back to reference Ke L, Archetti C, Feng Z (2008) Ants can solve the team orienteering problem. Comput Ind Eng 54(3):648–665CrossRef Ke L, Archetti C, Feng Z (2008) Ants can solve the team orienteering problem. Comput Ind Eng 54(3):648–665CrossRef
go back to reference 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 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
go back to reference Konak A, Coit DW, Smith AE (2006) Multi-objective optimization using genetic algorithms: a tutorial. Reliab Eng Syst Saf 91(9):992–1007CrossRef Konak A, Coit DW, Smith AE (2006) Multi-objective optimization using genetic algorithms: a tutorial. Reliab Eng Syst Saf 91(9):992–1007CrossRef
go back to reference 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 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
go back to reference 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 (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
go back to reference 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, 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
go back to reference 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 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
go back to reference 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, 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
go back to reference Martí R, Campos V, Resende MGC, Duarte A (2011) Multi-objective grasp with path-relinking. Technical report, AT and T Labs Research Martí R, Campos V, Resende MGC, Duarte A (2011) Multi-objective grasp with path-relinking. Technical report, AT and T Labs Research
go back to reference Montemanni R, Gambardella LM (2009) An ant colony system for team orienteering problem with time windows. Found Comput Dec Sci 34(4):287–306 Montemanni R, Gambardella LM (2009) An ant colony system for team orienteering problem with time windows. Found Comput Dec Sci 34(4):287–306
go back to reference Reinelt G (1991) TSPLIB—A traveling salesman problem library. ORSA J Comput 3(4):376–384CrossRefMATH Reinelt G (1991) TSPLIB—A traveling salesman problem library. ORSA J Comput 3(4):376–384CrossRefMATH
go back to reference Riera-Ledesma J, Salazar-González JJ (2005) The biobjective travelling purchaser problem. Eur J Oper Res 160(3):599–613CrossRefMATH Riera-Ledesma J, Salazar-González JJ (2005) The biobjective travelling purchaser problem. Eur J Oper Res 160(3):599–613CrossRefMATH
go back to reference Schilde M, Doerner KF, Hartl RF, Kiechle G (2009) Metaheuristics for the bi-objective orienteering problem. Swarm Intell 3(3):179–201CrossRef Schilde M, Doerner KF, Hartl RF, Kiechle G (2009) Metaheuristics for the bi-objective orienteering problem. Swarm Intell 3(3):179–201CrossRef
go back to reference Tang H, Miller-Hooks E (2005) A tabu search heuristic for the team orienteering problem. Comput Oper Res 32(6):1379–1407CrossRef Tang H, Miller-Hooks E (2005) A tabu search heuristic for the team orienteering problem. Comput Oper Res 32(6):1379–1407CrossRef
go back to reference 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 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
go back to reference Tsiligirides T (1984) Heuristic methods applied to orienteering. J Oper Res Soc 35(9):797–809 Tsiligirides T (1984) Heuristic methods applied to orienteering. J Oper Res Soc 35(9):797–809
go back to reference 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 (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
go back to reference 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, Berghe GV, Oudheusden DV (2009b) Iterated local search for the team orienteering problem with time windows. Comput Oper Res 36(12):3281–3290
go back to reference Vansteenwegen P, Souffriau W, Oudheusden DV (2011) The orienteering problem: a survey. Eur J Oper Res 209:1–10CrossRefMATH Vansteenwegen P, Souffriau W, Oudheusden DV (2011) The orienteering problem: a survey. Eur J Oper Res 209:1–10CrossRefMATH
go back to reference 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 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
go back to reference Zitzler E (1999) Evolutionary algorithms for multi-objective optimization: methods and applications. Ph.D. thesis, Swiss Federal Institute of Technology, Zurich Zitzler E (1999) Evolutionary algorithms for multi-objective optimization: methods and applications. Ph.D. thesis, Swiss Federal Institute of Technology, Zurich
Metadata
Title
An Evolutionary Algorithm with Path Relinking for a Bi-objective Multiple Traveling Salesman Problem with Profits
Authors
N. Labadie
J. Melechovsky
C. Prins
Copyright Year
2014
Publisher
Springer London
DOI
https://doi.org/10.1007/978-1-4471-5295-8_10