Charity logistics - programming project

[Katie_1]

I work for a small food charity that delivers hot meals to people in London. We are looking for a program that will make our logistics easier. We need a route planner that can take a list of postcodes and design routes that work with variable requirements such as the route should be no longer than one hour and no more than 12 meals per route.

We don't think a programme currently exists and wonder whether it might be a final year project or other university project. Or maybe it is a project for a graduate wanting to add to their CV? I'm afraid we don't have a development budget but we can write excellent references!

[rubberman]

This is a variant of the "Traveling Salesman Problem". There are well-known algorithms and programs that deal with it. The problem is not perfectly solvable without searching ALL possible routes, but good solutions are possible with reasonable use of computer time. Here is a link to the wikipedia article about the subject: http://en.wikipedia.org/wiki/Travelling_salesman_problem

[phorce]

I think, this can be completed in Polynormal Time, if I'm honest. If something, for example Euclidean TSP it would still be NP-Hard but not NP-complete.

Hope this helps :)

[jwenting]

there exist many such programs. What do you think UPS uses, FedEx, DHL, Royal Mail, most every trucking company, to generate routes?

And there are many ways to solve it, usually by encoding the map into a graph and letting loose a pathfinding algorithm.
Of course that's a crude approach, as there's a lot of stuff to factor in to get an optimal solution, and you'll need more software to calculate the loadout of your delivery vehicles and optimise that, then find a way to coordinate between the two so you don't end up with routes that look optimal but leave you with overloaded vehicles.