Adding Routes to Vehicle Routing Problem

1582
3
07-19-2011 09:11 AM
Highlighted
Occasional Contributor
I am trying to solve a VRP where 24 trucks service 106,928 service points in a gas district in 21 cycle days. I don't see an option in the orders input fields to specify number of days, so my idea was to create 504 separate routes (24 trucks x 21 days = 504 routes). I created the 24 trucks for one cycle day, and then copied and pasted them 21 times to make the routes.

The problem is the solver will not run unless each route has a unique name, and I was wondering if there was a way to automatically generate routes using specified criteria while creating unique names so that I don't have to go through each route renaming it Cycle_1_Truck_1, Cycle_1_Truck_2, etc....Thanks.
Tags (2)
Reply
0 Kudos
3 Replies
Highlighted
Esri Regular Contributor
You can open the routes attribute table and use the Field Calculator to make up some expression like:
"Cycle_" & [ObjectID] to get unique names. You can add more vb script there to make more compliated expressions.

BTW, the scale of your problem suggests to me that you are trying to some sort of "meter reading". VRP is not designed for such applications. But you can give it a try by making sure that when you load in the service order points have their curb approach property set to "No_U-turn" and set the solver properties to make U-Turns only at dead ends. Even then, you will have to partition the number of service orders into some smaller set as you will run out of memory when the VRP solver starts by by computing a matrix of travel times between all orders before it can start to optimize the route sequence.

Jay Sandhu
Reply
0 Kudos
Highlighted
Occasional Contributor
OK I used the field calculator to make unique route names. However you were right, the solver fails out with an out of memory error. We also tried running it on my colleagues workstation with Windows 7 but ended up with the same error (it did run for substantially longer though).

Is there any possible workaround to this problem that does not involve splitting up the orders and thus reducing time-savings?
Reply
0 Kudos
Highlighted
Esri Regular Contributor
VRP is designed to route a few thousand orders for delivery tomorrow or over a certain horizon.

What I am reading into your application is that it is a high density meter reading problem. Traditionally this is solved using the Chinese Postman Problem Solver not the Vehicle Routing Problem Solver as the goal is to visit EACH edge of the network. Since we do not provide a Chinese Postman Problem solver it is not feasible to solve it with VRP as is. So you can either aggregate the data or reduce the data by making regions in your data to solve at a time. One way to aggregate the data is to take any edge with multiple stops and reduce it to one or two stops on that edge. For example if one edge had 20 houses, then use the GP tool FeatureToPoint and it will place one point at the midpoint of the selected edges. Now you can load that point into the VRP order layer with curb property set to No U-Turn. That way when VRP solves it will have visited each edge and you can post-process the data with your original locations to get the best sequence to visit. (Hint: output routes have measures for linear referencing, so use a GP tool Locate Features Along Route to get the sequence)

If the above does not work for you then I suggesst you take a look at one of our business partners that provides a solution to meter reading: RouteSmart.com

Regards,
Jay Sandhu