GIS high density vehicle routing soloution

[lucasmostyn]

Hello

I've been asked to provide an optimized routing soloution for the rubbish and recycling trucks in my district. I do not have access to the Routesmart extension so I've had to work with the Network Analyst 'Route' or 'Vehicle Routing Soloution' options.

So far I've had most success with the 'Route' option by manually creating polygons of the service areas, then intersecting this data to all of the city street corner house numbers, and then using the zones field from my manually created polygons to organise the days collections. This is essentially a table based system of solving the problem.

The problems are really starting to pile up though. My routes are certainly not the most efficient. I've lost all of my truck capacity functions, and although I am capable of routing trucks from the depot to the route, to the recycling centre, back to the route and then onto the depot again, I have no way of doing the drop offs intelligently. That is to say I lost most of the benifit of optimizing a route.

Does anyone have a soloution or any ideas?

p.s I have used the city street corners to try and remove some of the density from the problem. It would be more ideal to be able to use all of the street addresses as i would be able to calculate capacity more effectively...

Any thoughts would be appreciated...

Regards,
Lucas

[JoeBorgione]

The problem you are trying to solve is know as the Chinese Mailman Problem; I can't remember why it's called that, but I do know that at this time, ArcGIS Network Analyst is not able to provide a solution.

You might look at the Traveling Salesman Problem (TSP) as your approach.  You would need to have a point file for each address on your route.

My guess is Jay or Patrick with ESRI will spot this thread on their radar screen and be able to offer better details....

[JaySandhu]

As Joe alluded to in his post, the VRP solver is not the best way to solve high density routing problems as they are really arc routing problems. But if that is all you can use then I can suggest a work flow:

1. Partition your stops into meaningful clusters. You can use Location-Allocation with the maximize capacitated coverage option to get clusters of a  specified capacity. Try to keep the cluster size to what a typical truck may do in one route (few hundred stops) More details here:
http://resources.arcgis.com/en/help/main/10.1/#/Location_allocation_analysis/004700000050000000/


2. Use VRP with the clusters.  Make sure you load in your locations with curb approach set to right-side only. Also set the u-turn policy to intersections or dead ends. You can specify the depot location, dump as well as rules for visiting the dump if the vehicle is full. With VRP you can set additional things such as how much garbage you pick from individual locations, how much time is spent at each location, hourly costs and per mile costs, etc. Do note that there is no guarantee that you will get the best possible route but it will be close and you can tweak the results a bit in the end.

Jay Sandhu

[lucasmostyn]

Thanks for the help guys

I've been working through your suggestions and have a few more questions. I'm finding that i cannot solve for more than 300 points without a crash.

1.Is there any way for me to break the problem into smaller parts, save the routes and then join them together? And if there is how?

2.Jay mentioned that you can adjust the route at the end of the process... how can I do this? it seems that you would need to re-run the solver to change the allocated route?

Thanks again,
Lucas

[JaySandhu]

By adjust I mean you can take an existing VRP layer and for the Orders, set the Assignment rule to be "Preserve route and relative sequence" instead of the default "Override". Now you can update the sequence numbers and re-solve. This way you can take a solved layer and adjust some stops manually.

As far as VRP failing after 300 stops, what version of software are you using and how much memory (RAM) do you have on the machine? What network dataset are you using? It should not crash!

Jay Sandhu

[lucasmostyn]

Running ArcGIS 10 and the machine has 16.0 GB RAM

I'm sure that should be upto the task, I must be making a mistake somewhere. I'm rebuilding my network at the moment with time and distance costs.

How many stops should the VPR be able to handle? approximately?

I have 28,000 dwellings, and im surrently using corner numbers to reduce the density, but that has given me no way to utilise the capacity function...


Regards,
Lucas

[JaySandhu]

Ideally you should place one point along the mid point of an edge with its demand summed from all the dwellings on that street. Or perhaps two points per edge, one on each side. You can create mid points on streets using the GP tool Feature To Point.Note that if you run the Calculate Locations on your point data, it will add the street object id and side of street information to each point. You can then summarize per street how many points are there on each side.

16 GB is more than enough. Normally on a 64 bit OS, only 4 GB can be used by an ArcMap process. Server 10.1 and background 64 bit GP in 10.1 can use more memory.

How big is your network (number of edges)? Is there hierarchy? And is it being used by the VRP layer?

Generally you should be able to solve a few thousand points per layer spread over many routes, but if you have more than a few hundred on a single route then it will take longer to solve.

Jay Sandhu

[lucasmostyn]

Hi Jay

My network has 3185 edges. I've re-run everything but finding the process is stalling at 33%. I've let it run, and although its not crashing, its not completing either. I've tried with 400 points and 2634 points with the same result.

The closest I'm getting is by reducing the capacity to around 50. When I do this the process runs right through... it sticks at 33% for about 1 minute, then at 66% for 15minutes, then completes.

Any ideas would be appreciated... I'm not really sure what to try next
I've already tried limiting the prcess to just MON1 & MON2 but am finding similar problems.... it works when the capacity is at 50, not when its at 500

[ATTACH=CONFIG]25562[/ATTACH]


POSITIVE NOTES.... The routes are now recording total travel time and distance. I am also getting the total culumative cost.

THINGS IVE NOT DONE YET:
The blue polygon that you can hopfully see in the distance will become my routes zone layer once ive figured out how to get the whole process to run through.

Ive also not yet managed to run the calculate locations tool into my point data. I will do this once the routes are running a bit easier

[lucasmostyn]

One more thing that my be relavent is that i've not given a sequence... when working with the network analyst 'route' i found that sequence was basically the key to speed... I imagine this is because Network Analyst must then apply either the Dijiskas or Tabu algorithm to sort the points.

[JaySandhu]

The problem with about 2800 stops and 10 routes should be solveable. What are the max orders on each of the 10 routes?

Jay Sandhu