5

We have been approached by our Public Works Department to try and optimize their routing for street sign inspections to improve efficiency and productivity. We are unsure of the best way to go about creating the routes. All of the signs are in a database, there are roughly 55,000 signs that need to be inspected. All trucks would leave from the same location and return to the same location each day. We are using ArcGIS 10.1.

Responding to comments below

The tool suggested is the solution we'd like to use, however, it seems to max out at 1000 stops. The stops are only a couple minutes long so it is possible to do a large number of stops per day, spread out over 4 or 5 trucks. So we are trying to figure out the best way to divide our county up into smaller chunks to be able to meet the 1000 stop threshold.

  • 1
    Do you have a license for the Network Analyst Extension? – Kirk Kuykendall Sep 5 '13 at 18:53
  • yes. We have also looked at clustering but these signs are everywhere. Our county is 1,663 Square Miles. Obviously the inspections are spread out over time. – Craig Sep 5 '13 at 19:02
  • 5
    Did you consider treating this as a Vehicle Routing problem? – Kirk Kuykendall Sep 5 '13 at 19:25
  • I do treat it as such, however, the tool maxes out at 1000 stops. So we are trying to find a work around. – Craig Sep 6 '13 at 14:06
  • It seems to me like a cross between a travelling salesman and a garbage collection problem. I would call your neighboring counties, or what they do up in Michigan and see. AASHTO or TRB must have some documentation on "inspecting mechanisms for traffic signs". I know for us we used to collect day time asset data and night time retroreflectivity data – dassouki Sep 9 '13 at 16:18
3
+50

We are working on a very similar problem at the moment and have been using a different approach.

We loaded all of our data into a PostgisS enabled PostgresQL database and used the data to construct a node/vertice network which is then snapped to the road network. We then installed pgRouting and used the pgr_tsp function to create our recommended route. The steps are basically:-

-create topology using the pgr_createTopology function
-create a distance matrix for the network using pgr_dijkstra
-run pgr_tsp function to calculate the route
-map topology back to the road network

Our routes are several hundred nodes but I see no reason why it should fail with 1000's, it just might take longer. If you need the routes back into ArcGis then export the geometries from PostGis.

1

Don't get stuck in finding the absolute optimal planning. The mathematical problem is a hard nut to crack. You'll probably be happy with a 95-99% good solution to start with, from my personal experience as a operations research consultant.

You could start off with clustering locations into several groups, each group representing a day of work. You may want to look into k-means clustering:

http://en.wikipedia.org/wiki/K-means_clustering

After clustering, for each day of work optimize the route separately, putting the locations in the best order to visit.

Btw, I work at a RouteXL, a multi-stop route optimizer.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.