[Dogstopper]

This week's challenge can have many ways to do it. However, the purpose is to explore Graph theory. Give it a shot to see what you can do.

You run a post office and you have a certain number of destinations that you need to deliver to. However, each one has a certain cost associated with it. For example, if stop A and stop B are close by, it is better to go by A, then B rather than going to A, back to the post office and then to B. See if you can find the optimal route for a list of several delivery locations.

For a tougher challenge, create a list of destinations on a route not just for one truck, but optimize the algorithm to handle any number of trucks and find the fastest/most efficient route for a bunch of delivery trucks.

[macosxnerd101]

My solution using Dijkstra's algorithm:

Spoiler

Already implemented

[moobler]

This is the first challenge I'm posting to, so I don't really know the protocol...so the description's going in spoiler tags and my JAR (including the ugly, mostly uncommented source) is here: FunctionChallenge3.jar.

Spoiler

I made the following assumptions about the problem:

• That the town is setup in such a way that you can go directly to any destination from any other destination (it's a connected graph).
  
• That all streets are two-way streets (an undirected graph).
  
• That every location in the graph must be visited at least once, but that it's not a violation to visit a location multiple times.
  
• That all trucks must start and end at the same point - in my case this is vertex 0.

I started off by generating a random graph. By default it has 1000 locations, with a cost of [1-9] between any two vertices. These values (and others mentioned below) are stored as constants in the Main file for simplicity.

I then use the Floyd-Warshall algorithm to find the least-length path between any two vertices. Those values are used to precompute and cache the full paths from any vertex to any other vertex.

This is where I hit a wall on figuring out how to actually solve the problem. So I went with an old favorite: a simplified Monte Carlo simulation. It's "simplified" in the sense that the data is truly random - there is no on-the-fly tweaking to improve results.

To do this, I took a list of the vertices (not including 0) and shuffled them. Then a fleet of trucks is created (10 by default). Each truck takes the next unvisited location in the randomized list and takes the shortest path from its current location to the destination, marking off all intermediate vertices as "visited". They continue taking turns until all vertices have been visited, then each truck makes one last trip back to the origin. The total distance traveled by all trucks is recorded for comparison. This whole process should be repeated many times to get a statistically significant sample, but I only used 1000 trials for the sake of quick testing.

The lowest total cost and all truck paths are printed out at the end.