I am trying to create an optimized route plan for a townships garbage truck fleet for garbage pickup. I have tried using ESRI's Network Analyst within ArcMap but have found the analysis to be to complex and the results returned are not as desired. There are approximately 2000 stops within each zone within the township with 3 trucks per zone. Recently I have come across the PGRouting SQL extension and would like to know if this type of project would be to complex for PGRouting to run? Can PGRouting handle the large volume of pickups?
found the analysis to be to complex
You are talking about an optimization problem that is an NP-hard problem. They are complex problems including TSP
and the results returned are not as desired.
Normally what you get as "solutions" on NP-hard problems algorithms are approximations. Some can be "close to reality" and some might look "far from reality", in your case maybe by visual inspection it came out to be far from reality.
Visual inspection, does not necessarily give you a correct result, because, there are constraints that might not be included on the problem definition and those can add more complexity to the problem, and even if the "routes" looks fine if those are not taken into consideration then those additional constraints will make the solution invalid.
Maybe the constraints are well defined, but not taken into consideration on the algorithm, because it would make it a specialized algorithm.
- City A - trucks pick container on the left side
- City B - employees pick & take the garbage bags to the truck.
So, if an algorithm exists for problem for City B, it would not look as a solution for city A
Suppose the route looks ok for city B... So the algorithm is used for city A, but when the solution says "pick container", it happens that some of them are being picked at the right side of the truck which makes the solution invalid on City A.
Does it matter if the trucks can pick from the right side, from the left side?, or does not matter, because people pick up the bags and put them in the truck? The trucks fleet contains a mixture, some pick up from the left, some from the right some don't care?
Can the truck do U turns?, Speed limits are an issue?, are the trucks of equal capacity? can they make multiple trips to the dump? are the schedules of the drivers taken into consideration? are times used to fuel gas also taken into consideration?
You might like to see this presentation: http://talks.vicky.georepublic.info/2016/garbageCollection.html
PG_Routing's TSP needs distance matrix as one of inputs... Since counting this matrix (only) will take about 23 days (assuming 2000 starting points, 2000 destinations and performance of 2 distances per second) I don't think anyone tested it with more than 100 points...
IMO of course - correct me if I'm wrong