A Comparison of Algorithms for Finding an Efficient Theme Park Tour

Autor: Elizabeth L. Bouzarth, Richard J. Forrester, Kevin R. Hutson, Rahul Isaac, James Midkiff, Danny Rivers, Leonard J. Testa
Jazyk: angličtina
Rok vydání: 2018
Předmět:
Zdroj: Journal of Applied Mathematics, Vol 2018 (2018)
Druh dokumentu: article
ISSN: 1110-757X
1687-0042
DOI: 10.1155/2018/2453185
Popis: The problem of efficiently touring a theme park so as to minimize the amount of time spent in queues is an instance of the Traveling Salesman Problem with Time-Dependent Service Times (TSP-TS). In this paper, we present a mixed-integer linear programming formulation of the TSP-TS and describe a branch-and-cut algorithm based on this model. In addition, we develop a lower bound for the TSP-TS and describe two metaheuristic approaches for obtaining good quality solutions: a genetic algorithm and a tabu search algorithm. Using test instances motivated by actual theme park data, we conduct a computational study to compare the effectiveness of our algorithms.
Databáze: Directory of Open Access Journals
Externí odkaz:
Nepřihlášeným uživatelům se plný text nezobrazuje