Re: FN-FORUM: Challenge

date posted 25th May 2007 09:21

Mark Hutchinson wrote:
> It it was only that simple - scenario 120 orders, 15 vehicles, multiple
> destinations.
>
> There are three different decisions that need to be made (i) which orders
> need to go on which vehicles and (ii) which routes and (iii) in what order
> do deliverys need to be made.
>

You could look at what information will suffice. Can you answer question
(i) simply by plotting the coordinates of all the points (using OS grid
references for example) and if the coordinate falls within a defined
area it goes with a certain driver?

This means you can take some account of the roads involved.

I'm surprised that (iii) is a requirement. I would expect a driver to be
sufficiently motivated to finish early and determine himself, from
experience how best to do the job.

Could you present a map to the person who currently does this job with a
system recommendation, then allow them to move things around? This will
provide valuable feedback, perhaps some automated learning system could
be developed, and it gives the company the flexibility they will
probably want sooner or later anyway.

Also by having someone check and allowing changes you do not need to
worry about selecting the incorrect route too much.

On a general point, the travelling salesman problem is difficult, but
only really when you are trying to solve it completely and come up with
some general purpose algorithm which is efficient.

By splitting the problem up into routes you are normalizing it somewhat,
which allows you to introduce optimisations in the calculations.
Imagine all the points are within a mile of the M1 south of Sheffield,
and at least 10 miles apart. In that case you could simply choose the
next delivery south of the previous one.

Shortest route algorithms generally work by selecting a starting point
and then calculating all the different combinations of points and their
total cost. The one with the lowest cost is the one you choose.

Optimisations are achieved by cutting out some of the possible
combinations. So in my example you would start at the top point and
could not go north, which only has several combinations when there are
two delivery points on the same latitude.

By calculating the total cost one step at a time you can refer to the
shortest found cost and if the current combination exceeds that then you
give up on it.

By adding some bias to which point is chosen next you can encourage the
algorithm to find the shortest route in one of it's early iterations,
assuming there is some usual pattern of a particular for, for example,
the route tends to follow a clockwise rotation back to base.

It is also possible to find a upper limit for the shortest distance, and
I have the feeling that there is a formula out there which can provide
that quite quickly, but I do not have it to hand.

I would advise doing things close to the way they are currently done,
where possible. Should you link into some traffic aware route finding
software and it does a worse job than at present you will become unpopular.


Hope some of this helps

Regards
Richard



--
Artumi Systems, 58 Salmon Street, Sheffield, S11 8DD.
Tel 0114 250 7654, Web http://www.artumi.com
VAT Reg 889 0317 88