Assignment 4

Consider the following "delivery scheduling" problem. A stationery supply service supplies many clients each day with stationery. Each day, several trucks leave the stationer's warehouse with supplies and return after deliveries are complete. Each truck is assigned a subset of the clients and their merchandise is loaded onto the truck. A truck makes its rounds as efficiently as possible by choosing the order of clients carefully. Note that because each client has different needs, the time spent unloading at client sites can vary. The total time taken by a truck is the time from leaving the warehouse to returning after all the clients on its list are served. This includes driving and unloading time. The "delivery scheduling" problem described above is actually a problem structure common to many problems, including various kinds of delivery scheduling (postal service, trash pickup, inter-state trucking).

In this assignment, you will implement (at least) two algorithms for a version of the delivery scheduling problem. This version simplifies the problem somewhat by removing the complexity of finding paths in street maps. The input to this problem is the following:

A set of n "locations" or clients. The locations are specified as (x,y) coordinates and are given to your algorithm as instances of the class Pointd (see link to documentation below). With each location is associated the time needed at that location to unload the delivery.
A set of k trucks. Each truck is assumed to be identical. As we will see, it is possible to set the speed of the trucks via the properties file.

The goal of the algorithm is to "divvy" up the locations among the trucks so that each client location is served by only one truck. A second goal is to order the clients for each truck. Then the truck will travel from location to location in that order, thereby completely defining the time required from start to finish. The simplification of the general problem comes from allowing trucks to travel directly (in a straight line) from one location to another. This approximation might be reasonable for inter-state commerce or a "snow-sled" delivery service in the Alaskan wilderness. Whatever the application, it certainly helps reduce the routing complexity while still leaving the problem interesting.

The ultimate objective is to minimize the total time required to complete all deliveries assuming that all trucks leave at the same time and work in parallel. This amounts to minimizing the worst time among the trucks, since the total time is determined by the last truck to return.

An example might help clarify. First, we'll consider an example without loading times.

In the example above, the warehouse is located in the center of the square and there are 8 client locations on the periphery. The (x,y) coordinates of some of the locations are shown. Suppose we have two trucks and suppose Algorithm A assigns locations {0, 2, 4, 6} to one truck and locations {1, 3, 5, 7} to the other. Suppose for simplicity, the trucks move at unit speed. Then, the first truck moves a distance of 10.84 (approximately) while the second truck moves a distance of about 6.24. At unit speed, this amounts to 10.84 hours and 6.24 hours respectively. Thus, the total time required is 10.84 hours (the larger of the two).

Now consider Algorithm B that assigns locations {0, 1, 2, 3} to one truck and locations {4, 5, 6, 7} to the other:

Then, each truck moves a distance of 5.414 (approximately), resulting in a total time of 5.414 hours. This is obviously a better solution.

Now, in the actual problems, there will be loading times. For example, consider these two possible solutions:

In the left figure, the total load time for the red truck is 20, whereas the load time needed for the blue truck is 2. Here, the second solution requires longer driving, but the total time is shorter because the "load time", which dominates travel time, has been balanced between the trucks.

In your assignment, you will implement two algorithms. One will be called SimpleGreedy and the other will be called MyAlgorithm. The SimpleGreedy algorithm is just to help you get started; as you will see, it should be fairly easy to improve on its results. The second algorithm is up to you; we will run your second algorithm in a class-wide competition, as explained below. You are welcome to submit more than two algorithms. Simply name them MyAlgorithm2, MyAlgorithm3 etc. (Don't go overboard - we don't want to test too many).

For this assignment:

Both algorithms will need to implement the DeliverySchedulingAlgorithm interface.
The input is the following:
- A set of points (representing the client locations);
- The location of the warehouse (the starting point);
- The time required for unloading at each client;
- The number of trucks;
- The speed of each truck.
The output is an array of arrays. The first dimension is the number of trucks. The second dimension can vary. Here's what our test code does:
```
     int[][] assignment = alg.computePaths (locations, start, timeNeeded, numVehicles, speed);
   
```
Now suppose the algorithm assigned locations {0, 3, 5, 11} to truck #4 (the fifth truck). Then, assignment[4][0] == 0, assignment[4][1] == 3, assignment[4][2] == 5 and assignment[4][3] == 11. Next, the travel distance is computed by traversing from the start location to location 0, then from there to location 3, then to location 4, then to location 11 and back to the start location. Thus, it is your job to allocate locations to trucks and create an order for them. There might be a big difference between traversing in the order {0, 3, 5, 11} versus the order {11, 5, 0, 3}.
An algorithm may choose not to assign any clients to a particular truck by making assignment[i] = null for that truck (truck i in this case).
The test environment checks that an assignment is valid: all client locations need to be served, and no client is served by more than one truck.
The SimpleGreedy algorithm works as follows:
- First, compute the bounding box containing all the locations. This is the smallest rectangle containing all the points.
- Divide the box into k equal horizontal slabs, where k is the number of trucks.
- The points that fall in the i-th slab are assigned to truck i.
- To find the order of points for each truck, first find the the closest point in the slab to the start location. That gives you the first point in the order. Then, the second point is the the closest point to the first point among the remaining points. Then, the third is the closest remaining point to the second, and so on.
Use this properties file to run your algorithm in the test environment.
The javadoc's relevant to this assignment are:
Algorithm
DeliverySchedulingAlgorithm
Pointd
Note: You will need to import edu.gwu.geometry.* in addition to the usual imports to be able to use the class Pointd.
Please download the latest version of the test environment.
The Competition. we will run three competitions for this problem:
1. Best quality: the algorithm that finds the best solutions (among test data that we will generate).
2. Fastest: the algorithm that produces good solutions the fastest (it should produce solutions that are better than the SimpleGreedy algorithm to qualify in this competition).
3. Bang-for-the-buck: the algorithm whose ratio of of solution quality to running time is best.
Some points will be awarded based on ranking in the competitions.
Finally, the above delivery scheduling problem is NP-Complete. Can you argue why it is so?

Submission:

Follow the usual submission instructions carefully.