1

How do I create a routing with multiple stops?

Currently I have uploaded on PostGIS the nodes and edges of the road graph but I want the stops to match the housenumbers. The ideal work would be to considerate the time windows of each stop and the capacity of the vehicle (once reached the max capacity, the vehicle must return to a point 0, resume the route and then complete it).

Which is the best algorithm to solve this problem?

Here is a small area of housenumbers and nodes (orange points) on QGIS

enter image description here

Improve this question

2 Answers 2

Reset to default
2

The problem is called VRPTW: Vehicle Routing Problem with Time Windows. Google that. The best algorithms are most likely far from free.

Improve this answer
4
  • Can I use the VRPTW in a garbage collection context? once the vehicle has reached the maximum capacity, he needs to go back to depot and then resume the route?
    – Matt Marston
    Commented Dec 9, 2020 at 12:17
  • Basically, yes.
    – Uffe Kousgaard
    Commented Dec 9, 2020 at 16:10
  • Ok but, is it correct that the VRPTW doesn't give the option to go back to the depot and restock (in the case of garbage collection unload the truck)? I've just read that pgr_pickdeliver for the one depot problem is better if I need to go back to point 0 and then resume the route.
    – Matt Marston
    Commented Dec 10, 2020 at 12:59
  • No, it is generally not correct. But in the end it depends upon an actual implementation, VRPTW is just the generic name of the problem you are trying to solve.
    – Uffe Kousgaard
    Commented Dec 10, 2020 at 16:10
1

You could have a look at the set of functions offered by pgRouting in the field of VRP http://docs.pgrouting.org/latest/en/VRP-category.html?highlight=vrp. Some additional information can be found here http://osgeo-org.1560.x6.nabble.com/pgrouting-users-Introduction-to-VRP-with-time-windows-Work-done-in-Gsoc-2014-td5197304.html and here https://github.com/pgRouting/pgrouting/wiki/VRP-Algorithms.

Improve this answer

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.