Trucking Freight - Rules
Trucking Contest Rules
This is the seventh MATLAB programming contest, and so far we have managed to avoid doing a variation on the Traveling Salesman problem. But we couldn't resist forever. Here's our twist on that well-known puzzle.
You are driving a truck to various stations around a particular vicinity described by a map. The map you drive through is populated with certain stations that contain either some amount of freight (a warehouse) or some amount of fuel (a gas station) for your truck. In this problem you are asked to maximize the amount of freight that you can put in your truck and bring back to your home base. You will be penalized (to a lesser degree) for the amount of gas you collect. So if two trucks bring home the same amount of freight, the one that picks up less fuel is preferred. The actual distance that you travel does not by itself affect the score. Here are some guidelines.
- Your truck must perform a closed circuit (don't run out of gas!)
- There is no limit to how much freight you can carry
- There is no limit to how much gas you can carry
- Stations can be visited no more than once
- When you reach a station, you are required to pick up all available material, whether freight or gas (which is then depleted)
- One unit of gas will move your truck exactly one unit of distance, regardless of how much freight or gas you are carrying
Consider the diagram below. All the short straight-line distances are equal to one unit. You start off at the home base, indicated by the star, with one unit of gas (the yellow box in the left-hand column) and no units of freight (the right-hand column). It would be nice if you could drive to station A and return with two units of freight, but if you go straight from your home base, you'll run out of gas upon reaching A and be stranded. In fact, the only location you can profitably visit is the gas station at location B, where you pick up two units of gas. From there you can proceed to gas station C. At this point you can either drive back to warehouse A and then home (a total distance of sqrt(5)+1) or to warehouse D and then home (also sqrt(5)+1). You can't do both. Which choice is best?
Because you get more freight at D and because the gas collected is the same either way, then D is the optimum destination for your truck. The material at A will have to wait for another day.
You are provided with a four column vector that uses this format
[ x y freight gas]
From this, you need to work out the logistics and return your best answer as a vector of station indices. For the case shown above, the problem might be posed like this (the first item on the list is always home)
[ 0 0 0 1 ] home
[ 1 0 200 0 ] A
[ -1 0 0 2 ] B
[ -1 1 0 3 ] C
[ -2 1 300 0 ] D
and the answer returned would be
[ 1 ] home
[ 3 ] B
[ 4 ] C
[ 5 ] D
[ 1 ] home
From this we can compute the result. Because the result needs to diminish as performance increases, the result is the total amount of available freight minus the amount of freight collected plus the amount of gas collected.
result = total_freight - freight + gas
result = (200 + 300) - (300) + (1 + 2 + 3)
result = 206
If you believe your optimum travel plan is to stay at the home base and not move at all, return the degenerate answer
[ 1 ] home
[ 1 ] home
The result, along with the associated runtime, gets passed to our scoring algorithm before returning a final score, according to the equation
score = k1 * result + k2* e (k3*runtime)
We don't publish the values k1
, and k3
Developing your entry
The files you need to get started on the contest are included in a ZIP-file available here at the MATLAB Central File Exchange. If you download and uncompress this zip-file, you will have the files described below.
The routine that does the algorithmic work is solver.m, and the answer it returns is very simple: [1 1]. This means, go nowhere.
function c = solver(a)
c = [1 1];
A few points to keep in mind about this function and your contest entries:
- The function must have the right signature: one input argument, one output argument. Variable names are unimportant.
function c = solver(a)
- The function must return a vector c of the indices of the locations visited.
To test this function with the test suite in the zip-file, run runcontest.m.
>> [message,results,timeElapsed] = runcontest(drawboard)
The second column of results contains your result, and the third column gives you an estimate of the runtime. message returns a string describing the overall statistics of your submission.
It's sometimes useful to visualize what your entry is doing; you can do this by passing runcontest an input of 1.
>> [message,results,timeElapsed] = runcontest(1)
This provides a plot of the resulting path as each test is completed.
Collaboration and editing existing entries
Once an entry has been submitted, it cannot be changed. However, any entry
can be viewed, edited, and resubmitted as a new entry. You are free to
view and modify any entries in the queue. The contest server maintains
a history for each modified entry. If your modification of an existing
entry improves its score, then you are the "author" for the purpose of
determining the winners of this contest. We encourage you to examine and
optimize existing entries.
We also encourage you to discuss your solutions and strategies with
others. You can do this by posting to the comp.soft-sys.matlab thread that we've started from our newsreader.
Some notes on MATLAB 6.5
The version of MATLAB used for this contest, MATLAB 6.5, uses new JIT-Accelerator technology for fast execution of code. This can have a fairly dramatic effect on the speed of your code. In particular, some things, like loops, that you would have avoided in the past, might be acceptably fast now. If you are not running MATLAB 6.5, you may notice surprising differences between the runtime on your machine and the performance on the contest machine.
The allowable functions are those contained in the basic MATLAB package
available in $MATLAB/toolbox/matlab, where $MATLAB is the root MATLAB directory.
Functions from other toolboxes will not be available. Entries will be tested
against MATLAB version 6.5 (R13).
The following are prohibited:
Java commands or object creation
eval, feval, etc.
Shell escape such as !, dos, unix
Handle Graphics commands
File I/O commands
Benchmark commands such as tic, toc, and
Check our FAQ
for answers to frequently
asked questions about the contest.
About named visibility periods
Contests are divided into segments where some or all of the scores and code may be hidden for some users. Here
are the segments for this contest:
- Darkness - You can't see the code or scores for any of the entries.
- Twilight - You can see scores but no code.
- Daylight - You can see scores and code for all entries.
- Finish - Contest end time.