From: israel@math.ubc.ca (Robert Israel)
Newsgroups: sci.math
Subject: Re: scheduling N delivery people
Date: 5 Jan 1997 03:24:46 GMT

In article <5alb3t$7ou@lyra.csx.cam.ac.uk>, wb104@bioc.cam.ac.uk (Wayne Boucher) writes:
|> Consider N delivery people.  They each have several (scheduled) deliveries to
|> make each day.  Suppose they are at location z1(i), i = 1, ..., N, at time T
|> and the locations of the time (T+1) deliveries are at z2(i), i = 1, ..., N.
|> The problem is to minimise
|>         D(p) = (sum over i = 1 to N) distance(z1(i), z2(p(i))
|> over all permutations p (with distance taken in the plane, say).  This can be
|> generalised by replacing the distance function with a more general weighting
|> function (hence taking account of actual travel times, say).
|> 
|> Is this a known problem?  Are there any decent algorithms?

As stated (with each person making one delivery), it is an "assignment problem".  
This has been studied a lot, and there are very good, polynomial-time algorithms.
If you have several delivery times, but the locations of the N deliveries at each
time T are fixed, it is just a sequence of assignment problems.  However, if
the times of the deliveries can vary, it becomes much harder: with N=1
it becomes a "travelling salesman problem".

Robert Israel                            israel@math.ubc.ca
Department of Mathematics             (604) 822-3629
University of British Columbia            fax 822-6074
Vancouver, BC, Canada V6T 1Y4