Module 5 - Special Topics in GIS - Vehicle Routing Problems

16 Truck Routes with Orders for Southern Florida

This week's lab in Special Topics was a continuation of Network Analysis.  In these exercises, we worked on establishing routes for vans delivering patients to their doctor appointments, and for trucks delivering goods to supermarkets.

In the map on the left, we can see the routes for 16 trucks from the depot or warehouse, to various stores, as they deliver their orders over the course of a day.   Initially, we restricted the trucks to delivering only within their own zones, and excluded any other trucks from delivering to zones not assigned to them. There are 14 zones, and one truck was assigned exclusively to each zone in that scenario (14 trucks total).
This resulted in 6 orders being missed in the day's deliveries, and 10 additional orders for which the established time schedule was violated.


We then developed a new scenario (pictured here), in which we added two additional trucks from the fleet of 22 to be assigned to help with deliveries to the zones.  In this case, no orders were missed, and only one order was late.  In the figure above, blue dots are order deliveries that were delivered successfully, within their time constraints, and the red square is the solitary order that was delivered outside the time window.  The numbers in parentheses after each truck number are the quantities of orders assigned for each route.

Difference in revenue from the first solution (14 trucks) to the second solution (16 trucks):
$33,625 (16) - $32,000 (14) = $1,625 more was earned with new, 16-truck solution.
Difference in cost from first solution to second solution:
16,919.63(16) - $15,067.20 (14) = $1,852.43 more cost was
incurred with new, 16-truck solution.
So, the company had a net cost increase of about $227, but that resulted
in better customer service (6 orders filled that otherwise would not have been),
 which will be better for the company in the long run.

Module 5a - Remote Sensing - Introduction to ERDAS Imagine and Digital Data 1

Landcover Imagery from Washington State
Manipulated in ERDAS Imagine and exported to ArcMap

This week in Remote Sensing lab we had an introduction to ERDAS Imagine, which is software designed to manipulate and adjust the qualities of remote sensing imagery.  The various spectral bands from the imagery can be enhanced to make certain features easier to see: for example, the near infrared band is reflected off of vegetation preferentially, so an image enhancing this wavelength can be very usefule in studies of forest and agricultural land.

We are only getting started with learning how to use ERDAS, but it should be a very useful tool to extract the utmost value from remotely sensed data.

Module 4- Special Topics in GIS -Network Building

Routes with no restrictions (left) and accounting for traffic (right)

This week's lab was super-challenging.  The Network Analyst software of ArcMap is quite sophisticated, and so it's sometimes hard to understand how it works and get the results you're looking for.

In our case, we made a route to go among 19 stops, with no restricted turns.  A new network dataset is created within a geodatabase, and feature dataset, with street, traffic and restricted turn feature classes associated with it.  The traffic data is based on historical traffic patterns, which are actually models of how traffic ebbs and flows at different speeds over the course of a day, on different days of the week.  Rather than attaching all the traffic data to the specific streets, each street is referred to the particular pattern that is best suited to it.  A general traffic situation can be created for the streets, but live traffic data can also be accessed and applied to the streets on a minute-by-minute basis.

As can be seen from the two figures above, the route will change depending on whether or not we have no restrictions in the form of restricted turns or traffic.  The route at left is with no restrictions, and the route on the right takes into account traffic patterns.  By changing the path in a couple of places, indicated by the arrows, the travel time can be optimized.  Total time went from 105 minutes in the non-restricted turn case, to 107 minutes once traffic effects were added and the route was adjusted by the Network Analyst.

Module 4 - Remote Sensing - Accuracy Assessment of Land Use and Land Cover Classification

Map of Accuracy Assessment of Land Use and Land Cover,
Pascagoula, Mississippi, based on Google Street View

This week we did a virtual "Ground Truth" accuracy assessment of our Land Use and Land Cover interpretation and classification from last week.

Here is the map from last week, with 30 sample points to be checked against Google Earth Street View.  The points were more-or-less randomly scattered across the area, however, none are located in the southwest quarter of the map, because this area is covered with large areas of water and wetlands that are not visible from Street View.  A few sample points are located along the coast, in areas that could be seen from the shore-side roads.

The procedure was to find the location of each sample point on Google Maps, satellite view, then go into Street View and ascertain what is actually at that spot, and if it follows the classification that was given earlier for that spot.
In my map, 11 of the 30 sample locations returned incorrect classifications, giving an accuracy of 63.3%.  Most of the errors resulted from the misinterpretation of an actual Commercial and Services area (class 12) as a Commercial and Industrial Complex area (class 15).  Also, some areas that I earlier classified as Forested Wetlands (61) are probably Mixed Forest Land (43); in other words, forested areas on dry land.

Residential areas, lakes, rivers and roads are very easy to classify from aerial imagery, because they are very distinctive in geometry, details, and textures.  However, a couple of spots that looked like residential houses turned out to be commercial locations, and vice-versa.

Module 3- Special Topics in GIS - Determining Quality of Road Networks: Completeness

Map depicting relative completeness of two road networks

In this week's lab, we explored a method of comparing the completeness of two road networks covering the same area, in this case, Jackson County, Oregon.  The two networks to be compared are the U.S. Census Bureau's TIGER lines for 2000, and the Street Center Lines network from the Jackson County GIS Department.

First, we can simply compare the total length of all streets from the two networks, within the county.

A more rigorous method can show the pattern of relative completeness between the two networks. In this exercise, we overlaid the two road networks with a simple grid.  Then, by using ArcMap 10.2 Intersect and Summary Statistics tools, we were able to create a total length of road segments for each separate grid cell,  This procedure was carried out for both networks. Then, for each individual cell, the percent difference in road segment length between the two networks was calculated.  The following calculation was carried out on each grid:

(Total segment length of Street Centerlines) - (Total segment length of TIGER lines) 
                                     Total segment length of Street Centerlines                                     X 100

The result is negative percentage values in grid cells with larger TIGER line segment lengths, and positive values for cells in which Street Center Lines have a larger sum of segments.

Based on this method of analysis, TIGER Lines is more complete than the Street Center Lines, with a more cells with longer segment length.

The completeness results are depicted in the map above.  Blue cells are those in which TIGER Lines are more complete, and green cells are those in which Street Center Lines are more complete. (Darker tones represent higher percentage of difference.) The pale cells are those in which the lengths are very similar, within 3%, plus or minus.

Module 3 - Remote Sensing - Land Use and Land Cover Classification

Map of USGS Level II Land Use and Land Cover,
 Pascagoula, Mississippi

In this week's Remote Sensing lab, we began to gain experience in interpreting land cover and land use from aerial photographs, as well as digitizing land use and land cover features onto a map.  The learning curve was steep for me at the beginning, because I had to wade through some inefficient methods and repair a lot of errors before I could really start to make progress.  All in all, this exercise was very educational!

This map has been classified and digitized according to USGS Level II of land use and land cover classes (Level I is very general, while level IV, the highest, is most detailed). The main challenge at Level II is learning to generalize, while still identifying the major subclasses. Features that can be discerned from the entire extent of the map must be identified. At Level I, there would only be 4 classes on this map: Urban, Forest Land, Water and Wetland.  At Level II, we divide up those very broad classes somewhat, as shown by the map legend directly to the left; for example, the Urban Level I class includes Residential, Commercial and Services, Industrial, and Transportation at Level II.

Module 2 - Special Topics in GIS - Positional Accuracy of Road Networks

Map produced by the City of Albuquerque,  with sample intersections
placed for this accuracy assessment.

This week in Special Topics in GIS, we continued to practice making calculations of error between a sample dataset and a reference dataset considered to be more accurate.

Last week, we calculated error on two existing sets of data that we were given as part of our lab materials.  This week, we generated our own datasets from maps of the city of Albuquerque, New Mexico, then calculated error.





The figure above is a simple street map for the first dataset to be tested . The dark dots represent samples of street intersections taken from a map created by the City of Albuquerque. This City map is considered to be quite accurate, according to our lab materials this week.  We also examined the accuracy of another street network from StreetMap USA, over which we placed sample location points on the same street intersections as for the City map.    In order to assess the accuracy of these two datasets, we needed an independent reference dataset with corresponding street intersection points, which has been deemed to be much more accurate than those datasets we want to test.
For this "truer" reference, we digitized a new set of points on the centers of the sample street intersections, based on digital orthophoto quarterquads (DOQQ's) covering the city.

For this accuracy assessment, we followed the methods developed for the National Standard for Spatial Data Accuracy (NSSDA).  This document and others based on it line out a 7-step process for assessing and documenting the positional accuracy of a data set.  A very well-written summary of this process, with several case-studies, was produced by the Minnesota Planning and Land Management Information Center and included in our lab readings, and this was my main guide in this project. 

In summary, here are the seven steps for assessing the positional accuracy of the dataset in question:

1.  See if you need to test horizontal, vertical, or both accuracy in your dataset.
        (For this assignment, we assessed only horizontal accuracy.)
2. Select a set of test or sample points from the dataset that you're testing. 
       (We tested two datasets, one from the City of Albuquerque map, and the other from the
       StreetMaps USA map of the same area.)    
       For this step, select at least 20 points, make sure that at least 20% of them are in each 
       quadrant of your study area, and that they are at a distance from each other of at least 
      10% of the diameter of your study area.
3. Find another, independent dataset that represents the locations of those same points, 
    but with higher spatial accuracy.
      For this, you might have to digitize the locations from an orthophoto, or measure them in the field       with GPS, or the points might already exist in another more accurate dataset.  
      (Our reference data was digitized from the DOQQ's.) 
4. Tabulate the x and y coordinates for both datasets.
5. Calculate positional accuracy statistics, either horizontal or vertical.
       In this step, calculate the distances for both X and Y between each pair of points (test and
       reference), square those differences, then sum the squares.  
      This is the first part of the Pythagorean equation, but in this case, do NOT find    
      the square root of the sum.  Instead, calculate the average  of the sums of x and y squares
      for all of the pairs of points.   Then, take the square root of that average.
      This gives you the average error distance between all of your test and reference points.    
      This is called the Root Mean Square Error (RMSE).  
      From this statistic, we now want to calculate the error distance at which 95% of our 
      tested data points fall from their corresponding reference points.  
     To do that, simply multiply the RMSE by 1.7308 for horizontal error, and 1.9600 for 
     vertical error (these factors are calculated from the mathematical characteristics 
     of a Gaussian or bell-shaped distribution curve.) 
     These products are known as the NSSDA statistics and should be reported in the 
     final accuracy assessment.
6. Write a standardized accuracy statement in the NSSDA format.  
     (My statements for these assessments are shown below.  
7.  Include that accuracy report in the metadata of the dataset you are testing.


Here are formal my NSSDA accuracy statements for the two tested datasets in Albuquerque, NM.

a. City of Albuquerque road network, Horizontal Positional Accuracy:

Using the National Standard for Spatial Data Accuracy, the dataset tested 16.8 feet horizontal accuracy at 95% confidence level.

b. StreetMaps road network, Horizontal Positional Accuracy:

Using the National Standard for Spatial Data Accuracy, the dataset tested 341.5 feet horizontal accuracy at 95% confidence level.


As we can see from these statements, the City of Albuquerque dataset is much more accurate than the StreetMaps USA dataset.  We can say (based on this sample test at least), that 95% of the City of Albuquerque-mapped street intersections lie within 16.8 feet (horizontally) of their true positions based on the DOQQ's.  However, we can only say for the StreetMaps USA map that  95% of the samples tested lie within 341.5 feet (horizontally) of their true locations.  This disparity was easily seen from cursory visual comparison of the street network datasets and the orthophotos.  The City mapped streets were always very close to their counterparts in the DOQQ's, but those of StreetMaps varied considerably from being fairly close (generally in the center of the map) to hundreds of feet away, and skewed at large angles (generally at the corners and edges of the map).

Module 2 - Remote Sensing - Visual Interpretation

In the second week of Photo Interpretation and Remote Sensing, we began looking more closely and analytically at aerial photos.  By making use of some systematic and discriminating methods, it's possible to learn much more from air photos than we can with a more casual and cursory approach.

The top map to the left shows examples of different degrees of tone, or brightness along a gray-scale, and texture, in features in an aerial photo.  Our tone scale has five classes: very light, light, medium, dark and very dark.  It's important to use a scale like this in order to maintain consistency as we describe and identify objects on the ground.

The bottom map illustrates four different elements of image interpretation.  Different objects on the ground have a variety of characteristics...some, such as cars and houses, are most easily recognized by their shape or size, others, such as a parking lot, by a distinctive pattern, and others, such as light poles, more by the shadow that they cast on the ground.  Finally, some features, (such as the pier in this map) can be distinguished mainly by their association with certain other features (the ocean in this case.) An interpreter must keep all of these elements of interpretation in mind while working to identify objects from aerial imagery.

Module 1 - Special Topics in GIS - Calculating Metrics for Spatial Data Quality

Data quality is a critical aspect in GIS analysis.  Both accuracy and precision must be addressed.  Both may be positional, temporal, or thematic in nature.  Accuracy is defined as the degree that measured values approach the "true" or reference value.  Precision is not the same as accuracy, but rather is a measure of how close repeat measurements are to each other.  

The map at left depicts 50 repeat measurements (black dots), made using a GPS device, of a single location in Hillsborough County, Florida, near Tampa. The spatial average of the measurements (horizontal only) is shown by the green circle at the center, while degrees of spread, or estimates of precision, are shown by the blue circular zones.  The central zone contains 50% of the measurements, while the outer-most zone contains about 95% of the measurements.  This is a measure of the precision of the data gathering.

Horizontal accuracy of the measurements is indicated by the distance between the average of the measured points (green circle) and the reference location, which is know to be truer to the real position on the ground (red triangle).  The fact that the average of the measured points lies about 3 meters southeast of the reference location indicates a bias in the measured point toward the southeast: a systematic error in accuracy.

Here is a table of the horizontal and vertical accuracy and precision for these GPS measurements.

-Horizontal precision (68%):                                                            4.4 meters

-Horizontal Accuracy

  (Distance between average location and

  reference (“true”) point):                                                                3.2 meters

-Vertical precision (68%):                                                                 5.7 meters            

                            

-Vertical Accuracy

 (Difference between average elevation and

 reference (“true”) point elevation):                                                   6.0 meters

As seen in the table above, if you’re comparing horizontal to vertical for either precision or accuracy, vertical error is larger in both cases.  If you compare horizontal precision to horizontal accuracy, and then vertical precision to vertical accuracy, the pairs of values are fairly similar.  The 68% estimate for vertical precision is slightly better than the vertical accuracy.