12

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?

Improve this question
1
  • I happen to have a similar need like yours. I am operating an NPO NEMT (Non-Emergency Medical Transportation) business. we need to transport patients to their appointments with time windows for pickups or deliveries. Most requests are received in advance, others are on the spot. DARP seems to be a good algorithm. Are you in need of DARP solver for the same reason? Nick
    – Nick Bazzi
    Commented Jul 1, 2015 at 15:05

3 Answers 3

Reset to default
10

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.

Improve this answer
1
  • 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
    Commented Jan 21, 2011 at 11:51
2

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

Improve this answer
2
  • See also some announcement here: openvrp.com/blog/darp-algorithm-in-pgrouting
    – dkastl
    Commented Jan 21, 2011 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
    Commented Jan 21, 2011 at 11:48
1

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.

Improve this answer
4
  • 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
    Commented Jan 21, 2011 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
    Commented Jan 21, 2011 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
    Commented Jan 26, 2011 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 [email protected] if you want to discuss it further.
    – Uffe Kousgaard
    Commented Feb 8, 2011 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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