Interface DeliverySchedulingAlgorithm is implemented
by algorithms that solve the Delivery Scheduling problem.
In the general problem, an operator of delivery k trucks has merchandise to
ship from a warehouse to a group of n clients. The clients are
distributed among the trucks so that the trucks may serve the clients
in parallel. Since all trucks are assumed to leave the warehouse at the
the same time, the traversal route of each truck and the unloading time
at each client for that truck determine a truck's return time to the
warehouse. The goal is to minimize the return time of the last truck
to return.
Algorithm| Method Summary | |
int[][] |
computePaths(edu.gwu.geometry.Pointd[] locations,
edu.gwu.geometry.Pointd start,
double[] timeNeeded,
int numVehicles,
double speed)
Method computePaths should compute the assignment
of clients to trucks and, for every truck, the order in which each client is
served by the truck. |
| Methods inherited from interface edu.gwu.algtest.Algorithm |
getName, setPropertyExtractor |
| Method Detail |
public int[][] computePaths(edu.gwu.geometry.Pointd[] locations,
edu.gwu.geometry.Pointd start,
double[] timeNeeded,
int numVehicles,
double speed)
computePaths should compute the assignment
of clients to trucks and, for every truck, the order in which each client is
served by the truck.
locations - a Pointd[] value. This is the list of locations,
each of which is an instance of Pointd[]. The Euclidean
distance between two points is used to determine the time needed to travel
between the two points.start - a Pointd value. This is the location of the warehouse.timeNeeded - a double[] value. For each location, the time
needed for unloading at that location. Thus, timeNeeded[3] is
the unloading time required at the fourth location.numVehicles - an int value. The number of trucks.speed - a double value. The speed of each truck, common to all
trucks. By dividing the distance by speed, you obtain the time taken.
int[][] value. The return value is an assignment of
of locations to trucks. Thus, consider the following use:
int[][] assignment = alg.computePaths (locations, start, timeNeeded, numVehicles, speed);Here,
assignment[3][5] represents the sixth client assigned to the fourth
truck. That is, truck 3 has clients assignment[3][0] (first client),
assignment[3][1] (2nd client), etc;
and assignment[3][5] is truck 3's sixth client.