Welcome dear students we are in the lecture 14, we have already covered the basics of GISand GIS operations; how data gets stored, how we store the attributes? So, now, we are intothe applications we have covered the basics of GIS. So, today we shall look into the networkanalysis in GIS.
So, the topics that we are going to cover today are we are going to introduce what is anetwork, though we had already seen or I mean how a network can be coded in GIS, how thedata can be stored? We would look into network connectivity concepts, we would see the
different types of summaries of network characteristics, it is complexities, connectivitys. So,how to summarize a network, then to identify the shortest path, if we have a network toidentify the shortest path.
Now, you come across the application of this shortest path in your Google I mean routefinder, say whenever you have or you are travelling in a city and you give your origin anddestination it would find the shortest path, either the shortest time distance path or you canfind out the shortest cause distance path in a network.
So, one such algorithm which I mean works on finding out the shortest path is Dijkstra’salgorithm, wherein you can find the shortest path in a network. Another shortest path problemI mean wherein a person would have to visit n number of nodes, in a given number, in a givennetwork can be solved using a traveling salesman’s approach. So, these are the concepts thatwe are going to touch upon today.
So, let us see what is a network. So, a network is a aggregation of links and nodes and it isvery easy to code the data for links put the data for nodes and you can create attributes for thelinks as well as the nodes. So, in arc GIS we generally for links we call it as arcs and each arcwould have it is vertices. So, the order in which you are at is it digitizing would show thedirection of the arc. So, otherwise we can also give some indication for directions in a networkand we will revisit this while we are discussing further.
Nodes, now the nodes are the endpoint of arcs and they are the points where in the differentarcs are connected to each other. So, we can denote a real city or the network of a city I meanthat is connected through roads, rail, or other form of transportation network. And, we canestablish this network in GIS using arcs and nodes, we can represent such networks in GISusing arcs and nodes.
Now, we can also do a characterization of the network we can do an accessibility analysis, ifsome of the areas are unserved by network, we can identify that and we can do acharacterization of the complexity of the network in a given urban area.
Now, we can also find out the shortest paths between the start and the end point. Thesealgorithms of finding shortest path or visiting n number of nodes, in the most optimal way canbe used, in the determination of the shortest corridor, in case of emergency evacuation toroute and schedule vehicles. So, these are some of the application areas wherein we can usenetworks.
Now, let us see how the networks are connected and how do we represent it? We representthe network connectedness of the network using a connectivity matrix. So, this would be adiagonally symmetric matrix, because I mean the node numbers would be connected to each
other. So, I mean this you would have the different nodes as vertical columns and as rows andyou would use numbers, probably an impedance value or the distance to travel or the cost tofind out the connectivity in the network.
Now, this is basically a square matrix and it would contain the arc level as the column and asrow headings. So, these matrix indicates that, if they are connected by arc those nodes the Imean the intersection of these 2 columns and rows would have a value of 1 and 0 otherwise, incase they are not connected. Now, this connectivity between the different nodes can be ofdifferent order.
So, let us discuss what is the first order connectivity? So, these are a nodes which are directlyconnected to each other by arcs. So, such nodes or such connectivity is known as first orderconnectivity. Now, we have another term which is known as second order connectivity wherein the nodes are connected by 2 arcs with a further node in between them. So, you would haveI mean 2 nodes connected to each other, through some other node why are some other node.
So, we call a second order of connectivity. Now, as we had already said that this connectivitymatrix, wherein we had said that it is a square matrix.
(Refer Slide Time: 06:53)
So, it has it is a symmetric matrix and it is a square matrix. Now, the summary of the networkcharacteristics can be given and we have a range of measures to characterize networks. Thefirst among them is known as the gamma index, which gives the complexity of a network andwe have alpha index, which gives us the degree of connectedness, we had talked about thefirst order connectivity, we had talked about the second order connectivity. So, the alphaindex it gives us the degree of connectedness.
So, a better connected network would be 1 where these values of gamma and alpha providesummary of the network connectivity’s and where these values are larger. So, there is a minorI mean edit in this particular slide, for g please read gamma and for a please read it as alpha, itis some typographical issue because of some fonts in the computer. So, while you are goingthrough this lecture please read g as gamma and a as alpha.
Now, these networks are generally represented through graph theory and there we have agraph which is known as planar graph, which represents networks wherein there are nointersecting arcs or edges or links. As you may call it I mean in different GIS terminologies orbooks you may come across different terms, but all of them mean the same.
Now, we have these planar graphs, which has n number of node and the maximum possiblenumber of links that it can have is 3 into n minus 2 number of links. Now, there could benon-planar graphs also which are 3 dimensional. For example, we can have a transportationnetwork varying the maximum link is given by n into n minus 1 divided by 2.
(Refer Slide Time: 09:11)
Now, the measure of connectivity is given by a measure a measure c, which is known asnumber of circuits that exist within a given network. Now, every circuit has a start node andthat is the same as the n node. And, therefore, it is a closed loop it comprises a closed loop.
So, if we have a circuit which is minimally connected I mean network which is minimallyconnected, in that case we would not have any circuits ok.
So, the number of circuits can be calculated by subtracting the number of arcs, that is requiredfor minimally connecting a network from the observed number of arcs in a network. So, youcan calculate the number of circuits in a network. So, this is how it is calculated, where l is thenumber of arcs and n is the number of nodes. So, I mean you can calculate the number ofcircuits by I mean differencing l minus n plus 1.
Now, you can see that least cost path analysis is used for I mean the least accumulative costpath is found out. I mean we can use this least cost path analysis to explore the least cost pathin a given network. So, in this we require a source raster, we would have a cost raster, we
would have a cost distance measure and we would have an algorithm, which would process allthese different inputs into an output of the shortest cost path.
So, in this particular graph, in this particular image, you can see that this is a raster whereinthe centroids are basically the nodes and these centroids are connected through links. So, thislink which goes horizontally or vertically is known as lateral link. And, the link which joins thecentroids of diagonally placed elements is known as the diagonal link. Now, in case of sourceraster you are the only the source raster would and the destination raster would have cellvalues. And, the other cell values will not have any other data.
So, you can identify in a raster giving the location of those grid points, where your source isand where your destination is where you use is your start point and where is your end point.Now, the source cell is an end point it could be an origin or destination as we have talkedabout. So, we can calculate the accumulated cost path we shall see an example how we cancalculate the accumulated cost path. I mean this cost path is calculated to source cell or to theclosest source cell. And, we can find out the distances if 2 or more source cell are presentspresent, we can find out the alternate your path from the source to the I mean destination.
Now, we can also find out the cost and the cost implications of traversing between 2 nodes isregistered as a cost raster. So, in this analysis we are talking about a raster data model, but wecan also do a similar analysis using a vector data model. So, in this case for the cost we have acost raster. So, the cost raster is either there are a cost to travel across different nodes or itcould also be an impedance or a penalty cost of or impedance to move through each cell.
So, it would if you want to move through the different routes in a network it might offerdifferent kind of resistance. So, we shall see, what are the different types of impedances orresistance offered by networks? So, there are three characteristics to a cost raster. So, the costfor each cell is a summation of the different types of cost. For example, construction cost oroperation cost, or potential cost of a kind of an environmental impact that might happen,
because of pollution or for some other reason. So, you can find out the potential cost such asenvironmental cost.
So, like you are traveling from a location to a destination. So, the construction of the roadwould entail some money there would be some operational expenditure because you have tomaintain the road. So, that will also I mean you would incur some cost and there would bepotential cost in terms of pollution or other impacts so, that needs to that can be accounted.So, we can sum up each of this cost and find out what is the traversal cost from each node tothe other node.
So, we can either work the actual cost or we can also work out the relative cost, which arebasically ranked values and involves a blanket of cost factors. It may be ranging different Imean factors which could be I mean used for working out the relative cost. So, we can rankthe relative cost for relative cost we can rank the values between say 1 to 5, 5 being thehighest cost value or it could be in a different scale all together. So, we can rank this values,we can find out the relative cost.
So, what we can do is we can standardize the cost. If we know the I mean aggregated cost thesum of cost over different links like we had talked about construction cost, operation cost,maintenance cost or environmental cost. So, we can aggregate all those costs over all the linksand we can standardize that, we can take the summation of that and we can divide the cost oftraversing between 2 nodes divided by the total cost of traversing across each of those nodes.
So, that will give us the relative cost. So, it is generally used when you are trying to I meancode intangible values, values that you cannot measure. Like say, suppose aesthetics or I meansome kind of intangible factors, like your cultural resources or say suppose you have a wildlifehabitat. So, I mean we tend to work the relative cost. Since, it is very difficult to quantifythese kind of intangible factors.
Now, the cost factors can be weighted by relative importance of each factors. So, we can alsohave a mechanism that we do apportion some kind of weights based on the relative importanceof the different factors that we have been talking about. So, probably I mean safeguarding the
wildlife habitat could be the prime objective. So, there you may apportion a higher weightagecompared to probably aesthetics or some other cost. So, you can have different kind ofweights for the different factors. And, the cost raster is compiled by evaluating and summingup all these different cost factors.
So, we make raster’s for each of this cost factor and the way we generate the composite costraster is we multiply each of this cost factor by it is weight. And then what we do is we sumup all the individual raster’s to give you the final cost raster. So, I mean we can work out thelocal sum which is the cost I mean summed up cost to traverse each of the cells from eitherlaterally or diagonally as we had seen.
So, it is based on the node link cell representation. A node represents a cell, and a link and itas we have seen is either lateral or it is diagonal and it connects node to it is adjacent cell. The
lateral link connects cells to it is immediate neighbors and the diagonal link connects thecorner elements, or the corner neighbors from a given point. Now, this distance if we aretraversing in the lateral direction would have to travel 1 cell distance and if we are travelingdiagonally we have to travel 1.414 or which is equivalent to root 2.
I mean the centroid between 2 cells. So, that can be worked out I mean you can calculate thatand you can work out the centroid between 2 cells. So, in this case in this particular equationyou can see that we have product of I mean average of the C 1 and C 2, where C 1 is the costvalue at cell i and C j sorry C i and C i and C j divided by 2 where C j is the cost value at theneighboring cell. So, we can work out either the lateral I mean distance to the link or we canfind out the diagonal distance.
So, we you can see this particular cost raster. So, we have assumed a cost raster. So, in thiscase this matrix has 4 by 4 elements. So, you can see this top right 4 elements are zoomed inand I mean it has shown by this particular enlarged representation. So, the distance betweenthe laterally linked cells are summation of the values of the particular link distance.
So, suppose this value is 2 and this value is 1. So, the lateral your cost of traversing these 2nodes, the centroid of this pixel to the centroid of this pixel would be 2 plus 1 that is 3 dividedby 2 which is 1.5, but when we are traversing the diagonal link say suppose we are traversingthis diagonal link between 5 and 1. So, what we do is we sum up 1 plus 5, which works out to6 divided by 2 is 3 into 1.414, which comes to a value of 1 4.2.
So, for this diagonal link you can see this value is 4.2. So, similarly this diagonal link has acost value of 2.1 and similarly the lateral links all have different values. So, you know nowhow to calculate the cost distance of the lateral or diagonal link.
So, we can do same thing in this particular matrix. So, first we had said we had the sourceraster. So, the source raster we said the source and the destination would have values and theother elements would have null values. So, you can see that in this particular your matrix orthe raster representation.
So, you have the cost raster that is the cost of traversing across your lateral links or throughyour diagonal links. So, you can work out the court cost raster and then as we had seen wehad calculated the cost for this particular sector. I mean these 4 pixels; we have done this forall the pixels now. For all the elements in this given raster we have calculated the lateral coststraversing the lateral in a lateral fashion and in a diagonal fashion.
So, from there you can work out if this is your origin and destination, you can work out thedistance to traverse to the next cell in a cumulative fashion. So, you can find out the route
which would I mean have the minimal cost in this given network ok. So, you can eithertraverse like this. So, if you traverse from here to this you have a value of 6.7. I mean then thevalue of 4 is added to this. So, it would have a value of 10.7, but if you traverse along this lineprobably that will give you the least cost path.
Now, we have different types of outputs of cost distance measure operations. So, the firstoutput could be a least accumulative cost raster and the next output is the direction raster, it isshowing which shows the direction of the least cost path for each of the cell. And, the thirdoutput could be a allocation raster showing the assignment of cells to the source cell on basisof the least cost distance measure.
Now, the fourth type of I mean output, that we can have from cause distance measure is theshortest path raster, which shows the least cost path from each cell to a source cell. So, from
our earlier example, we mean we have this, I mean route the minimal route if we are travelingfrom c to a or c to b, we can traverse this route and for the minimal distance, cost distance.
Now, the least cost distance is obtained after each path is evaluated. Now, we can use aDijkstra’s algorithm and algorithm given by Dijkstra and it is an iterative algorithm, which Imean we have a method and we basically iterate it many times to come to the optimum. So,the steps involved include activating the cells adjacent to the source and we compute the costto these cells. The second step in this method is that the cell having the lowest or the least costdistance is chosen from the neighboring nodes, I mean if you have active cell list the least costdistance is chosen and it is distance is value is assigned to the output raster.
Now, the in the next step what we do is we try to find out the cells adjacent to the chosen cellthey are activated and then we added to the active cell list, and the lowest cost cell would be
chosen and it is neighboring cells are then activated. So, whenever we are reactivating a cell, acell is accessible to source and what we is we I mean try to identify alternate routes, and Imean try to pick out the least cost path, and we accumulate the cost, and we re compute theweightages of the alternate possible routes and the least cost path is retained.
So, then what we do is after we have worked out the least cost path it is again assigned to thereactivated cell. So, this process is an iterative one and it would continue till your all the cellsin your output raster would be assigned with the latest accumulative cost to the source cell.
Now, let us see this particular network we have this first diagram on your left wherein youhave the age values or the link you can say the link impedances. So, which are weights? So, traversing from B to A the cost is 3 and from traversing from your D to A we have the cost as5. So, your A 2 B is linked and traversing from A to B would have a cost of 3. So, what wedo is we based on the directionalities, we try to identify the cost as well as the direction andwe find out the I mean aggregated cost or the accumulative cost.
So, we do this for the entire network and we can see that which is the shortest possible routebetween say link D and link F.
Now, talking about another method of transportation problem when we are to visit saymultiple nodes in a given network, we have an algorithm which is known or travelingsalesman’s algorithm. So, it is a route routing problem wherein I mean the salesman wouldstart from 1 node and he would traverse through all the nodes that are selected in a givennetwork, but he has to return to the original node.
So, our objective of implementing this traveling salesman’s problem is that we want to identifythe route, varying the there would be a minimum total impedance value or minimum total costvalue. Now, it is a heuristic method this traveling salesman’s problems are solution is aheuristic method and we begin the initial search using a random tool and runs this process runsa series of locally optimal solution. And, we swap the stops and try to find out if there is areduction in the cumulative impedance.
Now, this iterative process would end, when there is no improvement there is no change in thevalue of your cumulative impedance, by swapping the stops I mean in a in our earlier step wehave been swapping the stops. So, whenever you see that between 2 successive iterationsthere is no improvement in terms of the impedance value or the cost value, we can stop theiteration and we can create a tool with a minimum or a near minimum cumulative impedance, Imean always it may not give you the best solution.
So, one of the methods which gives you the best possible results is a Tabu search algorithmfor I mean finding out connectivity between n number of nodes. The time window constraintcan also be added that, you want to complete this node within some amount of time or withina time delay certain amount of time delay, minimum amount of time delay, you can alsoapportion time window constraint.
So, then what it will do; it will do is you it will try to pick out the links, which varying thetravel time are the least. So, that it would be able to complete this entire tour or travel withinthat stipulated trying frame.
Now, we have a system of linear features with appropriate attributes for flow of objects andthese linear features or networks could be a bicycle track, or a network stream of a river ordrainage course it could be a railway line, or some public transit corridor, or a road. And, wecan create a topology wherein the lines would meet at the intersections and we the lines shouldnot have any gaps. Otherwise, the errors would show up in your analysis, because connectivityis a very important thing in this particular network.
So, whenever you are trying to digitize your networks for doing a network analysis you haveto see that, there are no overshoots or undershoots while you are digitizing. So, you can alsoapportion direction, some of the link could be a one way street. So, you can apportion the turnimpedance as well because you know, if you want to travel a turn take a right turn or a left
turn, you would have to I mean negotiate a lot of vehicles through I mean in that during thatprocess of turning or if you are taken the u turn.
So, that will delay your travel and it will impede your movement. So, I mean we can have animpedance not only for the links, but we can also have an impedance for the nodes as well. So,these data would be aggregated and we create a real world street networks. So, thesegeometries again are defined by two points two end points.
So, we can I mean find out the link impedance in a urban in an urban context and we can findout the cost of traversing a link. So, it could be a simple measure like finding out the length, Imean accounting for this cost in terms of the physical length, which is a reliable measure, Imean you can measure that through GPS or your software would generate those points, if you
are digitizing lines on a geo referenced image say a satellite high resolution image or a toposheet.
So, you would be able to find out the exact distances between these nodes. So, this lengthcould be a measure of reliable measure of cost. I mean we can have the speed on a link and itcould be used to calculate the link impedance from the length as well as the speed on the link.So, there could be different types of link travel time. So, I mean we can find out the directionaltravel time, I mean your if you travel 2 nodes in different direction whether the travel time issame or different it could be different in most of the cases.
So, we can enter this data I mean the directional travel time separately. So, we have when weare having the topology of the networks, we have those columns like from node and to node.So, we can create two columns like from and to and to and from. So, we can identify thenodes the origin node and the destination node and we can have a value, directional travel timevalue and from the other end that is from the 2 node to the from node, we can have anothertravel time value.
So, this travel time would depend on the of the day or the week or the season or in differentlocations. So, I mean we can include this travel time and I mean in a different context whereinwe may have I mean a one way corridor or a two way street. So, we can attribute this traveltime. So, when we are doing some network analysis like we had talked about the travelingsalesman’s, I mean your algorithm or we were talking about Dijkstra’s algorithm.
So, there we not only include your link impedance, but we also include the term impedance indoing the calculations. So, you can see that we can assess the cost of a link using a distancefunction, which would give you the link impedance, we can find out the commuting cost, wecan find out the queue length, we can find out the delay at intersection probably due to signals,which will give us the turn impedance. So, all these can be accounted and aggregated into acost function for accessing a particular link.
So, a recapitulation of what we had covered in this particular lecture we had talked aboutnetworks. We had talked about network connectivity, we had seen some indicators forsummarizing network characteristics, we have identified the shortest paths using a Dijkstra’salgorithm. And, then we had seen a traveling salesman’s problem and how it can beimplemented and it can be applied in an urban context.
So, most of the software’s like qgis, arcinfo and other software’s have these algorithms builtin, and you can devise your own I mean application based on either the shortest path or usinga traveling salesman’s approach.
So, thank you.
Log in to save your progress and obtain a certificate in Alison’s free GIS and Spatial Interpolation online course
Sign up to save your progress and obtain a certificate in Alison’s free GIS and Spatial Interpolation online course
Please enter you email address and we will mail you a link to reset your password.