Question

Garage collection routes

deanhowell
Badge +9

Is it possible to use FME to calculate the optimal route that covers all roads in a network?

 

The scenario is that the garbage truck needs to ensure that all houses have their garbage collected in the most optimal way?

 

Has anyone done something like this - similar to a travelling sales person problem but they are going to every property?

2 replies

virtualcitymatt
Rank
Userlevel 4
Badge +26

This is pretty challenging problem, would be really interested to see what you come up with.

Several questions that come to my mind:

 

  • Is it assumed that the garbage trucks will never get full during their route and have to return to empty?
  • Can/does the truck ever need to leave the network to access other parts of the network (end of a small street which is connected to a bigger street that lies outside the network)?
  • Are there any streets where the truck needs to go up and down the street to cover all the homes? or can it just go down once and service homes on both sides of the street?

 

I guess you'd need to look into graph theory to figure out what the particular problem you need to solve is called - it probably has a name and there may even be existing algorithms you can use (maybe this? - https://en.wikipedia.org/wiki/Eulerian_path).

Given that the length of the network will likely always be the same you probably just need to find one path that doesn't go over the same line twice (assuming that path exists). To optimise it further would be to have the start and end be as close to the depot as possible.

 

 

deanhowell
Badge +9

This is pretty challenging problem, would be really interested to see what you come up with.

Several questions that come to my mind:

 

  • Is it assumed that the garbage trucks will never get full during their route and have to return to empty?
  • Can/does the truck ever need to leave the network to access other parts of the network (end of a small street which is connected to a bigger street that lies outside the network)?
  • Are there any streets where the truck needs to go up and down the street to cover all the homes? or can it just go down once and service homes on both sides of the street?

 

I guess you'd need to look into graph theory to figure out what the particular problem you need to solve is called - it probably has a name and there may even be existing algorithms you can use (maybe this? - https://en.wikipedia.org/wiki/Eulerian_path).

Given that the length of the network will likely always be the same you probably just need to find one path that doesn't go over the same line twice (assuming that path exists). To optimise it further would be to have the start and end be as close to the depot as possible.

 

 

Thanks @virtualcitymatt​ That is a great reference. I didn't know such a theory existed and will be a good test for FME. Cheers Dean

Reply


Community Stats

28,724
Posts
109,517
Replies
36,563
Members
Terms & ConditionsCookie settings
A product of
Safe Software respectfully acknowledges that we live, learn and work on the traditional and unceded territories of the Kwantlen, Katzie, and Semiahmoo First Nations.