MATLAB Programming Contest Blog
April 9th, 2003
Trucking Freight: Algorithm Analysis
By Lucio A. Cetto
As a previous participant in the addictive MATLAB Contests, I have to restrict myself this time to just observing it (I am now working at the MathWorks). I enjoyed watching everybody collaborating towards a common objective. Of course, I personally think everyone that submitted at least one passing entry should get a reward.
I wish I could have participated. From the sidelines, I wanted to point out that there were cities with no gas or freight. I also was noticed that no one exploited the fact that the cities were clustered. That might have alleviated the bottlenecks reducing the search space a little… but it’s hard to say.
After the competition, I was invited to analyze the winning entry. The first thing that caught my eye was the fact that Ave kept his best tricks for the end. It was a good strategy. Ave was also a persistent participant, making his first entries early in the contest.
The winning entry breaks down as follows: there is one main solver (“subsolver”) and a set of path-refining functions. The refining functions are used inside “subsolver” as needed. Understanding them helps to figure out the different strategies used in the overall approach.
This function analyzes a given pre-calculated path and determines if the path can be broken at some point to include a non-visited city with freight. A verification needs to be done in order to ensure that the new path will have enough gas to be completed after adding the new route.
This function seems to be a copy from “addfreight”, but its objective is instead to insert to the path non-visited cities with available gas as long as there is a profit. This explains why this function is called always before “addfreight”. More gas, then more cities.
Savegas looks at the path and tries to see if there is a shorter path that goes to the same cities. It does this by permuting the elements of the path, checking to see if the path is shorter and also feasible.
This function studies a path and tests for cities which can be swapped. This is one of the most common strategies used in travel salesman problems, and is certainly a good option to get away from the local minimum traps.
All the refine functions need as an input a first route to work with. The functions “diesel2″, “routefinder”, “petrol3″ and “findenum” are all different strategies to provide a first path. Generally they aim to build the path iteratively, adding one city at the time, searching for a city which must met a variety of criteria, primarily one prefers a city with enough gas for the round trip or for a safe return to home. Other more complex ideas will look for a city with gas and then pick all the freight that is on the road.
It is difficult to give credit to all of the people involved in the final entry. However I would like to congratulate Heinrich Acker, Nathan, Sean Simmons and E. Brian Welch for contributing early in the contest with the “base” algorithms that were carried across the whole contest. They provided a good starting point for other to work from. After that: Christian Ylämäki, PU, Jack Snoeyink, Hannes Naudé, RAU team, and Yi Cao fed the contest with new ideas, especially by modifying and improving the performance of the early leaders. Stijn Helsen deserves credit as the best improver across the entire contest. Late in the contest, Christian Ylämäki and Jack Snoeyink pushed for the lead, but there was Ave waiting the final moment to show up some hidden tricks and win the glory.
Congratulations all. We look forward to seeing you in the queue next time around.