topic Re: Simple TSP problem with open area in ArcGIS Network Analyst Questions

Simple TSP problem with open area

DavidChevrier — Thu, 05 Dec 2013 15:51:43 GMT

Hi, I have a feature class with about 400 points that are in the ocean. I'm trying to use the network analyst extension to find the shortest route to travel to each point (as the crow flies more or less). I'm having trouble creating my network dataset. I read in another post that I should make a fishnet feature class (of polylines I'm assuming) of the whole area and use that as the roads. I would have to add a land feature class as a sort of barrier. Then I could solve the route with using the reorder option. None of the tutorials I've read have really shown me how to deal with this situation. Could someone please point me in the correct direction for solving this traveling salesman problem? Thanks

Re: Simple TSP problem with open area

JoeBorgione — Thu, 05 Dec 2013 19:27:32 GMT

Hi, I have a feature class with about 400 points that are in the ocean. I'm trying to use the network analyst extension to find the shortest route to travel to each point (as the crow flies more or less). I'm having trouble creating my network dataset. I read in another post that I should make a fishnet feature class (of polylines I'm assuming) of the whole area and use that as the roads. I would have to add a land feature class as a sort of barrier. Then I could solve the route with using the reorder option. None of the tutorials I've read have really shown me how to deal with this situation. Could someone please point me in the correct direction for solving this traveling salesman problem? Thanks

Don't you hate it when a simple problem isn't really so simple?

As mentioned in that other post, use the Create Network tool to create the basis of your network. The extents should be set to include all of your points. Probably a good idea to use the same projection parameters as your points as well. Once you get your fishnet built, (you'll be the best judge has to how big the cells should be) put them into a feature dataset and create your network. You'll have a length attribute to use as your impedance. I'm not sure what the land feature class barrier idea is for, but it sounds to me like you are ready to go.

Re: Simple TSP problem with open area

DavidChevrier — Thu, 05 Dec 2013 19:39:06 GMT

Thanks, I've been trying something like that, but haven't nailed it yet. The polygon land barrier is needed because these points stretch from Gulf of Maine to the Carolinas and when I did a nearest neighbor route (calculating the closest point, drawing a line to it, then removing it from the list), I would get lines running from Jersey across Cape Cod over land. And unfortunately, our ship can't fly 🙂

Re: Simple TSP problem with open area

JoeBorgione — Fri, 06 Dec 2013 13:12:21 GMT

Thanks, I've been trying something like that, but haven't nailed it yet. The polygon land barrier is needed because these points stretch from Gulf of Maine to the Carolinas and when I did a nearest neighbor route (calculating the closest point, drawing a line to it, then removing it from the list), I would get lines running from Jersey across Cape Cod over land. And unfortunately, our ship can't fly 🙂

Flying ships probably aren't the answer but if Amazon can use drones....

What's not quite nailed yet?

Re: Simple TSP problem with open area

DavidChevrier — Fri, 06 Dec 2013 13:12:57 GMT

I have a couple questions on how to create the network dataset for this challenge as I'm new to the network analyst (but not arcgis). This is what I'm doing now.

-create a new file geodatabase
-create a new polyline fishnet matching the stop points' extent and projection
-create a new feature dataset within the new geodatabase with the same projection as the fishnet
-add fishnet to the new feature dataset
-right click the feature dataset and click new-->network dataset
-take the defaults for 1st two menus

-Now it asks me if I want to model turns in this network. I'm not exactly sure what that means in my context. Would the turns be the paths across the polyline fishnet? What should I put here? If yes, are the turn sources just the default global turns?

-Next menu is connectivity. When I click that and the connectivity groups show up, what options do I take? Do I set the connectivity policy to end point or any vertex? There is another column with a "1" and a check box under it. Do I check that or not?

-On the next menu I select None for elevation as that isn't a factor on the ocean (well, in how I need to solve this problem anyway).

-The next menu asks to specify the attributes for the network dataset. A row with the name Length is there with cost for usage. Do I need to add any parameters or change anything under the evaluators button and menu?

-Next is driving directions. It is defaulted to No, and the Yes option is grayed out, so I'm assuming this is ok.

-Then I build the network when prompted.

Is this the correct way for me to create this open area network data? I'm not sure if that is my problem or how I'm query the route solution is. Any advice is appreciated.
Thanks.

Re: Simple TSP problem with open area

JoeBorgione — Fri, 06 Dec 2013 14:04:48 GMT

-Now it asks me if I want to model turns in this network. I'm not exactly sure what that means in my context. Would the turns be the paths across the polyline fishnet? What should I put here? If yes, are the turn sources just the default global turns?

For this project, you don't need to worry about turns.

Next menu is connectivity. When I click that and the connectivity groups show up, what options do I take? Do I set the connectivity policy to end point or any vertex? There is another column with a "1" and a check box under it. Do I check that or not?

I'm a big fan of of end point only, but I route emergency vehicles to incidents; if I were to use vertex connectivity I might have an ambulance go from a freeway overpass bridge to a surface street; not good. In your case, the fishnet should not have any vertices, just endpoints.

The next menu asks to specify the attributes for the network dataset. A row with the name Length is there with cost for usage. Do I need to add any parameters or change anything under the evaluators button and menu?

For any routing problem you need to minimize some sort value to get the optimum route. The classic TSP not only minimizes some value, but only allows one stop and one stop only at each of your locations. Length is all you have to work with so go with it. In my case, I minimize travel time; I want find the 'closest' unit based on time to get from the station to the incident. Not a TSP in my case, but VRP; vehicle routing problem.

Of course you'll need to add your stops in order to solve your analysis; be sure that they are all within a reasonable search area when you set up the solve in ArcMap. Nothing in your post jumps out at me that says you're doing anything incorrectly.

Maybe Jay or Patrick with ESRI can take a look here and see what's missing...

Re: Simple TSP problem with open area

DavidChevrier — Fri, 06 Dec 2013 14:56:27 GMT

If I use just end points, doesn't that turn each line in a a street with no turns off of it? Meaning if I wanted to travel 100 meters east to a parallel street and I was on a north/south street, I would have to travel all the way to the end and turn twice? I don't think I am explaining that well, but I thought each overlap in this case would be a 4 way intersection so that diagonal lines could be traveled upon.

I created the data with your help and if it is correct, then how I solve the problem is the issue. What I do is add the newly built network dataset to my map when prompted and make sure it is selected in the drop down in the network analyst toolbar. Then (in the toolbar) I then click network analyst-->new route. Then I click the create network location tool and add new points which are entered in as stops. When I click the solve button I get this message every time (and I've tried different locations in the network with different numbers of points and it is always the same):

Warning: No route from location "Graphic Pick 1" to location "Graphic Pick 2".
Error: No solution found.

Re: Simple TSP problem with open area

JoeBorgione — Fri, 06 Dec 2013 16:43:21 GMT

If I use just end points, doesn't that turn each line in a a street with no turns off of it? Meaning if I wanted to travel 100 meters east to a parallel street and I was on a north/south street, I would have to travel all the way to the end and turn twice? I don't think I am explaining that well, but I thought each overlap in this case would be a 4 way intersection so that diagonal lines could be traveled upon.

I created the data with your help and if it is correct, then how I solve the problem is the issue. What I do is add the newly built network dataset to my map when prompted and make sure it is selected in the drop down in the network analyst toolbar. Then (in the toolbar) I then click network analyst-->new route. Then I click the create network location tool and add new points which are entered in as stops. When I click the solve button I get this message every time (and I've tried different locations in the network with different numbers of points and it is always the same):

Warning: No route from location "Graphic Pick 1" to location "Graphic Pick 2".
Error: No solution found.

The concept of turns is you can penalize a route with turns; for example, a left turn may take a little longer than a right turn in a street network. Or a left turn at 5:00 rush hour is heavily penalized. As mentioned, turns are an issue for me, but not in your case.

So what you are doing now is running a simple point to point route, right? You're basically testing the connectivity of your fishnet-network, and it sounds like if it's not going to work with two manually entered points, its not going to work with 400. Any chance you can post a portion of your network here? I only have a 9.3 install here at home so a shapefile would be fine. I think you are just missing something in your workflow that I'm not catching.

Re: Simple TSP problem with open area

JoeBorgione — Fri, 06 Dec 2013 17:05:51 GMT

I think the problem is the fishnet itself. I just created one and it does not create intersections where the columns and rows 'intersect' I tried to integrate mine and that didn't do it. I gotta run out for a couple hours but I'll see if I can remember what needs to be done...

Re: Simple TSP problem with open area

DavidChevrier — Fri, 06 Dec 2013 17:25:12 GMT

I repeat the procedure with a shapefile (which still failed to work). The zipped folder of data with the network dataset and grid data is too large for me to attach unfortunately. They have a 2mb limit on zip files. Could you try to make a grid and see if you get any errors?

Re: Simple TSP problem with open area

DavidChevrier — Fri, 06 Dec 2013 17:59:25 GMT

Thanks for looking into this!

Re: Simple TSP problem with open area

DavidChevrier — Fri, 06 Dec 2013 19:51:56 GMT

I think I got it to work. I had to create the grid as a polygon then use the polygon to line tool making sure the "identify and store polygon neighboring information" is checked.

Thanks for all your help!

Re: Simple TSP problem with open area

JoeBorgione — Fri, 06 Dec 2013 20:17:47 GMT

I think I got it to work. I had to create the grid as a polygon then use the polygon to line tool making sure the "identify and store polygon neighboring information" is checked.

Thanks for all your help!

I looked at the online help, and at 10.0 and 10.1 it gives you the option of lines (that intersect) or polygons. At 9.3.1 creating a fishnet is useless to create intersecting lines. Glad you got it to work.

Re: Simple TSP problem with open area

JoeBorgione — Tue, 10 Dec 2013 14:40:52 GMT

I think I got it to work. I had to create the grid as a polygon then use the polygon to line tool making sure the "identify and store polygon neighboring information" is checked.

Thanks for all your help!

Just a follow up; I knew there was a tool that will split lines where interections should be. It's the planerize tool on the topology toolbar. Somebody mentioned it in a recent thread.

http://help.arcgis.com/en/arcgisdesktop/10.0/help/index.html#//001t0000008t000000.htm