Top

4OR

Published in:

01-03-2015 | Research paper

A fast metaheuristic for the travelling salesperson problem with hotel selection

Authors: Marco Castro, Kenneth Sörensen, Pieter Vansteenwegen, Peter Goos

Published in: 4OR | Issue 1/2015

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

search-config

AI-assisted search

Off

Abstract

The travelling salesperson problem with hotel selection (TSPHS) is a recently proposed variant of the travelling salesperson problem. Currently, the approach that finds the best solutions is a memetic algorithm. However, this approach is unsuitable for applications that require very short computation times. In this paper, a new set-partitioning formulation is presented along with a simple but powerful metaheuristic for the TSPHS. The algorithm is able to obtain very competitive results while remaining at least one order of magnitude faster than the best-performing method so far. The parameters of the metaheuristic were carefully tuned by means of an extensive statistical experiment.

previous article The dirty dozen of 4OR

next article An application of deterministic and robust optimization in the wood cutting industry

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!

inform now

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!

inform now

In Table 14, the gap value is omitted for instance berlin_52. The reason for this is that the MA was able to find a solution with one trip less than the solution with optimal TSP length, which contains nine trips.

Angelelli E, Speranza MG (2002) The periodic vehicle routing problem with intermediate facilities. Eur J Oper Res 137(2):233–247CrossRef

Applegate D, Bixby R, Chvátal V, Cook W (2007) The traveling salesman problem: a computational study. Princeton University Press, Princeton

Applegate D, Bixby R, Chvátal V, Cook W (2006) Concorde TSP solver. http://www.tsp.gatech.edu/concorde

Bektas T (2006) The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega 34(3):209–219CrossRef

Berretta R, Cotta C, Moscato P (2011) Memetic algorithms. In: Cochran JJ, Cox LA, Keskinocak P, Kharoufeh JP, Smith JC (eds) Wiley encyclopedia of operations research and management science. Wiley, London

Castro M, Sörensen K, Vansteenwegen P, Goos P (2013) A memetic algorithm for the travelling salesperson problem with hotel selection. Comput Oper Res 40(7):1716–1728CrossRef

Cordeau JF, Gendreau M, Laporte G (1997) A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks 30(2):105–119CrossRef

Crevier B, Cordeau JF, Laporte G (2007) The multi-depot vehicle routing problem with inter-depot routes. Eur J Oper Res 176(2):756–773CrossRef

Croes GA (1958) A method for solving traveling-salesman problems. Oper Res 6(6):791–812CrossRef

Desaulniers G, Desrosiers J, Solomon M (2005) Column generation. Springer, BerlinCrossRef

Dijkstra EW (1959) A note on two problems in connexion with graphs. Numer Math 1(1):269–271CrossRef

Ghiani G, Improta G, Laporte G (2001) The capacitated arc routing problem with intermediate facilities. Networks 37(3):134–143CrossRef

Hansen P, Mladenović N, Brimberg J, Moreno-Pérez JA (2008) Variable neighbourhood search: methods and applications. 4OR 6(4):319–360

Hansen P, Mladenović N, Brimberg J, Moreno-Pérez JA (2010) Variable neighborhood search. In: Gendreau M, Potvin J-Y (eds) Handbook of metaheuristics. Springer, Berlin, pp 61–86

Kim BI, Kim S, Sahoo S (2006) Waste collection vehicle routing problem with time windows. Comput Oper Res 33(12):3624–3642CrossRef

Laporte G, Gendreau M, Potvin JY, Semet F (2000) Classical and modern heuristics for the vehicle routing problem. Int Trans Oper Res 7(4–5):285–300CrossRef

Letchford AN, Lodi A (2007) The traveling salesman problem: a book review. 4OR 5(4):315–317

Lin S, Kernighan BW (1973) An effective heuristic algorithm for the traveling-salesman problem. Oper Res 21(2):498–516CrossRef

Lourenço HR, Martin OC, Stützle T (2010) Iterated local search: framework and applications. In: Gendreau M, Potvin J-Y (eds) Handbook of metaheuristics. Springer, Berlin, pp 363–397

Or I (1976) Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking. Ph.D. thesis, Northwestern University

Polacek M, Hartl RF, Doerner K, Reimann M (2004) A variable neighborhood search for the multi depot vehicle routing problem with time windows. J Heuristics 10(6):613–627CrossRef

Polacek M, Doerner KF, Hartl RF, Maniezzo V (2008) A variable neighborhood search for the capacitated arc routing problem with intermediate facilities. J Heuristics 14(5):405–423CrossRef

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

Prins C, Lacomme P, Prodhon C (2014) Order-first split-second methods for vehicle routing problems: a review. Transp Res Part C Emerg Technol 40:179–200CrossRef

Solomon MM (1987) Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper Res 35(2):254–265CrossRef

Tarantilis CD, Zachariadis EE, Kiranoudis CT (2008) A hybrid guided local search for the vehicle-routing problem with intermediate replenishment facilities. INFORMS J Comput 20(1):154–168CrossRef

Toth P, Vigo D (eds) (2002) The vehicle routing problem, volume 9 of discrete mathematics and applications. Society for Industrial and Applied Mathematics, Philadelphia

Vansteenwegen P, Souffriau W, Sörensen K (2011) The travelling salesperson problem with hotel selection. J Oper Res Soc 63(2):207–217CrossRef

Title: A fast metaheuristic for the travelling salesperson problem with hotel selection
Authors: Marco Castro
Kenneth Sörensen
Pieter Vansteenwegen
Peter Goos
Publication date: 01-03-2015
Publisher: Springer Berlin Heidelberg
Published in: 4OR / Issue 1/2015
Print ISSN: 1619-4500
Electronic ISSN: 1614-2411
DOI: https://doi.org/10.1007/s10288-014-0264-5

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Other articles of this Issue 1/2015

Multi-period stochastic optimization problems in transportation management

Combinatorial optimization approaches for multi-part cyclic hoist scheduling problem

Semi-Markov decision processes with variance minimization criterion

The dirty dozen of 4OR

Competitive location in cognitive radio networks

An application of deterministic and robust optimization in the wood cutting industry

Premium Partners