I'm wondering if anyone's written an algorithm before, not necessarily in
Databasic, but anything for that matter, which can find the closest match,
or rather the closest utilisation of a series of delivery distances.

I want to write a routine which takes a list of typical delivery times in
minutes from base (for argument's sake, over 100 deliveries), such as 120
minutes, 55 minutes, 40 minutes, 100 minutes etc. and tries to find the best
utilisation, fitting in as close as possible to the maximum time available
during the working day.

The deliveries would always be made from the base, in other words, there is
no going from A to B to C. It would always be A to B and then back to A.
Then A to C and then back to A.

If I could loop through all the deliveries that need to be made, all of
which will have an approximate number of minutes attached to them, and
distribute them accordingly.

While it's very easy to just keep on looping until I've reached no more than
the maximum time for a day's work, that would not provide the most efficient
utilisation, because someone might only fill 70% of a day's work, because
the next order would take them over 100%.

I thought it might be an interesting subject anyway and possibly a diversion
from the strange posts that appear to be on the group!

Just as a quick thought without much forethought...

I'd start by sorting the deliveries from largest to smallest and then cycle
through each delivery truck/person and assigning the longest delivery times
first and work towards the smallest. With each delivery cycle through the
trucks to see if any can take it, if not move to the next smaller time. The
sort of "put the big rocks in first theory...".

You'll have to add some code to ensure that deliveries that could/should
have been delivered in the previous days get sorted to the top of the list
for the next days deliveries.

I suspect that this would be a good way have handling things but may not be
the best as some possible deliveries will be held until the next day.

This method would be quick and easy to code.

Anyway, it's a thought that might spark others.

Regards,

Dale

"Steve" <dajda (AT) bu430 (DOT) cp.net> wrote

Steve wrote:

While not exactly what you're asking for, you may find information at
the following link useful.

http://www.nist.gov/dads/HTML/travelingSalesman.html

--
Kevin Powick

Code at the bottom. modify anything anyway that works
This takes a work item with two elements: trip # and distance
It's got a hard-coded max
it builds a list of items that fit into the max then goes thru to see if by
deleting any single item you can replace it with one or more from the
residual list that will either increase the max distance covered or maximum
trips within the limit.

Mark Brown


"Steve" <dajda (AT) bu430 (DOT) cp.net> wrote

open 'workfile' else abort
read r from 'mark' else abort
dx = dcount(r<1>,@vm)
tot = 0
max = 35
l2 = ''
for i = 1 to dx
d = r<2,i>
if tot + d le max then
tot += d
l2<1,-1> = r<1,i>
l2<2,-1> = r<2,i>
r = delete(r,1,i)
r = delete(r,2,i)
dx -= 1
i -= 1
end
next i
dy = dcount(l2<1>,@vm)
*
* we have a list (l2) with enough items to be LE max
*
for k = 1 to dy
lx = l2 ;* make a copy
lx = delete(lx,1,k) ;*
lx = delete(lx,2,k) ;*
tx = sum(lx<2>) ;* current total with out this item
l3 = '' ;* list of possible substitutions
for j = 1 to dx ;* for each left over trip
if j # l2<1,k> then
if tx + r<2,j> < max then
l3<-1> = j ;* key track of which ones we added
tx += r<2,j>
end
end
next j
if (tx GE tot or dy < dy-1+dcount(l3,@m)) and (tx le max) and l3 # ""
then
r<1,-1> = l2<1,k> ;* put back the ones you drop
r<2,-1> = l2<2,k> ;*
l2 = delete(l2,1,k) ;* drop this item
l2 = delete(l2,2,k)
for j = dcount(l3,@am) to 1 step -1
l2<1,-1> = r<1,l3<j>> ;* add the new item
l2<2,-1> = r<2,l3<j>>
dy += 1
r = delete(r,1,l3<j>) ;* and drop from original list
r = delete(r,2,l3<j>)
dx -= 1
next j
tot = tx
k -= 1
end
next k
*
crt "trip #","dist"
for k = 1 to dy
crt l2<1,k>,l2<2,k>
next k
crt
crt 'total',tot

Item IN:
001 1]2]3]4]5]6]7
002 5]8]12]30]45]6]8

program produces:
trip # dist
2 8
3 12
6 6
7 8

total 34


1,2,3 & 6 fit @ 31 miles
2,3,6 & 7 fit better at 34 miles

Thanks to all for the response on this. You've given me several good things
to go on there.

Mark, thanks for the code too.

Cheers.