Given a number of n customers with coordinates (xi, yi) (i = 1, ..., n),
find a set of r routes, starting from a depot located at (x0, y0), and
visiting all the customers such that :
-- First objective : the length of the longest route is minimum,
-- Second objective (after having minimized the first one) : the sum of
the delivery hours of each customer (or average delivery time) is minimum.
Particularities :
1) The distances are MANHATTAN distances i.e. the distance between
customer i and j is |xi-xj| + |yi-yj|
2) The routes do not return to the depot.
This problem was proposed by the Dutch journal "De Telegraaf" for servicing
as soon as possible a set of 120 customer located in Manhattan.
The route are performed by 4 bikers.
There was many prizes of fl.5000.- for those who find the best solutions
before October 22. 1996.
In the professionnal category, the winner was Marco Wiering from IDSIA.
Format of the data file :
n, r
0, x0, y0
1, x1, y1,
.....
n, xn, yn