Trucking Contest Rules

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

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

   [ 1 ]   home
   [ 3 ]   B
   [ 4 ]   C
   [ 5 ]   D
   [ 1 ]   home

  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

score = k₁ * result + k₂* e ^{(k₃*runtime)}

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)

Collaboration and editing 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

Fine Print

The following are prohibited:

MEX-files
Java commands or object creation
eval, feval, etc.
Shell escape such as !, dos, unix
Handle Graphics commands
ActiveX commands
File I/O commands
Debugging commands
Printing commands
Simulink commands
Benchmark commands such as tic, toc, and flops

FAQ