MATLAB Programming Contest Blog
April 9th, 2003
Trucking Freight: Mid-Contest Analysis
Bowen Kerins, firstname.lastname@example.org
Friday, April 4, 2003, 4:00 pm EST
Below is an analysis of some of the over 500 entries submitted to the MATLAB Trucking Contest so far.
The international flavor of our contest has been exhibited, to an extent, in the naming used throughout — both variable names and entry names. As of 1:00 pm EST on Friday, the leading entry included each of the words “petrol”, “gas”, “diesel”, and “fuel”, and other variable names contributed along the way such as “notnearlythere” and “ontheway”. These names have all been contributed along the way as entries have evolved since the contest began at 9:00 am EST two days earlier.
As always, there are plenty of wacky entry names and comments. Ned’s entry “bumpy GTI1″ includes the comment “It’s Thursday! Let’s go shopping!” While this is a little different than the typical traveling _salesman_ problem, it suits the algorithms just fine. Other interesting notes:
- Perennial contest combatant Stijn Helsen replaced an algorithm called “Petrol3″ with a related algorithm called “Diesel”. He noted that this was a good idea because, after all, we are driving trucks.
- Colin Ross, whose entries last contest included things like “Quirk with a Twist of Lemon”, submitted an entry called “One time I will do all my own work”. His comment to that entry? “But not yet.”
- Noteworthy contributors have included the mysterious RAU Team, several entries from “Tweaks R Us”, a guy named Joe Test (not as popular as Joe Millionaire, we presume), and the winner for the contributor with the longest name ever, Surapong Lertrattanapanich.
We have created three test cases to work with. The first is a difficult circuit problem — there is some valuable and easily reachable freight, but three-fourths of the freight is not reachable without following a circuitous path to the other stations. It is possible to collect all the freight on this map by following the circuitous path, then doubling back to get the initially reachable freight. It is pretty challenging to find the best path (even with its small size).
The second test case is geographic positions of 29 cities in Western Sahara, Africa. In this problem, all the gas is given up front, and generally random freight values have been provided. We also placed the largest cache of freight very far from the starting point. The amount of gas provided up front is about 10% larger than the proven minimum distance to complete a full tour of all cities, so it is possible to collect all the freight on this map.
By the way, we used the DATALABEL M-file available on MATLAB Central and the GNAME function in the Statistics Toolbox to help make these plots.
We’ll look at a third data set later — the 48 US state capitals. Some will have freight, some will have gas, and we’ll see if anyone can finish the grand tour.
Early entries: Greed is Good, Conservation is Better
PLEASE NOTE — although we have tried our hardest to give credit where credit is due for an algorithm, it is pretty likely that we’ve missed a lot of fantastic contributions. Our apologies in advance.
We’ll focus on many of the entries that we call “corner points”, places where a new entry significantly improved on every other entry that had yet been submitted. The first example comes from Sean Simmons, whose entry “Greedy1″ took an early lead. Its strategy was to find the most freight that can be reached directly, and go straight there.
The solver dashes directly across the map in the Sahara data set, and even though it tracks down many of the biggest hauls, it misses a lot of the goods.
Later entries began to put a premium on gasoline (or petrol or…), basing the decision of where to go next on a cost vs. benefit basis. Heinrich Acker’s “Fuel Priority” entry will likely finish the contest as the entry which most triumphantly crushed all entries that came before it — it beat the best score at the time by almost 20 percent! Lines 30 and 35 of this entry give the formulas that were used — the first to determine which fuel (or diesel or…) depot to travel to, and the second to determine which freight depot to travel to if no fuel was available.
This entry does a much better job with the Sahara data set. Since it only looks ahead one depot at a time, it’s not able to notice the freight bonus available in the circuit data set.
Right on the heels of Heinrich came the possibly Klingon Nath O’Q, whose entry “Petrol2″ really lit up the scoreboard. Even though it was written independently of “Fuel Priority”, it kept the same idea of basing a single step on a cost-benefit metric.
These two entries, submitted directly after one another and written independently, formed the basis of many later algorithms.
Completing the Circuit
The first day of the contest ended with Christian Ylämäki holding the longest lead of the contest so far — six hours in first place. His algorithm included two solvers, a new solver that used MESHGRID and CUMSUM alongside a previous leader, Yuval Cohen’s “Dumpter 3″. “Dumpter 3″ was a direct evolution from Petrol2, but trashed Petrol2 on speed.
Nath O’Q made a triumphant return, revealing himself as Nathan Quinlan in the apt “Petrol3″:
“Petrol3″ was the first entry to complete the circuit map correctly. It uses the same type of algorithm as “Petrol2″, but with a more involved metric calculation. In a rarity, “Petrol3″ took the lead even though it was over 30% shorter than the previous leader.
Master tweaker Stijn Helsen in his “bumpy” series of entries, and other key players, incorporated “Petrol3″ into their own entries. Nathan later shot back with the “Diesel” entry — most current entries include this code to find “on the way” stations that may have been passed by initially.
The Current Leader
The winner of our Early Bird Prize is “MadMax2″ by Paulo Uribe, the winner of our previous Molecule contest. It’s hard to tell just where all the contributions to this file have come from, but they come from Paulo and at least six to ten others. The file clocks in at 340 lines. It runs two algorithms, produces the one with the better score, then runs algorithms to try and add gas and freight to the overall trip.
It still hasn’t been able to complete the tour of the Sahara, but a more appropriate data set (with a mix of fuel and gas) might demonstrate its ability a little better.
The US Capitals Tour
The final test case is the 48 US State capitals. We created a test case with freight and fuel laid about the map; there is about 5% more fuel available than the proven minimal tour of all 48 capitals, and freight has a high enough value that the available score from freight is much higher than the available score from gasoline.
Let’s see how some of our corner point solvers do with this.
“Petrol2″ does a very nice job, but “AddFreight5″ improves upon it and “MadMax2″ does even better (only missing a few cities). Run to run, “MadMax2″ may perform differently, since part of its algorithm is random. At times it does not perform as well as “AddFreight5″ but at others it is a veritable road warrior.
And here is one way (of several) to perform the full loop:
Where does it go from here…?
It’s up to you — submit an entry! There are things to tweak, and plenty of other algorithms to try. Take the lead by using logical indexing instead of FIND or by removing a calculation that never gets referred to later!
I hope this bare-bones analysis of the 574 (and growing) contributions to our Contest was interesting, and best of luck to all as the contest continues.
See you in the queue, The MATLAB Contest Team