Traveling Salesman Problem (TSP)

From CUOSGwiki
Jump to navigationJump to search

Introduction

Ottawa

This is a Free and Open Source Software for Geospatial (FOSS4G) inspired tutorial. It focuses on Network Analysis using a Geographic Resources Analysis Support System (GRASS).

About the Tutorial

This tutorials' main aim is to be clear and understandable. I made every effort to use real data even though this presents many problems. However, it is a reality that data is dirty and software is faliable. This tutorial will be very time consuming to complete, however, you will learn alot along the way and this knowledge will easily transfer to future projects.

In this tutorial you will

  • Install GRASS
  • Download and prepare data
  • Start a GRASS database
  • Build a network and perform analysis on it


Note If the command line is not working and you don’t wish to take the time to troubleshoot this problem I have been given a great work around from my teacher Scott Mitchell. If you do not have GRASS folders set up refer to step named Getting on our way.

  • 1. Launch the OSGeo4W
  • 2. Type grass64 –gui and then hit enter on the keyboard. (notice there is a space between 64 and the dash)
  • 3. You will see the old GRASS version load, so simply click File from the menu bar and click Quit GIS Manager.
  • 4. Now in the command box type g.gui gui=wxpython&

Installation

Install OSGEO Package (30-60mins)

Quick Start

First, you will need to install free geospatial software. I am using GRASS 6.4.2. This can be found through the secure and trusted site of Open Source Geospatial Foundation OSGeo4w is Your Open Source Compass for Windows This package provides a set of open source geospatial software for a Win32 environment. Simply follow the directions from this site: Click Here to go to Download Page

Launch GRASS(1-1.5 hrs)

Launching GRASS Tutorial This tutorial will give you a simple walk through of GRASS allowing for an increased understanding of the software, though it is not necessary to complete it in full.

The Tutorial

GRASS Database (just minutes)

NewLocation.png

1. Prior to starting a GRASS session, create a New Folder named Grassdata and a second named nonGrassData. Start GRASS and once the screen opens, browse to the Grassdata folder. Ensure all file and folder names contain NO spaces, that they are short, and do not begin with numbers.

2. Push the button for Georeferenced files, name the newLocation Ottawa and then browse to the nonGrassData folder. Select the Roadways.shp file. Now click define.

3. Click on both Ottawa and then PERMANENT in each of the grey boxes and then push the ENTER GRASS button. Now we are ready to start working in GRASS.

Import data files and prepare them for processing and analysis

Importing .shp

1. You now have three screens open and running under GRASS. A command line black box, a GRASS GIS Layer Manager, and a Map Display pane. In the Layer Manager window click File | Import Vector Data |Common Import Formats.

2. A GUI window will appear to lead you forward. Choose Roadways.shp from the drop down menu and push Run. If you watch the Layer Manager window it will tell you when all is complete. At the bottom of the window you will have to hit the Map Layers tab as you have been watching the command console tab.

Tabs.png

3. Now the Roadways.shp file is loaded to the Layer Manager window simply toggle it on to view it in the Map Display window.

Next do the same for the wards.shp file.

Importing .csv

This is not as straight forward as the .shp files. You must first open the Addresses.csv file in OpenOffice Calc for editing.

When OpenOffice asks which format the file is in pick the one that has ASCII. Then toggle on: 'separted by commas' and untoggle anything else like periods or spaces ect. In the preview box at the bottom it should now display a more normal spaced looking file.

Calc

Edit all the column headings to simple, short, alphabetical names with no spaces. Delete unnessary columns. Leave the first one, pin number,addressNumber,road names and the x and y coordinate columns. You have six columns now.

The x,y columns need to be formated. You can use the 'Find and Replace' tool. First replace all commas with periods. Then right justify the x and y columns. These are necessary steps.

Save the file as a .csv. OpenOffice might say that there is a problem, just ignore it.

To bring it into GRASS:

Click File|Import vector data|ASCII points/GRASS ASCII vector import [v.in.ascii]

Under the Required Tab:

Browse to the file and choose it. Then back in the GUI, name the output file.

Under the Imput Format Tab:

Change the Field Sparator to a comma ','

Under the Points Tab:

Number of header lines to skip: 1
Number of column used for x: 5
Number of column used for y : 6
Number column used for category: 1
Hit Run

Processing in Grass

Type this in the command line box, it will adjust the region parameters.

G.Region.png
g.region -p vect=Roadways

Next extract the location you specifically wish to focus on. In this case it will be the Somerset ward.

v.extract input=Wards_2010 output=Somerset type=area where=cat=16

Next extract the customers that are within that ward from the larger customer data set.

v.select ainput=Addresses@Try1 atype=point binput=Somerset@Try1 btype=area output=addSomerset 
operator=within

Next extract the Roadways

v.overlay ainput=Roadways@Try1 atype=line binput=Somerset@Try1 output=SomerRoads operator=and

Network Preperation

Type this in the command line box, it will adjust the region parameters.

g.region -p vect=Somerset

Next clean the data

v.clean input=SomerRoads output=SomerRoadCl type=line tool=break,rmdupl

Extract a Start point. When you right click on the addSomerset layer in the Layer Manager window, select to veiw the Attribute table. Scroll to find the exact address you want to use and note its 'cat#.' you will interchange that number with the 444 I have in the code below.

v.extract input=addSomerset output=StartPt type=point where=cat=444

We know that the homes are not located directly on top of the roads so we must calculate and attach them to the network for processing and analysis. First we will create 3 new columns in the attribute tables and then populate them.

v.db.addcol map=addSomerset columns='x double precision,y double precision,dist int'
v.db.addcol map=Start columns='x double precision,y double precision,dist int'
v.to.db map=Start type=point option=coor columns=x,y
v.to.db map=addSomerset type=point option=coor columns=x,y
v.distance from=Start to=SomerRoadCl  to_type=line upload=dist column=dist
v.distance from=addSomerset to=SomerRoadCl  to_type=line upload=dist column=dist

Once we have the distance from all points to the roads,connect all the addresses to the road-network according to a threshold (distance)

v.net input=SomerRoadCl points=Start output=network_S operation=connect thresh=10
v.net input=network_S points=addSomerset output=net_S operation=connect thresh=50

Note: If the program crashes after the last input, as mine did, try repeating the cleaning step (v.clean) on the network_S file prior to running the next step on it. You will notice that my new file is named clNetwork with the output file being TheNetwork.

v.clean input=network_S output=clNetwork type= line tool=break,rmdupl

we can view information about the network

v.category TheNetwork op=report

Report1.png

Network Analysis Examples

Shortest path, no cost

We have a start point, now it is time to choose a destination. Once again choose the 'cat#' of an address point, as you did earlier, using the attribute table from addSomerset.

v.extract input=addSomerset@Try1 output=EndPt type=point where=cat=44592


file:///C:/OSGeo4W/apps/grass/grass-6.4.2/docs/html/v.net.path.html how do i type this?

Data

Conclusion

Contributions to This Tutorial

About This Tutorial

This tutorial was created for GEOM4008 which is part of the Geomatics program at Carleton University, located in Ottawa, Ontario, Canada.

frame

External Links

Here is a list of links that offer additional support and information;

References

Data

Tutorial http://meta.wikimedia.org/wiki/Meta:Sandbox