A comparison of algorithms for finding an efficient theme park tour
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.
- An Optimal Algorithm for the Orienteering Tour Problem
- A survey on route planning algorithms, focusing on its touristic applications
- Algorithms to solve the orienteering problem: A comparison
- scientific article; zbMATH DE number 836777
- An approximation algorithm for the traveling tournament problem
- Efficient algorithm for a kind of exploration problem with N vehicles
- An efficient algorithm for the Knight's tour problem
- Improving TSP Tours Using Dynamic Programming over Tree Decompositions
- A branch-and-cut algorithm for a production scheduling problem with sequence-dependent and time-dependent setup times
- A combined multistart random constructive heuristic and set partitioning based formulation for the vehicle routing problem with time dependent travel times
- A dynamic vehicle routing problem with time-dependent travel times
- A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem
- A simple min-cut algorithm
- A tabu search heuristic for a sequence-dependent and time-dependent scheduling problem on a single machine
- An Effective Heuristic Algorithm for the Traveling-Salesman Problem
- An integer programming approach for the time-dependent traveling salesman problem with time windows
- Future paths for integer programming and links to artificial intelligence
- Heuristic Bounds and Test Problem Generation for the Time-Dependent Traveling Salesman Problem
- scientific article; zbMATH DE number 1302201 (Why is no real title available?)
- scientific article; zbMATH DE number 194544 (Why is no real title available?)
- scientific article; zbMATH DE number 947471 (Why is no real title available?)
- Integer Programming Formulation of Traveling Salesman Problems
- Parallel iterative search methods for vehicle routing problems
- Scheduling examinations to reduce second-order conflicts
- Scheduling with time-dependent discrepancy times
- Solution of a Large-Scale Traveling-Salesman Problem
- Tabu Search—Part I
- The time-dependent traveling salesman problem
- The Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine Scheduling
- The traveling purchaser problem with time-dependent quantities
- The traveling salesman problem with time-dependent service times
- Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms
- Time-dependent routing problems: a review
- Time‐dependent traveling salesman problem–the deliveryman case
- Vehicle dispatching with time-dependent travel times
- Vehicle routing and scheduling with dynamic travel times
This page was built for publication: A comparison of algorithms for finding an efficient theme park tour
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1741683)
