Glider
"In het verleden behaalde resultaten bieden geen garanties voor de toekomst"
About this blog

These are the ramblings of Matthijs Kooijman, concerning the software he hacks on, hobbies he has and occasionally his personal life.

Most content on this site is licensed under the WTFPL, version 2 (details).

Sun Mon Tue Wed Thu Fri Sat
           
3
         
Powered by Blosxom &Perl onion
(With plugins: config, extensionless, hide, tagging, Markdown, macros, breadcrumbs, calendar, directorybrowse, entries_index, feedback, flavourdir, include, interpolate_fancy, listplugins, menu, pagetype, preview, seemore, storynum, storytitle, writeback_recent, moreentries)
Valid XHTML 1.0 Strict & CSS
Planning at ORTEC

Right now, I'm in Gouda in a bus heading towards ORTEC, a company that works with planning software and algorithms. Today they organise a in-house day. Together with a number of math students of Study Association Abacus we are going to work on a case titled "Restrictions within the Dijkstra algorithm".

So far we've been underway for 3 hours to get here, currently we're bouncing around in this bus, since the driver seemingly wants to catch up his delay. We're off to a good start, since as soon as we get there, we'll start with lunch (probably after a short boring intro talk). Read on for a "live" report :-)


Now that was a nice lunch. Haven't eaten as much as some of the others, but plenty of green stuff :-) Right now, we're listening to a presentation about Ortec, about what they do and how they do it. They got a fancy Powerpoint presentation with fancy sliding pictures and a guy bending over every few seconds to switch to the next frame (not sheet, since every sheet contains ten-ish frames with a new line of text every time).

Ortec is a company operating in the area of planning and decision support. They use a lot of IT and software solutions for this. Ortec has its grounds in Erasmus university and still has many ties with different universities.

Ortec does a lot with transportplanning, health care, pension funds and banks. Ortec also produces software for giving advice, such as advice in the stock market or the prices of KLM's plane chairs :-)

We're focusing on routeplanning today, as implied by the Dijkstra algorithm above. Ortec has put a bunch of components from other Ortec products together to form a route planning application called Shortroute, which is apparently what we will be working with today.

Shortroute seems like a simple route planning application at first glance, with a simple not-so-flashy interface (which I consider a good thing). It seems to contain features to track different vehicles and allocate resources. The demo shows a number of cryptical codes such as "RC1" and "RC2" which are supposed to mean "Loaded" or "Unloaded" it seems. I hope these codes are configurable to the user :-)

Another main component is localisation of target addresses, iow translating a fuzzy address to actual coordinates. The main challenge here is properly managing the many different different formats and detail levels of map data from different sources.

All this enables shortroute to plan efficient routes from a given place to a number of destinations. There is also the possibility of generating user-friendly directions to get somewhere, which turned out to be a bitch to implement. Another nice feature that is in development is using statistical traffic jam information to minimize driving time. This has significant implications for optimisations, since cached static data cannot take variable traffic jams into account.


We've just had one of the students explain the algorithm of Dijkstra. I helped him a little putting it a bit more formal and algorithmic, so now everybody knows how Dijkstra works again.

Next we were asked to think about the complexity of the Dijkstra algorithm, which is obviously n^2. They suggested there was another implementation called "bucketed dijkstra". This implementation does not give every vertex in the graph a label such as in normal Dijkstra, but it has a bucket for every possible label a node could have. In this way finding the next node to process is simply finding the next non-empty bucket.

The Ortect people argued that this implementation has a worst case complexity of O(n log n) instead of O(n^2). I, on the other hand, argued that this implementation still has a worst case of O(n^2), since every node has to be looked at and every neighbour of the node you are looking at should be considered, regardless of what datastructures are used. Obviously in worst case, the node you are looking for is always the last one you look at. Also, when given a fully connected graph, the number of neighbours is always n - 1. Since you look at all the neighbours of n nodes, which is O(n^2).

So far I don't believe them and they still think they are right. The guy is gonna ask his colleagues in the coffee break. We'll see.


We've just been working for about an hour on the case. The assignment concerned a fictional customer that uses trucks for transport.

After some brainstorming, we have made enough assumptions to have an actual solvable problem. Especially the toll problem is an interesting one which involved lots of (nice) algorithmic discussions. Now only writing down the actual answers is left and I think I've just been elected presenter by the rest of my team...


I've just given a short presentation about our solution. Apart from all the uh-ing, it went rather OK, for an unprepared presentatoin. There were a few easy solutions to the easy problems, which I explained first. For the nasty problem about toll roads, we have designed an ineffecient non-optimal solution which was fast to implement. Also, we've spent some time thinking about a structural different solution, which, given enough research, will yield an optimal and efficient solution, but takes a long time to implement. I think they rather liked this choice they were presented, so we'll see what we hear back from this (There is a prize for the best solution). Now, back to listing to the other presentations.


The guy from Ortec (Joaquim Gromicho , software architect and part time professor in combinatorial complexity or something similar) announced that he had checked about the comlexity of their algorithm with some other people who work with it and that it was indeed an O(n^2) algorithm in worst case. In typical topographical cases, where the maximum degree of nodes lies around 10, this algorithm does indeed perform at O(n*log n). Yes, so much we already figured. So I was right, Nice to be right ;-)

The prize for the best solution is a fancy ortec raincoat. There are two groups that are consdidered for this prize, namely us and the group before us. It's a close call, both teams produced good solutions. In the end, our solution was better presented and thought through, so we won! Yay! :-)

google Tatu

Now, down for drinks.


I've had some interesting talks with a few of the employees (also a graduated UT student I about planning, algorithms and programming. Ortect might be a company where I'd like to work or do an internship or something.

Anyway, we've just eaten at Charlie Chiu's, an "eastern" fast food restaurant, which serves a weird mix between burgers and eastern food. And they have very nice Chicken Wraps, which I had. Now we're back in the train to Enschede. Has been fun, but it's 21:40 now, so I'll be off to sleep soon once I get home.

Comments
Karlijn wrote at 2006-02-23 09:19

And did you have to listen to a 'boring' intro talk? :)

Matthijs Kooijman wrote at 2006-02-23 09:51

Well, it was better than usual company intro talks, since I've managed to write six paragraphs about it. :-)

Joaquim Gromicho wrote at 2006-03-05 17:15

Hello there! Nice blog, you keep! Now I know what you were typing on your laptop all the time…

Remember we talked about a game where you program in C and need to solve many shortest path problems? Can you tell me more about it?

If you prefer to, you may mail me at jgromicho at ortec dot nl.

With my best regards,

The ‘guy from ORTEC’.

Matthijs Kooijman wrote at 2006-03-05 19:06

Hey Joaquim,

the game I talked about is OpenTTD, an open source version of the older Transport Tycoon Deluxe game.

Bart wrote at 2006-03-14 13:51

Too bad you need a copy of the original Transport Tycoon Deluxe game :(

Comments are closed for this story.

 
5 comments -:- permalink -:- 17:36
Copyright by Matthijs Kooijman