Printer Friendly

A comparative analysis of routes generated by Web Mapping APIs.

1. Introduction

Some Web mapping providers (such as Bing Maps and Google Maps) provide mapping data and functionalities via Web Mapping APIs (WMAs) to allow development of specific geospatial Web applications and services. Such geospatial Web applications, also known as "Map Mashups" (Batty et al. 2010) and "Web Mapping 2.0" (Haklay, Singleton, and Parker 2008), reflect the emergent era of geospatial Web applications. WMAs allow researchers to access map data and map functionalities of which routes and directions, among other features, are prominent and commonly available. Currently, there are at least five publically available WMAs that provide access to geographic locations in which maps can be supported at no cost. These WMAs are Bing Maps REST Services (Microsoft Corp., n.d.), Google Maps API (Google Inc., n.d.), HERE Maps API (HERE n.d.), MapQuest Open Data API (MapQuest n.d.), and Yahoo Maps API (Yahoo! Inc., n.d.). Researchers in various fields employ WMAs to develop geospatial Web applications. Example usages of these WMAs are development of a web-based tool to provide tourism information for tourists in Charleston, South Carolina (Pan, Crotts, and Muller 2007); development of a decision-support tool to help analyze optimal locations for depots such that location and distribution costs are minimized (Lopes et al. 2008); development of a Web map for route and direction guidance to referral hospitals (Kobayashi et al. 2010); analysis of an origin-destination travel time matrix (Wang and Xu 2011); and development of a Web map that provides personalized optimal routes to people with physical disabilities (Karimi, Zhang, and Benner 2013). However, despite such projects, currently there is no study that compares the routes WMAs generate.

While WMAs generate different routes based on the same criterion and for the same pair of origin and destination addresses, researchers may not have the requisite knowledge and expertise to compare and analyze the generated routes. Among the features that WMAs differ, quality of data (spatial and non-spatial) and their routing algorithms are focused to address the following research questions:

* What is the relative positional accuracy among the road maps supported by different WMAs?

* Using the same route criterion, do different WMAs deliver the same or different routes for the same pairs of origin-destination addresses?

* For the same routes, are the route attributes (such as distance, direction, and estimated driving duration) also the same? In case of different routes, what are the differences between route attributes?

The paper's contribution is an understanding of routes generated by common WMAs. The results of this work can benefit researchers as they will gain an insight into WMAs and the routes they generate. The process of conducting the analysis in this paper can also be used as a guideline to help researchers perform empirical evaluation on routes generated by WMAs. The structure of the paper is as follows. Section 2 provides the background and related work. Section 3 discusses the data and experiment preparation. Sections 4, 5, and 6 discuss the different parameters for route comparisons. In Section 7, the results of the comparisons are discussed. In Section 8, conclusions and future research are discussed.

2. Background and related work

2.1. Web Mapping API

WMA is designed to work in the Web environment in which a server provides both map data and functionalities to geospatial applications running on a client. The benefits of WMAs to researchers are that: (a) they can save development time in setting up and managing Web Mapping Servers (WMSs) and (b) they can author specific content without concerns about base maps and related Web mapping functionalities. Table 1 shows a comparison between some WMA capabilities provided by Bing Maps, Google Maps, HERE, and MapQuest. Bing Maps, HERE, and MapQuest provide routes based on distance (shortest) and time (fastest) criteria. Google Maps does not allow request for shortest or fastest routes, but it provides a few alternative routes together with distance and travel time so that by analyzing alternative routes, shortest or fastest routes can be selected. The last row in Table 1 shows sources of road databases used by these WMAs. Note that only capabilities relevant to routes are summarized in Table 1; for other capabilities, refer to Haklay, Singleton, and Parker (2008) and Chow (2008).

2.2. Hausdorff distance

In this paper, Hausdorff distance (Hausdorff 1914), which is used to identify similar shapes, for example, see Huttenlocher, Klanderman, and Rucklidge (1993), Dubuisson and Jain (1994), Rucklidge (1997), and Peteri, Couloigner, and Ranchin (2004), is adopted to identify same route geometries retrieved from different WMAs. A brief description of Hausdorff is the following. Considering two sets of points in A and B, Hausdorff distance, dn(A,B), is defined as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

where a and b are the points in set A and B, respectively, and d(a, b) is the distance between point a and b, in a space of interest such as Euclidian space. If the points in A and B represent two different lines, then [d.sub.H](A,B) [not equal to] 0. If [d.sub.H](A,B) = 0, then it can be concluded that A and B are identical. Figure 1 shows four examples, all with the same value of Hausdorff distance ([d.sub.H]). Lines L5 and L6 in Example C, despite a large overlap, still have Hausdorff distance at the value of [d.sub.H]. This example shows that there is no correlation between the Hausdorff distance value and the overlap proportion between the two lines. However, [d.sub.H] [right arrow] 0 implies that the two lines are very similar, such that the geometric deviation between the two lines is small. When compared to the minimum (perpendicular) distance, Hausdorff distance is better for similarity measure because it takes into account the whole shape of the objects rather than considering only the two closest points.

To take into account the variations of route geometry, the condition for identical shape is relaxed such that the new condition is [d.sub.H](A,B) [less than or equal to][beta], where [beta] is a predefined threshold. To determine a suitable threshold ([beta], the upper bound), a number of trials based on randomly selected samples from the population (routes of interest) were performed. The detailed discussion about this process and the value of [beta] are provided in the "Experiment" section.

2.3. Route computation factors and relative positional accuracy

The factors that impact route computation are: (a) node-link connection in road networks; (b) accuracy and resolution of road geometries; and (c) algorithms for computing routes. Node-link connection in road networks significantly contributes to differences in route computation. A road network is composed of nodes (representing road intersections) and links (representing road segments). Links contain traffic flow directions (two-way or one-way) information and properties affecting traversing such as speed limit, road width, distance, and road type. Nodes connect adjacent links and also contain traversing rules among the connected links such as "no right turn," "no through traffic," and "one way". A small difference in node-link connection in two distinct road networks may cause differences for traversing from one node to another in the network. Sources of differences in node-link connection are data update cycle, blunders in data collection, misrepresentation of links and nodes relations, among other sources. These sources vary by map providers based on the assumptions they make in building map databases, the design on which they implement their services, and the software and tools they use to deliver their services. Since WMAs utilize different road network databases (with such differences as node-link connection, data update cycles, and blunders), different routes would be expected.

Accuracy and resolution of road geometry also cause inaccurate distance measurement. Since a road segment's distance is calculated directly from its coordinates, lower accuracy and lower resolution could result in less accurate distance. In addition to distance, relative positional accuracy of points (road intersections), retrieved from WMAs, was considered in this work. The vertical accuracy was not considered because the routes and directions provided by WMAs are mainly for 2D maps, and WMAs do not consider elevation in computing routes. Finally, another factor influencing the computed routes is the logic of the underlying algorithm. Route computation is an optimization problem which is usually addressed by optimization algorithms. Optimization algorithms use a weight (cost) on each road segment to find optimal routes. Example weights are distance, time, expense, and air pollution level. Finding fastest-time routes may consider several variables such as driving speed, traffic congestion, and traffic signal. These variables are often aggregated into a weight and used as an input to an optimization algorithm, such as Dijkstra (Dijkstra 1959) which is a widely used algorithm for finding optimal routes in various applications. For further reading on optimal route finding and optimization algorithms, refer to Pollack and Wiebenson (1960), Cooke and Flalsey (1966), and Cherkassky, Goldberg, and Radzik (1996). In the absence of information about the algorithms WMAs use for computing routes, the general logics in common optimization algorithms, which are commonly used in route computation, are discussed and analyzed in this work.

3. Experiments

A number of experiments were conducted to address the questions set forth in this paper. In the experiments, the road network maps of the city of Pittsburgh, Pennsylvania, USA, provided by the select WMAs were used. According to the US Census Bureau, the city covers 151 square kilometers and features 135 high-rise buildings (Emporis Corporation 2014). According to the road map from City of Pittsburgh, Department of City Planning, the city contained a total of 2179 kilometers of roads in 2012. An overall map of the city and its road network are shown in Figure 2. In this study, only intra-city routes, those with origins and destinations located within the city limit, were considered.

In general, WMAs take origin and destination as a street addresses or geographic coordinates. In case of street address, it needs to be geocoded to obtain its geographic coordinates, which are then used to compute routes. Due to the large variations in positional accuracy of geocoded street addresses by WMAs, in particular in residential and commercial areas (Roongpiboonsopit and Karimi 2010a, 2010b), road intersection addresses (such as N. Bellefield Ave & 5th Ave, Pittsburgh, PA 15213) instead of street addresses (such as 135 N. Bellefield Ave, Pittsburgh, PA 15213) were used for locating origins and destinations. A total of 80 road intersections were randomly selected and manually verified to make sure that they exist in all WMAs' road databases; their locations are shown in Figure 2. For details of geocoding and associated errors, refer to Karimi, Durcik, and Rasdorf (2004).

Figure 3 shows an example of geocoded road intersection address, "3rd Ave & Ross St, Pittsburgh, PA 15219," by Bing Maps, Google Maps, and MapQuest, respectively. These three WMAs locate the address at the location where the two road center lines are intersected. Despite the precise geocoding results of each WMA, each geocoded location by each WMA has different coordinates. To show the differences, the three coordinates (points #4, #5, and #6 in Figure 4) were plotted on a neutral map background from City of Pittsburgh, Department of City Planning. Coordinates geocoded by Google Maps (#4) are slightly away from the coordinates from Bing Maps (#6) and MapQuest (#5). This positional difference is due to geometrical discrepancies among WMAs. An empirical exploration on road intersection coordinates was also conducted and discussed in later sections.

Since this paper is focused on empirical comparisons of the routes retrieved from WMAs, to which road intersections are input for origin and destination, only Web mapping providers that could geocode road intersection addresses and provide routes and directions were considered. Table 2 shows the features of WMAs from Bing Maps, Google Maps, HERE, and MapQuest. Of these WMAs, as FlERE's WMA does not geocode road intersections, only Bing Maps (B), Google Maps (G), and MapQuest (M) were used. For the experiment, a total of 3160 distinct combinations of 80 road intersection locations, as O-D pairs for one-way trips, were considered. This resulted in a total of 3160 shortest routes and 3160 fastest routes. Associated with each returned route were route geometry, driving direction, route distance, and driving duration. Of the 3160 routes that were returned from each WMA, 2697 had geocoding results matched correctly for their origin and destination, hence the 2697 were used in the analysis. Figure 5 shows the spatial distribution of the 2697 routes (only shortest routes) in the study area.

For a pair of O-D, different WMAs may return the same or a different route. To address the research questions set forth, the routes were classified into same and different for analysis. Flausdorff distance was used with the relaxed condition [d.sub.H]{A,B) [greater than or equal to] [beta] to classify the routes. However, the threshold [beta] is data dependent and must be determined through experimentation. For this, the following process was implemented. One hundred routes were randomly selected from the 2697 routes. Those 100 routes were overlaid on a background map and visually inspected to identify the routes that share same road segments. After the visual inspection, 22 routes were identified as same routes. Hausdorff distances for the 22 routes were computed, and the maximum value (31.253 meters) among the computed Hausdorff distances was determined as the value of [beta]. Accordingly, in this work, routes are considered "same" if the Hausdorff distance between the geometries of all the three results (from the three WMAs) is less than 31.26 meters. To avoid ambiguity, a large threshold value should be used for "different" routes; 200 meters was arbitrarily selected for the threshold. Any routes that fall between 31.26 and 200 meters were considered "ambiguous" and not used. Therefore, based on the two metrics above, the returned routes from WMAs are classified into SS: same route under the shortest route criterion, SF: same route under the fastest route criterion, DS: different route under the shortest route criterion, and DF: different under the fastest route criterion. The number of routes in each group is shown in Table 3 and it is observed that the number of same routes increases (from SS: 554 to SF: 733) when route criterion changes from shortest to fastest, and vice versa for the number of different routes (from DS: 697 to DF: 428). This indicates that the three WMAs tend to return more same routes with fastest as the route criterion. Figures 6 and 7 show an example of a same route and a different route. Note that instead of using the calculated similarity quantity (Hausdorff distance) directly, the categorization approach was taken as it helps remove ambiguous routes and analyze routes at a lower level of granularity.

4. Relative positional accuracy

The positional accuracy is considered relative in that the coordinates of road intersections are compared among the WMAs, not to a gold standard or a baseline. The coordinates of the 80 road intersections retrieved from the three WMAs were compared against each other. Table 4 shows relative error distances of the coordinates of the road intersections from B, G, and M. The average error distance between B and M is 0.504 meters and the average error distances between B-G and G-M are 3.292 and 3.410 meters, respectively. To comply with standard positional accuracy evaluation, RMS (Root Mean Square) of the error distances was also examined. The acceptable RMS errors by the American Society for Photogrammetry and Remote Sensing horizontal map accuracy standard (ASPRS 1990) were based on Class 1 (which is the most stringent class). RMS errors for B-G and G-M are 4.18 and 4.27 meters, respectively, which fall into the Class 1 acceptable RMS error for map scale 1:20,000. RMS error for B-M is 0.95 meters which falls into the Class 1 acceptable RMS error for map scale 1:4000. Since RMS error for B-M falls into a larger map scale, it can be concluded that road intersection coordinates from B and M are more similar to each other than to those from G. Figure 8 shows the error distance distributions through histograms.

5. Attributes of same routes

To find out whether or not the route attributes of same routes are the same, comparisons of attributes of same routes were conducted. Route distance, driving duration, number of turns, and number of traffic lights were the attributes considered for the comparisons. Route distance and driving duration were retrieved from the WMAs and compared (see Table 5). The average route distances of B, G, and M are similar (SS: 4.62, 4.60, and 4.60 kilometers; SF: 5.99, 5.95, and 5.96 kilometers), and the ranges of the difference between average route distances are 0.43% for SS and 0.67% for SF. The route distances also satisfied homoscedasticity as shown in the box plots in Figure 9. These narrow ranges and the homoscedasticity are reasonable and expected because both SS and SF contain only same routes (same population) among the WMAs. Despite the similar average route distances and homoscedasticity, the normal distribution assumption was violated in both SS and SF (p < 0.05 in Pearson's chi-squared test). As a result, Kruskal-Wallis test was conducted to statistically analyze route distance. The test results (Table 6) for all the three pairs (B-G, G-M, and B-M) confirm that route distances between WMAs are not statistically significantly different for both SS and SF routes. Despite the statistically insignificant difference between route distances, driving durations are different. Kruskal-Wallis tests for driving duration (Table 6) indicate that driving durations of routes from G are statistically significantly different than those from B and M, while B and M are the same. Note that in each Kruskal-Wallis test, the level of confidence was 95% ([alpha] = 0.05), and the critical [chi square] value was 3.84.

Figure 10 shows the relationship between route distance and driving duration. With "shortest" as the route criterion (SS), the regression lines of B, G, and M are almost parallel to each other (slope = 0.0013, 0.0012, and 0.0014, respectively). However, with "fastest" as the route criterion (SF), the regression lines of B and G are parallel (slope = 0.0009) to each other, and M has the highest slope. For both SS and SF, B has the largest intercept value followed by G and M. Considering the effect of route criterion change (between SS and SF), B had the largest slope change (from 0.0013 to 0.0009, decreased by 31%) followed by G (from 0.0012 to 0.0009, decreased by 25%) and M (from 0.0014 to 0.0011, decreased by 21%). The decreases in slopes indicate that all of the three WMAs return routes that require shorter driving duration. Nevertheless, the intercept values of all graphs increase (the differences between them are also larger) with "fastest" as the route criterion. This means B, G, and M may take into account different factors (or same factors but different weights) for estimating travel time.

Numbers of turns were also compared. Numbers of turns were derived using the driving directions of the route. Table 7 lists the number of times that the turn-related keywords appeared in the driving direction. The keywords were grouped into three sets. The first set contained instruction indicating explicit turn such as "turn right" and "turn left." The second set contained the terms indicating slight turn related to ramp such as "take the right ramp." The third set contained the terms indicating general slight turn such as "bear right." It is observed that WMAs may not provide same driving directions even if the route geometries are same and only the number of turns is considered. Table 8 shows an example of different driving directions for the same route. The empirical results for different driving directions are shown in Table 5 where the average numbers of turns are counted based on each set of turn-related keywords. The turn comparison also reveals that B uses the terms "ramp," "bear," and "slight" to indicate turns most often followed by M and G, respectively. The range of the difference between average numbers of turns among SS routes is 21.9% and among SF routes is 39.2%. These large ranges are also in line with the work conducted by Lovelace, Hegarty, and Montello (1999) which argues that route directions are considered to be subjective.

In addition to the comparisons of number of turns, numbers of traffic lights were also compared. A traffic light is detected if its spatial buffer (radius 10 meters) overlaps the route geometry of interest. The 10-meter radius is arbitrary selected thus the counting may not be accurate compared to a ground truth. However, consistency is more important than accuracy since the experiment is focused on comparative comparison. The results are shown in Table 5 and reveal that the average number of traffic lights on routes from B, G, and M are similar for both SS (7.26, 7.20, and 7.24 with range difference 0.83%) and SF (8.10, 7.73, and 8.08 with range difference 4.6%). Kruskal-Wallis test results (Table 7) also confirmed that there was no difference between numbers of traffic lights for all the comparing pairs.

6. Comparing different routes

The final comparisons are related to the two groups of different routes (DS and DF). Route distance, driving duration, speed, and number of traffic lights were focused in this analysis. Number of turns was disregarded as the comparison of same routes (see earlier sections) indicates that turns appearing in driving directions are not reliable. The results of these comparisons are shown in Table 9. For DS (where shortest route request was made), B delivered routes with shortest average distance (8.57 kilometers) followed by M (8.96 kilometers) and G (9.33 kilometers). However, routes from G have the smallest average number of traffic lights (16.09) followed by M (17.18) and B (20.09). The average number of traffic lights per kilometer for routes from G is the smallest (1.83) followed by M (2.32) and B (2.01). Routes from G also have the fastest average speed (39.75 kilometers per hour). For DF, M delivered routes with the shortest average distance (9.43 kilometers) followed by B (9.71 kilometers) and G (9.90 kilometers). When route changed from DS to DF, the range of the difference between route distances decreased (from 8.5% to 4.9%), and, as well, the range of the difference between averages speeds (from 31.2% to 11.0%). This means routes are more similar in terms of distance and speed when "fastest" is made as the route criterion. G delivered routes with the lowest average number of traffic lights (1.36) followed by B (1.72) and M (2.02). However, when route criterion changed from DS to DF, the range of the difference between the average numbers of traffic lights increased from 22.5% (DS) to 36.3% (DF).

Statistical tests were also conducted for route distance, driving duration, speed, and number of traffic lights for both DS and DF routes. Box plots (Figure 11) of the four route attributes show explicit violations of both homoscedasticity and normal distribution assumption. As a result, Kruskal-Wallis test was used for all of the statistical analyses. The test results (Table 10) reveal that route distance, driving duration, speed, and number of traffic light are all significantly different for all comparing pairs for DS routes. Route distances are not significantly different for all pairs compared for DF routes. As for DF routes, driving durations and speeds are not significantly different for B-G, but are significantly different for G--M and B-M. The numbers of traffic lights are significantly different for all pairs. Note that in each Kruskal-Wallis test, the level of confidence was 95% ([alpha] = 0.05), and the critical [chi square] value was 3.84.

7. Discussions

To address the questions set forth in this work, the results are discussed as follows. Question 1: "What is the relative positional accuracy among the road maps supported by different WMAs?" The positional accuracy among the road maps supported by different WMAs is similar. Table 4 shows that all WMAs have similar positional accuracy, and B-M has closest relative positional accuracy among the comparing pairs. Question 2: "Using the same route criterion, do different WMAs deliver the same or different routes for the same pairs of origin-destination addresses?" The three WMAs tend to return more same routes with fastest as the route criterion. The evidence for this is in Table 3 where the number of same routes increases when route criterion changes from "shortest" to "fastest," and vice versa for the number of different routes. Question 3: "For routes that are the same, are the route attributes also the same?" According to the statistical tests in Table 6, neither route distances nor number of traffic lights are not significantly different for all the comparing pairs. As for driving duration, only B-M is not significantly different. Regarding the number of turns, Table 5 shows that the ranges of the differences between the average numbers of traffic lights among WMAs (SS: 0.83%; SF: 4.6%) are much smaller than that of the average numbers of turns (SS: 21.9%; SF: 39.2%). One reason for this large difference between the number of traffic lights and the number of turns can be that the number of traffic lights is more consistent compared to the number of turns. The numbers of traffic lights were computed using 10-meter spatial buffering as described previously, while the numbers of turn were extracted from driving directions retrieved from the WMAs. Since the WMAs employ different methods for turns in their driving direction (see an example in Table 8), larger variations in the numbers of turns are reasonable. As for route distance, the ranges of the difference for SS and SF are 0.43% and 0.67%, respectively. These small ranges are also reasonable since driving distance is a spatial property that is derived from positional information, and it was also shown that routes from the WMAs have similar relative positional accuracy. Question 4: "In case of different routes, what are the differences between route attributes?" According to Table 9, when route criterion is "shortest," B has the shortest average route distance, G has the fastest estimated driving speed and the minimum number of traffic lights. An observation related to numbers of traffic lights in Table 9 is that changing route criterion from "shortest" to "fastest" resulted in 26% decrease in the average number of traffic lights per kilometer for both B and G, and 5.6% for M. Based on this observation, the number of traffic lights may also play a role in B's and G's routing algorithms and its driving duration estimation. Changing route criterion from "shortest" to "fastest" also resulted in 24%, 4.8%, and 2.1% decrease in the average estimated driving durations for B, G, and M, respectively. Considering the driving durations and number of traffic lights per kilometer together, despite the same 26% decrease in the average number of traffic lights per kilometer for both B and G, G has a much smaller percentage decrease of estimated driving duration compared to B (B: 24% and G: 4.8%). This evidence reveals that number of traffic lights may have minimal impact on G's driving time estimation.

8. Conclusions and future research

In this paper, an empirical comparison of routes from three Web mapping APIs provided by Bing, Google, and MapQuest was presented. Shortest and fastest route criteria and 3160 origin-destination pairs were analyzed. Comparative analysis of the routes included relative positional accuracy, route distance, driving duration, driving direction, speed, and number of traffic lights. The results show that WMAs return different values of route attributes (such as driving duration) even if the routes are the same. It was also observed that the number of same and different routes changed significantly when route criterion changed between "shortest" and "fastest."

The findings in this paper are based on a small study area, and more complicated route criteria (such as avoid tool or highway) were not considered. Further studies with additional route criteria and different study areas may reveal more interesting findings.

Funding

The student financial support by the Ministry of Science and Technology of Thailand for this work is acknowledged.

http://dx.doi.org/10.1080/15230406.2014.976656

References

American Society for Photogrammetry and Remote Sensing (ASPRS). 1990. "ASPRS Accuracy Standards for Large-Scale Maps." Photogrammetric Engineering and Remote Sensing 56 (7): 1068-1070.

Batty, M., A. Hudson-Smith, R. Milton, and A. Crooks. 2010. "Map Mashups, Web 2.0 and the GIS Revolution." Annals of GIS 16 (1): 1-13. doi: 10.1080/19475681003700831.

Cherkassky, B. V, A. V. Goldberg, and T. Radzik. 1996. "Shortest Paths Algorithms: Theory and Experimental Evaluation." Mathematical Programming 73 (2): 129-174. doi:10.1007/BF02592101.

Chow, T. E. 2008. "The Potential of Maps APIs for Internet GIS Applications." Transactions in GIS 12 (2): 179-191. doi: 10.1111/j. 1467-9671.2008.01094.x.

Cooke, K. L., and E. Halsey. 1966. "The Shortest Route through a Network with Time-Dependent Intemodal Transit Times." Journal of Mathematical Analysis and Applications 14 (3): 493-498.' doi: 10.1016/0022-247X(66)90009-6.

Dijkstra, E. W. 1959. "A Note on Two Problems in Connexion with Graphs." Numerische Mathematik 1: 269-271. doi: 10.1007/BF01386390.

Dubuisson, M. R, and A. K. Jain. 1994. "A Modified Hausdorff Distance for Object Matching." Proceedings of the 12th IAPR International Conference on Pattern Recognition, 1994. Vol. 1 Conference A: Computer Vision & Image Processing, Jerusalem, October 9-13 (Vol. 1, 566-568). IEEE.

Emporis Corporation. 2014. "Tall Building of Pittsburgh." Accessed January, http://www.emporis.com/en/wm/ci/bu/sk/? id=101313

Google Inc. n.d. "Google Developers." Accessed January 2014. https://developers.google.com/maps/

Haklay, M., A. Singleton, and C. Parker. 2008. "Web mapping 2.0: The Neogeography of the GeoWeb." Geography Compass 2 (6): 2011-2039. doi:10.1111/j.1749-8198.2008.00167.x.

Hausdorff, F. 1914. Grundzuege der Mengenlehre. Leipzig: Viet.

HERE. n.d. "Maps API for JavaScript Developer's Guide." Accessed January 2014. https://developer.here.com/javascriptapis/documentation/maps

Huttenlocher, D. R, G. A. Klanderman, and W. J. Rucklidge. 1993. "Comparing Images Using the Hausdorff Distance." IEEE Transactions on Pattern Analysis and Machine Intelligence 15 (9): 850-863. doi: 10.1109/34.232073.

Karimi, H. A., M. Durcik, and W. Rasdorf. 2004. "Evaluation of Uncertainties Associated with Geocoding Techniques." Journal of Computer-Aided Civil and Infrastructure Engineering 19 (3): 170-185.

Karimi, H. A., L. Zhang, and J. Benner. 2013. "Personalized Accessibility Maps (PAMs) for Communities with Special Needs." The 12th International Symposium on Web and Wireless Geographical Information Systems (GGIS 2013), Banff, April 4-5.

Kobayashi, S., T. Fujioka, Y. Tanaka, M. Inoue, Y. Niho, and A. Miyoshi. 2010. "A Geographical Information System Using the Google Map API for Guidance to Referral Hospitals." Journal of Medical Systems 34 (6): 1157-1160. doi: 10.1007/ S10916-009-9335-0.

Lopes, R. B., S. Barreto, C. Ferreira, and B. S. Santos. 2008. "A Decision-Support Tool for a Capacitated Location-Routing Problem." Decision Support Systems 46 (1): 366-375. doi: 10.1016/j.dss.2008.07.007.

Lovelace, K. L., M. Hegarty, and D. R. Montello. 1999. "Elements of Good Route Directions in Familiar and Unfamiliar Environments." In Spatial Information Theory. Cognitive and Computational Foundations of Geographic Information Science, edited by C. Freksa and D. M. Mark, 65-82. Berlin: Springer.

MapQuest. n.d. "Open Data Map APIs and Web Services." Accessed January 2014. http://developer.mapquest.com/ web/products/open

Microsoft Corp. n.d. "Bing Maps REST Services." Accessed January 2014. http://msdn.microsoft.com/en-us/library/ ff701713.aspx

Pan, B., J. C. Crotts, and B. Muller 2007. "Developing Web-Based Tourist Information Tools Using Google Map." ENTER, Ljubljana, December, 503-512.

Peteri, R., I. Couloigner, and T. Ranchin. 2004. "Quantitatively Assessing Roads Extracted from High-Resolution Imagery." Photogrammetric Engineering & Remote Sensing 70 (12): 1449-1456. doi:10.14358/PERS.70.12.1449.

Pollack, M., and W. Wiebenson. 1960. "Solutions of the Shortest-Route Problem-A Review." Operations Research 8 (2): 224-230. doi:10.1287/opre.8.2.224.

Roongpiboonsopit, D., and H. A. Karimi. 2010a. "Quality Assessment of Online Street and Rooftop Geocoding Services." Cartography and Geographic Information Science 37 (4): 301-318. doi: I0.1559/152304010793454318.

Roongpiboonsopit, D., and H. A. Karimi. 2010b. "Comparative Evaluation and Analysis of Online Geocoding Services." International Journal of Geographical Information Science 24 (7): 1081-1100. doi:10.1080/13658810903289478.

Rucklidge, W. J. 1997. "Efficiently Locating Objects Using the Hausdorff Distance." International Journal of Computer Vision 24 (3): 251-270. doi:10.1023/A:1007975324482.

Wang, F., and Y. Xu. 2011. "Estimating O-D Travel Time Matrix by Google Maps API: Implementation, Advantages, and Implications." Annals of GIS 17 (4): 199-209.

Yahoo! Inc. n.d. "Yahoo! Maps Web Services." Accessed January 2014. http://developer.yahoo.com/maps/

Monsak Socharoentum and Hassan A. Karimi *

Geoinformatics Laboratory, School of Information Sciences, University of Pittsburgh, 135 N Bellefield Ave, Pittsburgh, PA 15213, USA

* Corresponding author. Email: hkarimi@pitt.edu

(Received 14 March 2014; accepted 25 September 2014)

Table 1. Comparison between routing parameters and criteria.

Parameters/criteria                           WMAs

                             Bing     Google    HERE   MapQuest
                             Maps      Maps

Travel modes available
  Driving                   Yes       Yes       Yes    Yes
  Walking                   Yes       Yes       Yes    Yes
  Bicycling                 No        Yes       No     Yes
  Transit (public           Yes       Yes       Yes    Yes
    transport)
Specific options for
    driving
  Shortest distance         Yes       No        Yes    Yes
  Shortest time             Yes       No        Yes    Yes
  Avoid highway             Yes       Yes       Yes    Yes
  Avoid toll                Yes       Yes       Yes    Yes
  Avoid ferry               No        No        Yes    Yes
  Avoid unpaved road        No        No        Yes    Yes
  Avoid country crossing    No        No        No     Yes
  Avoid seasonal closed     No        No        No     Yes
    road
  Avoid tunnel              No        No        Yes    No
  Avoid park                No        No        Yes    No
  Provide route             No        Yes       No     Yes
    alternative
Consider dynamic traffic    Yes       Yes       Yes    Yes
Waypoint (1) support        Yes (2)   Yes (3)   Yes    Yes (4)
Provide route geometry      Yes       Yes       Yes    Yes
Provide driving direction   Yes       Yes       Yes    Yes
Road database               HERE      Google    HERE   HERE

Notes: (1) Waypoint is a stop on the route; Waypoints alter the
route by routing it through the specified location(s).

(2) Limited to 23 waypoints for free service (exclude O-D
points).

(3) Limited to 8 waypoints for free service (exclude O-D points;
limited to 23 for paid service; Map API Premier).

(4) Limited to 48 waypoints (exclude O-D points) and under 8000
miles (total distance) for free service.

Table 2. Route characteristics and road intersection geocoding.

WMAs          Alternative    Route     Driving         Road
                routes      geometry   direction   intersection
                                                     address
                                                    geocoding

Google Maps       Yes         Yes         Yes          Yes
Bing Maps         No          Yes         Yes          Yes
MapQuest          No          Yes         Yes          Yes
HERE              No          Yes         Yes           No

Table 3. Classification of routes.

                                         Route criterion

Number of routes                      Shortest   Fastest

Total original retrieved routes         3160       3160
Total matched routes                    2697       2697
Total same routes (SS or SF)          (SS) 554   (SF) 733
Total different routes (DS or DF)     (DS) 697   (DF) 428
Total ambiguous routes                  1446       1536

Table 4. Error distances of the testing road intersections.

Statistics         Relative error
                 distances (meters)

              B-G      G-M      B-M

Average       3.292    3.410   0.504
Max          14.113   14.013   4.406
Min           0.085    0.203   0.000
SD            2.590    2.592   0.810
RMS           4.18     4.27    0.95

Table 5. Comparisons between same routes (SS and SF).

                                         WMA

Attributes (average values)        B      G      M     Range(%)

SS
  Route distance (kilometers)     4.62   4.60   4.60    0.43
  Driving duration (minutes)      8.45   7.43   8.04   12.8
  Number of turns (first set)     2.57   2.88   2.70      --
  Number of turns (second set)    0.46   0.06   0.01      --
  Number of turns (third set)     1.07   0.36   0.68      --
  Sum of turns                    4.10   3.31   3.39   21.9
  Number of traffic lights        7.26   7.20   7.24    0.83
  Traffic lights/kilometer        1.65   1.65   1.65    0.00
SF
  Route distance (kilometers)     5.99   5.95   5.96    0.67
  Driving duration (minutes)      8.75   8.02   8.83    9.5
  Number of turns (first set)     2.34   2.78   2.50      --
  Number of turns (second set)    0.95   0.10   0.05      --
  Number of turns (third set)     1.48   0.57   0.72      --
  Sum of turns                    4.77   3.44   3.27   39.2
  Number of traffic lights        8.10   7.73   8.08    4.6
  Traffic lights/kilometer        1.52   1.48   1.53    3.3

Table 6. Kruskal-Wallis test results for SS and SF routes
("[approximately equal to]": same, "[not equal to]" different).

Test parameters                      Comparing pairs

                      B-G, [chi         G-M, [chi        B-M, [chi
                      square],          square],          square],
                       p-value           p-value          p-value

SS
  Route distance   [approximately    [approximately    [approximately
                     equal to],        equal to],        equal to],
                     0.02, 0.8776      0.00, 0.9902      0.03, 0.8699
  Driving          [not equal to]    [not equal to]    [approximately
    duration         14.65, 0.0001     4.89, 0.0271      equal to],
                                                         2.50, 0.1140
  Number of        [approximately    [approximately    [approximately
    traffic          equal to],        equal to],        equal to],
    lights           0.01, 0.9119      0.01, 0.9404      0.00, 0.9690

SF
  Route distance   [approximately    [approximately    [approximately
                     equal to],        equal to],        equal to],
                     0.04, 0.8463      0.00, 0.9663      0.03, 0.8655
  Driving          [not equal to]    [not equal to]    [approximately
    duration         12.23, 0.0005     11.76, 0.0006     equal to],
                                                         0.01, 0.9404
  Number of        [approximately    [approximately    [approximately
    traffic          equal to],        equal to],        equal to],
    lights           1.52, 0.2175      1.29, 0.2567      0.01, 0.9272

Note: Degree of freedom = 1; N = 554 for SS; N = 733 for SF.

Table 7. Turn-related keywords.

First set              Second set              Third set

Turn right/left   Take ramp right/left   Slight right/left
Take the first    Take the ramp          Bear right/left
  right/left
Take the second   --                     Turn slight right/left
  right/left
Take the third    --                     --
  right/left

Table 8. Comparing driving direction for the same route.

WMAs                       Route direction

B      1. Depart Boulevard of the Allies toward Chancery
         Way
       2. Take ramp right and follow signs for Liberty Bridge
       3. Bear right onto Liberty Bridge
       4. Turn right onto PJ McArdle Roadway
       5. Turn right onto Grandview Ave
       6. Turn left onto Augusta St
       7. Arrive at Augusta St & Wilmar St, Pittsburgh, PA
       15211
G      1. Head southeast on Boulevard of the Allies toward
         Chancery Way
       2. Slight right onto the Liberty Bridge ramp to US-19/
         PA-51
       3. Merge onto Crosstown Blvd
       4. Continue onto Liberty Bridge
       5. Turn right onto P J McArdle Roadway
       6. Slight right onto Grandview Ave
       7. Turn left onto Augusta St
M      1. Start out going southeast on Boulevard of the Allies
         toward Chancery Way.
       2. Take the Liberty Bridge ramp toward US-19/PA-51.
       3. Turn slight right onto Liberty Bridge.
       4. Turn right onto PJ McArdle Rdwy.
       5. Turn right onto Grandview Ave.
       6. Turn left onto Augusta St.
       7. Augusta ST & Wilmar ST.

Table 9. Comparison between different routes.

Attributes (average                   WMA
values)

                               B       G       M     Range (%)

DS
  Distance (kilometers)       8.57    9.33    8.96      8.5
  Duration (minutes)         18.41   14.57   15.37     23.8
  Speed (kilometers/hour)    27.67   38.14   34.92     31.2
  Number of traffic lights   20.09   16.09   17.18     22.5
  Traffic lights/kilometer    2.32    1.83    2.01     23.9
DF
  Distance (kilometers)       9.71    9.90    9.43      4.9
  Duration (minutes)         14.05   13.87   15.05      8.2
  Speed (kilometers/hour)    41.03   41.68   37.29     11.0
  Number of traffic lights   15.86   12.52   18.15     36.3
  Traffic lights/kilometer    1.72    1.36    2.02     36.2

Table 10. Kruskal-Wallis test results for DS and DF routes
("[approximately equal to]": same, "[not equal to]": different).

Test route                       Comparing pairs
attributes

                 B-G, [chi          G-M, [chi          B-M, [chi
                  square],           square],           square],
                  p-value            p-value            p-value

DS
  Distance    [not equal to],    [not equal to],    [not equal to],
                16.82, 0.0000      4.03, 0.0447       4.86, 0.0275
  Duration    [not equal         [not equal to],    [not equal to],
                to], 179.30,       12.29, 0.0005      112.73, 0.0000
                0.0000
  Speed       [not equal to],    [not equal to],    [not equal to],
                614.28, 0.0000     68.71, 0.0000      429.93, 0.0000
  Number of   [not equal to],    [not equal to],    [not equal to],
    traffic     30.01, 0.0000      5.31, 0.0211       11.09, 0.0009
    lights
DF
  Distance    [approximately     [approximately     [approximately
                equal to],         equal to],         equal to]
                0.03, 0.8717       1.10, 0.2943       1.57, 0.2100
  Duration    [approximately     [not equal to],    [not equal to],
                equal to],         17.73, 0.0000      10.12, 0.0015
                1.32, 0.2504
  Speed       [approximately     [not equal to],    [not equal to],
                equal to],         78.20, 0.0000      34.78, 0.0000
                3.45, 0.0633
  Number of   [not equal to],    [not equal to],    [not equal to],
    traffic     45.09, 0.0000      115.00, 0.0000     13.42, 0.0002
    lights

Note: Degree of freedom = 1; N = 697 for DS; N = 428 for DF.
COPYRIGHT 2015 Taylor & Francis Group LLC
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2015 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Socharoentum, Monsak; Karimi, Hassan A.
Publication:Cartography and Geographic Information Science
Geographic Code:1U2PA
Date:Jan 1, 2015
Words:6844
Previous Article:A comparison of usefulness of 2D and 3D representations of urban planning.
Next Article:A method based on graphic entity for visualizing complex map symbols on the web.
Topics:

Terms of use | Privacy policy | Copyright © 2020 Farlex, Inc. | Feedback | For webmasters