A comparison of algorithms for finding an efficient theme park tour
type: Item
instance of: scholarly article
title: A comparison of algorithms for finding an efficient theme park tour
zbMATH Open document ID: 1437.90028
DOI: 10.1155/2018/2453185
author: Elizabeth L. Bouzarth
author: Richard John Forrester
author: Kevin R. Hutson
author: Rahul Isaac
author: James Midkiff
author: Danny Rivers
author: Leonard J. Testa
published in: Journal of Applied Mathematics
publication date: 2019-05-07T00:00:00Z
review text: Summary: 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.
Mathematics Subject Classification ID: 90B06
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 7051357
describes a project that uses: Tabu search
describes a project that uses: Scatter Search
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2018/2453185
OpenAlex ID: W2897016264
cites work: The traveling salesman problem with time-dependent service times
cites work: The Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine Scheduling
cites work: Scheduling examinations to reduce second-order conflicts
cites work: Scheduling with time-dependent discrepancy times
cites work: The traveling purchaser problem with time-dependent quantities
cites work: Time-dependent routing problems: a review
cites work: A dynamic vehicle routing problem with time-dependent travel times
cites work: Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms
cites work: A combined multistart random constructive heuristic and set partitioning based formulation for the vehicle routing problem with time dependent travel times
cites work: Vehicle routing and scheduling with dynamic travel times
cites work: Heuristic Bounds and Test Problem Generation for the Time-Dependent Traveling Salesman Problem
cites work: Q4715981
cites work: An integer programming approach for the time-dependent traveling salesman problem with time windows
cites work: Vehicle dispatching with time-dependent travel times
cites work: A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem
cites work: The time-dependent traveling salesman problem
cites work: Time‐dependent traveling salesman problem–the deliveryman case
cites work: A branch-and-cut algorithm for a production scheduling problem with sequence-dependent and time-dependent setup times
cites work: Integer Programming Formulation of Traveling Salesman Problems
cites work: Solution of a Large-Scale Traveling-Salesman Problem
cites work: A simple min-cut algorithm
cites work: An Effective Heuristic Algorithm for the Traveling-Salesman Problem
cites work: Q4692508
cites work: Future paths for integer programming and links to artificial intelligence
cites work: Tabu Search—Part I
cites work: Q4247468
cites work: A tabu search heuristic for a sequence-dependent and time-dependent scheduling problem on a single machine
cites work: Parallel iterative search methods for vehicle routing problems
Recommended article: An Optimal Algorithm for the Orienteering Tour Problem
Recommended article: Q2973226
Recommended article: Algorithms to solve the orienteering problem: A comparison
Recommended article: Q4861868
Recommended article: An approximation algorithm for the traveling tournament problem
Recommended article: Q3640530
Recommended article: An efficient algorithm for the Knight's tour problem
Recommended article: Improving TSP Tours Using Dynamic Programming over Tree Decompositions
description: scientific article; zbMATH DE number 7051357