Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

I have 100 destinations and 5 vehicles and I need to code a solution that efficiently routes the vehicles to each destination, so each destination is visited by 1 of the vehicles. Some of these destinations could have time windows to be visited during as well.

I'm using PostgreSQL and PostGIS, and was looking to use pgrouting but I'm not sure it's suitable for multiple vehicles - from my limited knowledge of Dijkstra etc I think they're designed for a single vehicle.

Any thoughts on whether pgrouting can solve this problem, and if so, any code examples? If not, are there any open-source alternatives that can do it?

share|improve this question

4 Answers 4

up vote 10 down vote accepted

pgRouting has a function called DARP (Dial-a-Ride Problem) solver:

The Dial-a-Ride Problem (DARP) solver tries to minimize transportation cost while satisfying customer service level constraints (time windows violation, waiting and travelling times) and fleet constraints (number of cars and capacity, as well as depot location).

More on DARP and pgRouting:

To use this new function, you need to install darp branch of pgRouting.


Answers to this question on stackexchange might provide additional info: Routing algorithm for multiple vehicles with multiple drops.

share|improve this answer
    
I initially saw the DARP algorithm but brushed over it as I didn't realise it could be used for couriers. Looks like that'll do the job nicely! It's a pity the documentation page doesn't have any examples of usage though, might be a case of hunting through the sourcecode to see how it works. –  RichW Jan 21 '11 at 11:51

pgRouting has a new function to solve DARP: http://www.pgrouting.org/docs/1.x/darp.html

share|improve this answer
    
See also some announcement here: openvrp.com/blog/darp-algorithm-in-pgrouting –  dkastl Jan 21 '11 at 2:46
    
Thanks Daniel, that's an excellent function you've built there. I didn't realise it could be used for delivery purposes but it definitely looks feasible. Thanks! –  RichW Jan 21 '11 at 11:48

While ESRI ArcLogistics clearly does not fit your particular needs of using PostGIS or open source, for others who may not have the programming skills or the time to implement their own solutions, it is a good off-the-shelf, paid-for extension to ArcGIS that is designed to accomplish the tasks you described.

They are currently also offering a 30-day free trial if you want to test it out.

share|improve this answer
    
I went down to ESRI HQ last week to discuss this software for them, but it doesn't appear to meet our needs (needs to run on a server and is also quite expensive). Excellent piece of kit though! –  RichW Jan 21 '11 at 11:50
    
Our FleetEngine product runs as a server with a SOAP interface. 100 destinations, 5 vehicles and time-windows is definetely within the capabilities. It is very close to being production ready, contact me for a test license. It ain't open source or free, but on the other hand not as expensive as ArcLogistics. –  Uffe Kousgaard Jan 21 '11 at 12:19
1  
Hi Uffe, can it take into account vehicle restrictions (weight and dimensions) and sort the packages onto the vehicles accordingly? Also, does it work in the UK and use road history data to work out speeds etc? –  RichW Jan 26 '11 at 11:12
    
Yes to all your questions. It uses simple additons of weight / volumes. It can't do 3D packing too, that would be too much to hope for. Full support for street networks in any country too, but you need to supply the street network. Unfortunately I didn't see the reply any sooner, I thought this discussion had ended. Ping me at uffe@routeware.dk if you want to discuss it further. –  Uffe Kousgaard Feb 8 '11 at 15:43

I've compiled and installed DARP branch. Is there any data example to test it?. I've used some data based on document instructions http://www.pgrouting.org/docs/1.x/darp.html but no results return. - What's the difference between depot_id and depot_point_is? - In distance query i don't understand fields from_order and to_order. - If i add a request for going from point A to point B, is necesary to add in distances table the cost of going from point B to point A?. - The field values in distances query, what time units should be?, minutes?, seconds?, miliseconds?. - Where do darp.c and darp_solver.c leave log messages?. I know that maybe darp branch is a RC version, but please could you help me with this?.

share|improve this answer
2  
The way the site works you should ask this as a new question. –  Andy W Feb 23 '11 at 13:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.