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