Routing algorithm for multiple vehicles with multiple drops

Question

I'm looking to find/create a routing algorithm that can be used to manage multiple vans performing deliveries as well as the loads of each of those vans.

Here's a rough specification of what I'm looking for..

• The routes should be calculated in a fast and efficient manner
• 100+ vans / 1000+ packages / 1000+ dropoff points could be processed in one go
• Each van could be a different size and have different weight restrictions
• Each package could be a different size and weight
• The packages should be organised onto the vans in a fair and economical manner, taking into account the routes, weight and size restrictions
• The routes the vans should take should be economical and as short as possible (or a configurable balance between the two)
• Vans could be limited to certain roads (low bridges, width, height and weight restrictions)
• Some packages may be given timeslots for delivery

Has anyone seen this sort of thing before, and if so, any ideas as to what algorithm could be used to do this, or an example of how it could be done? I've seen a few university papers but they're quite old (probably fairly inefficient now) and don't handle the package management - they just presume all the vans and packages are the same size.

Any thoughts would be appreciated!

Rich

Answer 1

pgRouting has a new function implementing a genetic algorithm for the Dial-a-Ride Problem: http://www.pgrouting.org/docs/1.x/darp.html

It's an extension of PostgreSQL/PostGIS and you can build an application with this. It also has functions for shortest path search, etc.

Answer 2

My impression is that this kind of problem routinely comes up in Operations Research, and the standard approach is to use a mixed integer programming solver. Here's an example of encoding a cargo shipping scheduling problem using MIP

Apparently 15 years of recent research in MIP made modern solvers 30,000 times faster than original ones.

If you want to make a solution from scratch, you could start by figuring out what your objective and constraints are, and then use some ideas from integer programming, like approximate branch-and-bound search.

Answer 3

Any algorithm this specific is going to be proprietary and you will probably need to buy something. However, this sounds suspiciously like a problem that could be solved with a genetic algorithm implimentation. Here is some research I found:

http://www.ijimt.org/papers/38-M415.pdf

http://www.springerlink.com/content/w3165x33n24v8610/ (A book that looks like its focused on your problem)

http://www.computer.org/portal/web/csdl/doi/10.1109/ICCIT.2008.407

Just because an algorithm is old, doesn't mean its not efficient.