Fall 2014, David Matuszek

- Introduce you to STM (Software Transactional Memory)

You are in charge of a small fleet of delivery vehicles. Each day there are deliveries to make to a number of locations. Your task: Given the locations that must be visited, produce routes for each vehicle that minimizes the total distance traveled.

A location is represented by a pair of integers,

. To keep things relatively simple, the distance between two locations

and_{1} y_{1}]

will be the Manhattan distance, that is, _{2} y_{2}]

._{1} - x_{2}) + abs(y_{1} - y_{2})

Each vehicle will start at a central location,

, make deliveries to some number of locations, and return to the central location. The problem is to decide which locations each vehicle will visit, and the order in which to visit those locations, so as to minimize the total distance traveled by all the vehicles.

This is an NP-complete problem, that is, a perfect solution requires exponential time--time which you will not have. Therefore, the assignment is to start with one or more (probably extremely bad) route assignments, and by trial and error, gradually improve the route assignments until you have something reasonable.

I will add one additional constraint to this problem, namely, that every vehicle should visit the same number of locations, plus or minus one (because the number of locations may not be a multiple of the number of vehicles).

You should use STM to keep track of the following data: For each vehicle, which locations it visits, and in which order; and the total distance traveled by all vehicles. Each time a better solution is found, use a transaction to replace the previous best known solution, and print the new best distance, along with which vehicle found it.

You should have several agents each working on the complete problem, vying with one another to produce better and better solutions. You can use additional "helper" agents if that seems desirable or useful.

Here's what I would do; you might prefer a different approach.

I would assign the locations to the vehicles, possibly randomly, possibly a little more intelligently. Then I would find a best route through those locations for each vehicle--this is the Traveling Salesman problem, which itself is NP-hard, but I'll keep the number of locations per vehicle fairly small.

After that I would randomly swap a pair of locations between two vehicles, find the best route for each, and see if that is an improvement; if not, put the locations back where they were in the respective routes.

At any point my agents might take the current best plan, rather than the one they have been working to improve, and use that as a new starting point.

This approach depends on trying a very large number of possible route assignments. You are welcome to use heuristics to do a more intelligent job, but begin by "doing the simplest thing that could possibly work" and, if you have time and inclination, improving on that solution.

While your program should accept any inputs, you can expect numbers in these ranges:

- Four to eight vehicles.
- Four to eight locations per vehicle (hence, 16 to 64 locations to visit).
- Four to eight agents working on the main problem. You can set this number yourself, but it should be easy to modify.
`x-y`

coordinates between -100 and 100.

Your program doesn't have to produce great solutions, but they shouldn't be awful.

The program should use shared memory to keep track of the best solution, run multiple agents, and the agents should make proper use of transactions to update that shared memory.

Limit the program in some way so that it takes no longer than about half a minute on your own computer; that way it should not take too long when we run it.