2

I have the following use case:

A company needs to make winter service at a set of addresses in a city. To be as fast as possible covering all addresses an efficient route calculation is required. However, it shouldn't be one single route between all addresses but a set of routes depending on the number of workers. So if the company has 4 workers the algorithm should find the most efficient SET of 4 routes between all addresses in which no address is covered twice. The start and end of each route is same (being the building of the company) and each route should cover a similar amount of addresses

Is there an algorithm for that particular use case? I am using QGIS 2.18.

Improve this question

1 Answer 1

Reset to default
2

You are just going into the classic Travelling salesman problem (TSP) , so there is not only one algorithm for it, but whole research area.

Working with QGIS, I suggest you to have a look to these two tools:

  1. The pgRouting Project, which has some toold to deal with OpenStreetMap data
  2. The Traveling salesman problem in GRASS
Improve this answer
2
  • But what about having not one but several "salesmen" for a set of addresses? So the question is not "Find THE most efficient route" but "Find the most efficient SET of routes"
    – JoeBe
    Commented Oct 3, 2017 at 8:53
  • Finding the best route is already a good challenge, so do not pretend to go beyond that with one single step. Four "salesmen" is afdordable, but I have no clue about the list of "cities", 10? 100? 1000?. If I were you, I would slipt the "cities" in four groups, get the total time for each "salesman" and then redistributing the cities taken some from the longest travel time salesman and giving them to the shortest travel time saleman. That is assuming you optimal is the minimum of the longest travel time and shortes of the aggregate travel time.
    – Marco
    Commented Oct 3, 2017 at 20:22

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.