Tower of Hanoi at Large
JeanFrancoisPuget 2700028FGP Visits (6801)
Did you know that the Tower of Hanoi puzzle had real world applications? I was lucky enough to be involved with one such application . Before describing the application, let me recap briefly what the puzzle is about. I'll borrow the definition from wikipedia.
The Tower of Hanoi (also called the Tower of Brahma or Lucas' Tower, and sometimes pluralised) is a mathematical game or puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.
The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:
With three disks, the puzzle can be solved in seven moves. The minimum number of moves required to solve a Tower of Hanoi puzzle is 2n - 1, where n is the number of disks.
The puzzle can be generalized in many ways. A classic one is to increase the number of rods. Another is to generalize the third rule of the puzzle:
3. No disk may be placed on top of a smaller disk.
What if we relax a bit this rule, and only state precedence constraints between disks? We could forbid some disk order, saying that disk A cannot be put above disk B for a given disk pair <A,B>. Note that we said above, and not on top. It means we want to forbid any stack where A is above B, whatever the number of disks between A and B.
We will also put a limit on the number of diks that can be stacked on a given rod.
We'll consider a generalized Tower of Hanoi (GTH) puzzle where the number of rods is limited, but quite large, rod height is limited, and where a number of precedence constraints are given.
The classical puzzle is obtained from GTH with 3 rods with height greater than the number of disks, and a precedence constraint between each pair made of a disk and a disk of smaller size. Indeed, in this case, we cannot put a disk above any disk of smaller size.
Now that we have defined GTH, where did we apply it?
We applied it to the problem of unloading/loading containers from/to ships. In that case, rods represent areas on the ship or on the yard that can receive a container stack. Disks are containers. They can be stacked up to a given number (say 9). Containers are moved using large cranes. Crane movement scheduling is in itself an interesting problem we worked on too, but let's focus on the GTH here. Point is that cranes can only remove a container from the top of a container stack and add it on another container stack (can be empty). The similarity with Tower of Hanoi is perfect here, each area being used to hold a stack of containers.
The precedence constraints can come from various sources. For instance, some containers are so heavy that they should not be stacked on others. The main source is however coming from the order in which ships are available for loading/unloading.
Let us look at a very simple example with 2 arriving ships and 2 departing ships. The port authority has to unload the first two ships and store the containers in a yard. Then, when ship 3 arrives, some containers are loaded on it. Latter, when ship 4 arrives, remaining containers are loaded on lt.
We therefore have 4 instances of GTH as follows:
Let' consider two containers A and B arriving on ship 1 such that A should be loaded on ship 4 and B on ship 3. Assume we stack A on B when unloading ship 1. When ship 3 arrives we must first remove A from the stack, put it somewhere else, then come back and take B and move it to ship 3. We therefore have at least two crane movements to load B on ship 3, one of them being irrelevant as it moves container A. In order to avoid this we state a precedence constraint: A should not be above B. More generally, a container A should not be put above a container B if the ship to which A will be loaded arrives after the ship to which B will be loaded. Now we know why such constraints are called precedence constraints! As soon as you get several ships you get many of those constraints.
There are also other constraints than the precedence constraints coming from destination ships. Containers come with different sizes, hence you can only stack containers of the same size together. There are constraints forbidding some container configuration. For instance, you cannot have a food container close to a chemical container. There are constraints coming from cranes physics as cranes can only reach some of the available areas, but not all. The problem is then to schedule all container movements, meeting all constraints. Container movements are decomposed in several sets of decision variables.
Now imagine you have one of the busiest container port of the world, the Port of Singapore, with tens of millions of containers a year.. You get a very complex and large GTH. It so happens that we solved this puzzle for the Port of Singapore Authority (PSA) As written here:
ILOG Constraint Programming has been used for several years by PSA Singapore to optimize yard slot allocation for transhipment containers. It determines the best yard slots to place containers and the order in which they should be picked from the yard and brought to the quayside. PSA states that it has reduced the time to produce loading plans from hours to 30 minutes.
Another interesting source is this video (sequence starts around 1'30) .
We used constraint programming (CP) as the primary tool for this application. Interested readers will find an example of how CP can be used to solve scheduling problems in this post. The PSA application is more complex and has many side constraints, but it contains a scheduling problem at its core.