## Tag: Thesis

## The Container Positioning Problem

by Jonas Ahmt 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 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 **G**raphical **U**ser **I**nterface (GUI) from which I have included a couple of screenshots below.

*Our program can be used to create random data sets.*

*The solution process.*

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

*3D visualization of the solution.*

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

*:*Containers, DTU, Post with pictures, Skott, Studies, Thesis, UoA, Wikipedia, Other blogs more...

## Sunset, cricket and surf

by Jonas Ahmt on 24 March 2010, under New Zealand, PSV

My todo list for every week always says “Write a blog post”. I am consistently a couple of weeks behind and for some reason it always takes me a war to write (I am quite sure that expression does not exist in English, however, I feel it is so self-explanatory that I will try to introduce it into the language). Where I am going with these considerations, I don’t know. With this post I will hopefully be able to catch up with the present. Because I feel a little sick (well, I did at the time I wrote the Danish text, and I am certainly not going to change it all, just because I am translating it into English the day after) there might be a chance it will be fairly short. One can always hope (it is ironic that, since I translate the English text after I have written the complete post in Danish, I know for sure that it is not what most would consider “short” – however, I am trying to give you the most literal translation of my initial post… except for these stupid comments).

In my last post I mentioned that I have moved back to PSV. I can see my old flat from my room and I have also spent a good deal of time with the crew from Flat 15 where I used to live last semester. Since I, for some reason, have made it a habit to list people, I will continue that trend, listing the people from the flat that has almost become my “second home” down here. Since I am a bit tired the list will only mention name and nationality:

Øystein: Norwegian

James: Canadian

Ilana: American

Kirsty: English

Esther: German

I met Øystein last semester although we seldom met or spent time together – that has changed this semester. The rest are all “new” to The University of Auckland. They were so kind as to let me sleep on the couch in their living room the day I before I could move into my own room in PSV (the day after the fire at my hostel) even though it was barely only Øystein that knew me at that point. I was of course quite grateful for that.

*The view from my room – I can see my old flat from here.*

A couple of weeks ago (yeah, I am still a bit behind with the blog) we (Flat 15, Stefani the Canadian, Jeremy the American and I, the Dane) went to Mount Eden, the highest natural point of Auckland, to enjoy the sunset. It was a nice trip which once again gave me an opportunity to play around with my new camera.

*Random guy skipping past in the background.*

*The group enjoying the sunset.*

The next photos I have are from the surf trip last weekend. However, before I get to that I want to mention that I have also been to my first cricket match ever. Unfortunately I don’t have any pictures from this drama since I had no idea I was going to a cricket match when I went to the university in the morning. But I could not say no when I got the offer to go which meant that I went to the cricket match with all my school stuff and my squash cloths which I didn’t get to use that day. We arrived a couple of hours into the match but apparently that is no big deal. I didn’t have any clue about what was going on for the first couple of hours but slowly the game started to make sense. Some of the other spectators helped us understand some of the finer details of the game which was quite kind of them. I have trouble coming up with any other kind of sport where everybody seems so relaxed. Curling might be close. I have been told baseball might also be kind of similar. Tour de France does have a pretty relaxing feeling to it as well but it does have some periods of intense drama which doesn’t really seem to exist in cricket. We were at the cricket match for seven (7!) hours. We did have a break of about one and a half hours between the two innings where we left the stadium to get some food. I have never tried to leave the stadium during a sports match just to come back later without having missed any part of the game (the players also had a break when we were eating). The guy who invented cricket must have been a man of great patience. Not only does the original cricket rules allow a game to last up to five days; if there is the slightest bit of rain, the rest of the match will be put off until half an hour after the rain has stopped. We did get to see that rule applied… hooray! We spent seven hours looking at men throwing a ball about 500 times while some other guy tried to block it with his bat, followed by one of the other ten players on the field walking to the ball to give it to the guy who threw it in the first place. We watched that, and then also an hour of some vehicles dragging a big “towel”, trying to dry the field after the rain while the crowd kept hoping that one of the guys on the field would be tripped by the “towel”. Unfortunately it did not happen. A very interesting experience indeed.

Since this is a post filled with randomness: I also want to mention that I am trying to be a bit active down here. I have played squash and run a couple of times. I have signed up for “Handball for beginners”, the only handball thing they offer at The University of Auckland. Unfortunately it is probably a bit too much a “beginners’” thing for me even though it is about seven years since I last touched a handball (which seems a bit scary to me). I was offered to join the “advanced” team for their games so I will probably do that if my feet can survive it.

Also! And this may come as a surprise, especially for me, I have started taking salsa lessons… I am not entirely sure how THAT happened but I guess it comes from some misguided idea I had before returning that I wanted to try some new stuff. Besides, both Øystein and Ilana tried to convince me and in the end it apparently worked somehow. So now I am going to have eight salsa lessons. Two of them have already been completed, although I have only participated in the first due to sickness (on my part) at the time of the second one. That probably means I will feel even more lost next time, as if my lack of sense of rhythm wasn’t enough.

I apologize that this post can seem a bit disconnected – I will once again use the explanation that I am kind of sick (even though the real reason is laziness). With that apology I will allow myself to take another weird jump. I spend most of my weekdays on my master thesis – the thing I am basically here for and which I have not mentioned on my blog so far. But now I HAVE mentioned it and then there can be no doubt that I am working hard on it with Skott. I assume that I will make a post at a later point, explaining exactly what the thesis is about and which might make people die from boredom. I can reveal that it is about containers… But that will have to wait till some other time.

While the weekdays are spent on the project, my weekends are fairly free. That means that I last weekend found myself on my way to Raglan, the surfers’ paradise in New Zealand. Going there was probably another one of those “let’s try something new” ideas. It was an extremely nice weekend with beautiful weather, a nice beach and a good group consisting of eight people, mainly from Parnell Student Village: Three Canadians (they are the new Germans this semester – they are everywhere), two Americans (although one of them claimed he could also be called a Kiwi), a French guy, a Norwegian and then me, the Dane. We lived at a hostel a bit outside of Raglan which looked like it was placed in the middle of a jungle in Colombia (or any other country in South America, I presume). It was really nice with free pool table, decent cooking facilities and then there was the sauna which we chose to use both nights. The surf went surprisingly well. With that I mean that I got through it unhurt; I did not drown (my initial criteria for success), destroy my ankles or hurt myself in any other way. I (and the rest of the members of the group) all managed to get up on the surfboards at least a couple of times. When I got home from the surf trip I realized that I had had another encounter with my arch nemesis. I am of course talking about the sandfly which had left a couple of stings at my feet which will now bother me extremely for the next many nights. I am considering trying to come up with some kind of scheme to take revenge. I do owe those bastards some kind of practical joke. But then again, I am not sure if insects understand practical jokes.

*I actually don’t have any photos of the surf itself so you will have to just be content with a picture of me… and in the following photos, the other people that were with me on the trip.*

*Øystein and Max in a friendly fight on the beach.*

*Stefani, Laura, Robin and James sitting on a trunk.*

*A goat and the small tent it lives in at the side of the road – it was actually NOT part of the group.*

*And to also have a photo of the last person on the trip:: Ilana in the middle (Max at the right, me at the left) after a well-deserved lunch in Raglan before going back to Auckland.*

In the end I want to talk a bit about the internet in New Zealand once again which I also did a couple of times last semester (as I am sure the people who have somehow managed to stick with the blog that will easily recall). However, I have also promised to not complain as much about stuff this time around, so I’ll just not mention the internet… and this way another post can get the tag “anticlimatic endings”.

*:*Ankles, Bad segues, Containers, Cricket, Handball, Ilana, James, Kirsty, New Zealand, Post with pictures, Salsa, Sandflies, Skott, Sunset, Surfing, Thesis, Øystein more...