The Application of Hanoi Towers Game in Logistics Management

The Application of Hanoi Towers Game in Logistics Management

José Alberto Hernández Aguilar (Autonomous University of Morelos State, Mexico), Augusto Renato Pérez Mayo (Autonomous University of Morelos State, Mexico), Santiago Yip Ortuño (Autonomous University of Morelos State, Mexico), Alberto Ochoa-Zezzatti (Autonomous University of Juarez City, Mexico) and Julio César Ponce Gallegos (Autonomous University of Aguascalientes, Mexico)
DOI: 10.4018/978-1-4666-9779-9.ch022
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

In this chapter we discussed the application of Towers of Hanoi in logistics management applications, for this purpose. Firstly, we discussed how pile problems applications impact in logistics, later we discussed the Hanoi Towers application in Logistics Management, its mathematical model and common solutions applying different paradigms (iterative, recursive, and heuristics), we present an in depth analysis in genetic algorithms, later we present the analysis of a genetic algorithm applied to solve basic Hanoi Tower game (three pegs three discs) implemented in C language, and later we discuss its generalization from three to four discs. Finally, we discussed preliminary results and present our conclusions. Main contribution of this chapter is demonstrate game theory, specifically Towers of Hanoi, can be applied to solve logistics problems, and an approach for the generalization of basic Hanoi Tower form, three discs to four discs, by means of genetic algorithms implemented in C language.
Chapter Preview
Top

1. Introduction

Lots of situations in real life present a configuration of items stacked up to a pile that requires to be transferred in another pile with another order of items, this type of problems can be identified in management logistics also. According Hempfel and Schmiedel (2006) the question that involves an optimization problem is: How to do it in the best way using only available resources and devices?

1.1. Pile Problems Applications in Logistics Management

Some examples are mentioned in (Hempel and Schmiedel, 2006): imagine a port where there are several containers and is necessary to load or to unload loading from the containerships, or suppose large concrete parts for a modern bridge or construction of buildings, or the shunt of trains in a marshaling yard, or patient plays. A container pre-marshaling problem is reported in (Shan-Huen & Tsan-Hwan, 2012) which purpose is finding a set of container movements to reach a final container arrangement by satisfying certain restrictions. Lu & Dillon (1995) discuss a parallelism implementation of Towers of Hanoi on which is permitted concurrent moves of disks in a single step. These authors analyzed three versions of parallelism considering two factors: the order of moves of disks and the resource utilization of pegs. They present a common technique for getting the non-recursive implementation by considering minimum steps. All of these problems can be modeled by applying basic principles of the Towers of Hanoi.

1.2. Mathematical Modeling

Puzzles are connected with graphs, it means can be modeled by using graphs, vertices of the graph represent configuration and graph edges define possible moves of the puzzle (Cull, Merril and Van, 2013). According (Hempel & Schmiedel, 2006) to describe pile problems more precisely is highly recommended using graph theory. For these authors:

For a given directed graph G = (V, A) and its vertices v ϵ V can be used the following notations: NG+(v) is the set of all successors of v, NG-(V) is the set of all predecessors of v. dG+(v) represents numbers of outgoing arcs of v and dG-(v) numbers of incoming arcs of v respectively. For G1 = (V1, A1) and G2 = (V2, A2) the union of G1 and G2 is defined as G1 U G2:= (V1 U V2, A1 U A2). A cycle in a directed graph G = (V, A) is a closed path in G. The directed graph G = (V, A) is called a pile, if and only if G is finite and does not contain a loop or a cycle. The vertices of G represent the elements of the pile; the arcs of G represent the order in which the elements are piled up. A step is the move of an element of data structure to another place. This place can be in different pile or in an auxiliary place if it exists (Hempel & Schmiedel, 2006).

Figure 1 and Figure 2, show an example of typical pile problems, meanwhile graphs representing the starting Gs and final Gf are shown below (Hempfel and Schmiedel, 2006):

Figure 1.

Starting situation

Figure 2.

Required final situation

Note how arcs in Figure 3 and Figure 4 correspond to inverted graphs.

Figure 3.

Starting pile Gs

Figure 4.

Final pile Gf

Towers of Hanoi

Also called the Towers of Brahma or Towers of Lucas; is a mathematical game, puzzle or toy that is made of three pegs (poles) and a number of disks of different sizes (in its basic form consisting of three disks), which can be moved into any peg (Hofstadter, 1996). The game starts with the disks placed in ascending order of size in one peg, the smallest at the top, forming a cone or pyramid (see Figure 5).

Figure 5.

Towers of Hanoi Basic game (three pegs - three disks) source (Hofstadter, 1996)

The purpose of the game is moving the entire pile of disks from the origin peg to the destiny peg, by considering next simple rules (Scheinerman, 2000):

  • Step 1: Sole one disk can be moved each turn.

  • Step 2: A move consists of taking the upper disk from one of the stacks and placing it on top of another stack.

  • Step 3: Is not allowed a disk be placed on top of a smaller disk.

According Mishra and Vishnoi (2015) with three single disks, the game can be solved in seven steps. The minimum moves required to solve a Tower of Hanoi puzzle is 2n - 1, where n represents number of disks, as can be seen, this is an exponential number that increases when n increases.

Complete Chapter List

Search this Book:
Reset