topic GIS high density vehicle routing soloution in ArcGIS Network Analyst Questions

GIS high density vehicle routing soloution

lucasmostyn — Wed, 19 Jun 2013 20:29:24 GMT

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

Re: GIS high density vehicle routing soloution

JoeBorgione — Thu, 20 Jun 2013 11:03:58 GMT

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....

Re: GIS high density vehicle routing soloution

JaySandhu — Fri, 21 Jun 2013 15:00:17 GMT

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

Re: GIS high density vehicle routing soloution

lucasmostyn — Tue, 25 Jun 2013 20:01:51 GMT

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

Re: GIS high density vehicle routing soloution

JaySandhu — Tue, 25 Jun 2013 22:17:21 GMT

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

Re: GIS high density vehicle routing soloution

lucasmostyn — Tue, 25 Jun 2013 22:33:29 GMT

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

Re: GIS high density vehicle routing soloution

JaySandhu — Tue, 25 Jun 2013 22:41:55 GMT

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

Re: GIS high density vehicle routing soloution

lucasmostyn — Thu, 27 Jun 2013 20:43:24 GMT

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

Re: GIS high density vehicle routing soloution

lucasmostyn — Thu, 27 Jun 2013 20:51:01 GMT

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.

Re: GIS high density vehicle routing soloution

JaySandhu — Fri, 28 Jun 2013 17:39:19 GMT

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

Re: GIS high density vehicle routing soloution

lucasmostyn — Wed, 03 Jul 2013 19:47:23 GMT

Max orders are 600

Re: GIS high density vehicle routing soloution

JaySandhu — Wed, 03 Jul 2013 22:10:35 GMT

600 stops should be doable. Have you tried some other solver such as load them as stops in a route layer and solve. Do you get a path? If yes, you could turn on the find best order option and run again (this is similar to vrp) and see if it can solve. Other than that I cannot say what is going on preventing its completion.

Jay Sandhu

Re: GIS high density vehicle routing soloution

lucasmostyn — Wed, 03 Jul 2013 22:45:41 GMT

Hi Jay

Yes I have tried loading them into the the 'Route' solver, and yes it does generate a route. However, I cannot get an optimized route this way. If i check the box to optimize the route order then the process freezes when over 400 points are used...

If I do not check the optimize route box then I can solve over 10,000 points.... (but this is only presenting a route between the points in the attribute table without sorting them into a good sequence)

I think this process would work if I could find a way to organise the points into the correct sequence before running the 'Route' solver...

Re: GIS high density vehicle routing soloution

JaySandhu — Thu, 04 Jul 2013 15:30:30 GMT

When it "freezes", what is the memory status for the ArcMap process? How much RAM has it consumed?

Also, can you send me your points (export to shape file and zip OR save the route or vrp layer and zip and send) and I can run them locally to see if I can get a solution? jsandhu at esri.com

Jay Sandhu

Re: GIS high density vehicle routing soloution

KarelKus — Wed, 04 Feb 2015 10:20:57 GMT

Hello,

is there a solution for this problem, I am dealing with similar thing - Micro routing for recyclables collection, and I also have to use Network Analyst.

I have two zones for collection 816 and 802 (nodes) bins.

After clicking solve the algorithm runs well. For 816 nodes it takes an hour, but after that time I get a sort of solution. I have outputs in route properties (TotalOrderServiceTime, TotalTravelTime...), but there is no route on the map. I can see only the sequence of orders.

In addition two error appears:

Error: "Failure while working with internal route problem instance"

Error: "A column was specified that does not exist."

I think I did sometning wrong with my network dataset or attributes but still cannot find out what it is.

Any suggestions?

Anyway the sequence of orders I can see is not the optimal one because some nodes are skipped and the truck returrns for them later.

1. Is this caused by that the solver is not designed for such a task?

2. I started experimenting and this anomalous sequencing occures on smaller sets too. Now It seems to me that it depens on the number of nodes per route, but also on the exact area in the network and set of nodes that is chosen. Sometimes it helps to use a seedpoint sometimes not.

Is there some exact threshold how many nodes the solver should be capable to do without this sort of error?

I would need 255 nodes for each of my zones to solve it by placing one point along the mid point of an edge.