Route-Planning Algorithms for Amusement-Park Navigation

Route-Planning Algorithms for Amusement-Park Navigation

Hayato Ohwada (Department of Industrial Administration, Tokyo University of Science, Noda, Japan), Masato Okada (Department of Industrial Administration, Tokyo University of Science, Noda, Japan) and Katsutoshi Kanamori (Department of Industrial Administration, Tokyo University of Science, Noda, Japan)
DOI: 10.4018/ijssci.2014040105
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

This paper describes route-planning algorithms for navigation in amusement parks (e.g. Disneyland). Unlike conventional shortest-path-finding used for traveling salesman problems, the authors provide several algorithms that consider waiting time estimates in real time, exploit the reservation facilities of an attraction such as Fastpass in Disneyland, and balance a series of enjoyment types such as excitement or relaxation. These features make the new shortest-path algorithms more flexible and dynamic for supporting the cognitive aspects of enjoyment. The authors developed a navigation tool as a Web application in which users select their attractions of interest and the application suggests reasonable and enjoyable routes. An experiment was conducted to demonstrate the performance of this application, focusing on well-known attractions in Tokyo Disneyland.
Article Preview

2. 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)

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 9: 4 Issues (2017): 3 Released, 1 Forthcoming
Volume 8: 4 Issues (2016)
Volume 7: 4 Issues (2015)
Volume 6: 4 Issues (2014)
Volume 5: 4 Issues (2013)
Volume 4: 4 Issues (2012)
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing