Article Preview
Top2. Extended Shortest-Path Algorithm
This paper considers an approach using the traveling-salesman problem. The traveling-salesman problem (TSP) is an NP-hard problem in combinatorial optimization that is studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find the shortest possible route that visits each city exactly once and returns to the origin city. It is a special case of the traveling purchaser problem. This study regards the cities in the traveling-salesman problem as attractions in amusement parks.
The salesman must visit all cities in the traveling-salesman problem, but it is impossible for a visitor to visit all attractions in this attraction problem. Accordingly, users select the attractions they want to visit, and then we apply the traveling-salesman problem method to the selected attractions.
Our paper solves this problem with an algorithm using the branch and bound method. We call this algorithm the Normal Traveling 1 (NT-1) algorithm. Figure 1 presents the NT-1 algorithm. We determine the optimum path to minimize the total time, including transit time, waiting time, and duration time. We then generate a specific formulation to find the optimal solution. First, we define the following notation. We define I as a set of attractions and T as a set of time zones. We further define Mij as the transit time from “attraction j ∈ I” to “attraction i ∈ I,” Wit as the waiting time of “attraction i ∈ I” when the time is t ∈ T, and Pi as the duration time of “attraction i ∈ I.” In particular, t of Wit is the arrival time at attraction i. The traveling time between the departure from attraction j and the departure from attraction i is defined as follows:
(1)The branching in this case is that of the direct path between any two attractions. Xij is a 0-1 variable, defined below:
(2)