Iqon's New Zealand Blog

Tag: DTU

The Container Positioning Problem

by on 27 June 2010, under DTU, New Zealand, UoA

What this post is about
I think I have promised a couple of times that this post would appear on my blog at some point. Apparently “at some point” is exactly this very moment (or rather, probably some seconds/minutes/hours/days/weeks/years/decades/centuries ago, depending on when you have decided to read it compared to the time I wrote this). If you didn’t really care for last semester’s post about my studies (which I of course assume that you, avid reader of my blog, has read long ago), there is a good chance that you will find this post pretty boring as well. I will assume it will become quite nerdy. On the other hand, I don’t expect that anyone would ever choose to visit this blog unless they can handle a bit of nerdiness.

What I study
It seems like a good idea to start from scratch, so that’s what I’ll do, even though I would assume that most people who have somehow ended up at this site already have a vague idea about what it is I study. I am currently trying hard to finish my master’s degree at The Technical University of Denmark (DTU), called MMC Master, an acronym for Mathematical Modelling and Computation Master. The name reveals a good deal about what most of my courses are about: Formulating mathematical models and using them to compute exciting numbers. A mathematical model is not some geeky guy or girl going on catwalks. Neither is it a bunch of clay shaped into numbers, symbols or multiplication signs. They can, however, be (partly) responsible for the bad sense of humor demonstrated in the last two sentences as I have spent almost five years studying them by now. No, mathematical models are a series of formulas set up to represent some kind of real life problem. When all of Europe (and especially the UK) got yet another reason for hating Iceland, this time due to the eruption of Eyjafjallajökull which prevented almost every airplane around Europe from flying, mathematical models were used to estimate the risks of flying through the ash spewed up by the volcano. Likewise, models were created to compute how long the eruption would last and the probabilities that other, larger volcanos in the area, would erupt.

The type of mathematical models I usually deal with are of a bit different kind, however. During my studies, I have chosen to focus on Operations Research (OR). OR uses a combination of statistics, mathematical modeling and mathematical optimization to calculate optimal or near-optimal solutions or proposals to solutions for different decision-making problems. It is heavily used to create production plans and work schedules while it also plays an essential role in route planning and almost any logistic problem you can come up with.

What my thesis is about
My thesis deals with what has been named The Container Positioning Problem. I am writing it with my study buddy, Skott, who was also in Auckland last semester, taking the exact same courses as me. Skott’s description of the project can be read on his blog- it is all in Danish, though, since he’s too lazy to translate it into English. Either that, or he is clever enough to know that it is a waste of time to do the translation since nobody would want to read these kinds of blogs anyway, except for a few family members, perhaps. Many of the people I meet down here seem to be surprised that we are working two people on the same project. I am glad that we do have that opportunity at my university as I’m sure the final result will be more than the sum of its parts. It is extremely helpful to have someone to discuss with on a daily basis about the progress of the thesis, without having to schedule meetings with supervisors who (understandably) don’t know all the exact details of what we have been doing with the project since the last meeting. We have two supervisors, one in Denmark and one in New Zealand who have both been quite unavailable for long periods of time. In those situations it has been even more helpful to be two people on the same project.

The project is about something as exciting as moving containers. When a container ship arrives at a harbor, the containers it brings with it are often paced in a terminal where they will be located for storage for a while, until they need to depart again, either via trucks further into the country, or continue with another ship. In the meantime (between arrival and departure of the containers) it is important to have a plan for how the containers should be moved around at the terminal: A container which is about to leave must not be buried underneath a lot of other containers since the crane can only pick up the ones placed at the top of a stack. It is important to spend as little time as possible to move the containers around; the cranes are expensive to use, especially if they have to be controlled manually, which is still the case at many terminals.

Containers

Containers at Auckland Harbor – can you imagine anything more exciting?

The last couple of years research has been done to try to solve the problem using OR methods. In 2008, Louise K. Sibbesen, a Danish Ph.D. student from DTU, wrote her doctoral thesis about the problem. Her approach was to use a so-called metaheuristic, a method in mathematical optimization which often results in “good” solutions without guaranteeing that the found solutions are also optimal. It is often acceptable to find just “good” solutions (measured in e.g. profit) to many of the problems which occur in real life. These solutions can still easily be better than what a human being would be able to find manually. Even if the solution is “only” on par with the ones that can be found manually there is often a certain value in having a computer program being able to compute these solutions automatically. Often it can be done much faster and the labor cost can be saved. In my bachelor thesis I (and two other people) developed a heuristic to help plan which teachers should be assigned which class to teach during a school year in the high schools around Denmark. Already before the thesis had been handed in, the heuristic had been implemented in the commercial product Lectio, used by the majority of Danish high schools. Later we were awarded the prize for best bachelor thesis at DTU by McKinsey & Co as I also mentioned on this blog last semester.

Optimal solutions are of course always attractive. Therefore, a student from The University of Auckland, Antony Phillips, decided last semester to look at the problem once again but from a different point of view. He wanted to prove that there was another approach to solving the problem which, possibly, could lead to optimal solutions in the future, without using heuristics. Using heuristics is in some circles seen as “cheating” since they don’t necessarily lead to pure, perfect solutions. He wrote about the subject in his Fourth Year Project which is kind of similar to a Danish bachelor thesis. Here he found a number of different mistakes and deficiencies in the original doctoral thesis by Sibbesen.

Skott and I are now trying to carry on the torch with our project. Our goal is to get closer to be able to solve real life sized problems to optimality. We spent the first month on going through the two previous theses about the subject and did find some more mistakes and deficiencies we found it necessary to take into consideration in the mathematical model. The ideal for a mathematical model for problems such as the one we are dealing with, is for it to follow a specific structure which makes the problem linear. Basically this means that there exist certain rules for how the mathematical formulas describing the problem can be set up. The special thing about linear programming (LP), as it is called if the formulation follows this structure, is that there exists certain solution methods (The Simplex method), which can be exploited. These are methods which run extremely fast and have been perfected through many years. Therefore it pays off to comply with these restrictions, even though it also means that a certain amount of thought is required to formulate these models. A mathematical model which describes an LP problem consists of two parts: An objective function plus a number of constraints. The objective function describes the goal for the optimization, which in our case is to minimize the use of the crane at the terminal. The constraints define what is meant by a feasible solution. For instance, our mathematical model contains constraints such as “a container can only be picked up if it is on top of a stack”, “a container needs to be at either exactly one position or be moving at any given time” and “a container needs to arrive to/depart from the terminal at the times specified by the given data”.

After we had spent some time looking into the previous theses we created our own model which corrected the mistakes we found in the original ones. At the same time the model is now more realistic since it captures more details of the problem as it exists in real life. For example the model now constraints how fast the crane can move, not only when it carries a container (which was the case in the original models) but also when it doesn’t carry anything at all. We have also implemented a solution technique which uses a “rolling time window”. Instead of trying to take all containers into consideration which might arrive or depart within the planning horizon, we cut down the focus to be a subset of the full period. In container shipping there often exists great uncertainty about the precise arrival and departure times for the containers. Often precise information doesn’t arrive until fairly close to the actual arrival or departure of the containers themselves. Therefore it doesn’t make sense to make big, detailed plans for every single container since there might very well arrive new information later which can completely ruin the meticulously laid plan. What we do instead is to focus on containers which are about to depart or arrive in a given period. The placement of a container which doesn’t depart until much later is fairly irrelevant as long as it doesn’t create conflicts with a container that is actually about to depart which need to get to the top of a stack so the crane can pick them up. The solution technique we use thereby focuses on the containers which are about to depart within a foreseeable future (a day or two). It is a continuously running solution process which moves the time window focused on as time goes by. Not only does this solution technique represent the reality much better than an assumption about all information being known from the very beginning; working with smaller time periods also makes the problem significantly easier to solve, resulting in faster solution times.

With this method (and a number of other clever techniques) we have accomplished some pretty good results so far. A problem which took 3000 seconds to solve previously, after Philips’ modifications to the original model, now takes about 50 seconds to solve. That is a fairly good improvement. Our program cannot yet solve problems so big that they could represent real life cases, though. Especially Skott has also spent a good deal of time on implementing a Graphical User Interface (GUI) from which I have included a couple of screenshots below.

Problem generation.png
Our program can be used to create random data sets.

Solution process.png
The solution process.

Gantt Diagram.png
A Gantt-diagram which shows the solution computed by our program.

3D visualization 1.png
3D visualization of the solution.

3D visualization 2.png
Example of a container being moved.

And that is pretty much our project. We are supposed to hand it in in the beginning of August and present it a couple of weeks after. We will be using the last available time to test our program, discuss the results and make some conclusions on our formidable work.

What these headlines are doing in this blog post
Pass… Maybe it is a weak attempt to make this text, full of technical terms and container talk, seem more clear and less boring. I think I failed (but at least the container pictures are colorful).



27 Comments :, , , , , , , , more...

Looking for something?

Use the form below to search the site:

Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!