Printer Friendly

Finding least-cost paths across a continuous raster surface with discrete vector networks.

The problem of finding the least-cost path from a source point to a destination point can be dealt with by routing across a continuous surface or routing along a discrete network. The solutions within these two contexts are linked to the use of a raster- or a vector-based least-cost path algorithm. This study presents a technique which integrates raster- and vector-based least-cost path algorithms for determining the least-cost path across a continuous raster surface with discrete vector networks. The technique incorporates ancillary vector data sets that are required to examine the travel cost at each link, connections between nodes, and the representation of intersecting links in the discrete vector network into raster-based least-cost path analysis. The integrated technique presented here is applicable to all-terrain vehicle navigation where a continuous raster surface and discrete vector networks need to be considered simultaneously in order to find least-cost paths. This paper describes the concept behind, and details of, the integrated technique. Applications of the technique with synthetic and real-world data sets are also presented. They provide proof that the technique is effective in finding least-cost paths across a continuous raster surface with discrete vector networks.

Keywords: least-cost path; route planning; network analysis; navigation; multimodal transport

Introduction

Least-cost path analysis is a spatial optimization technique that is frequently used in Geographic Information Systems (GIS) (Lee and Stucky 1998). Finding the least-cost path from a source point to a destination point can be done within two contexts: (a) routing along a discrete network and (b) routing across a continuous surface. These solutions involve vector- and raster-based least-cost path algorithms (Goncalves 2010).

When movement is restricted to the chains of a discrete network (for example, roads, pipelines, or aircraft flight corridors), vector-based algorithms, such as Dijkstra's (1959) algorithm and the A* algorithm (Hart, Nilsson, and Raphael 1968) can be used to determine the least-cost path (Huang, Wu, and Zhan 2007). In this case, vector data sets are required to build a network model in which spatial nodes are connected by weighted links that represent physical distance, time, cost, or risk incurred in travelling between the nodes. Vector-based least-cost path algorithms can robustly solve problems which need to model flow along a discrete vector network. However, they are incapable of exploring a continuous raster surface to locate a usable path (Goncalves 2010).

In contrast, raster-based least-cost path algorithms can model possible routes across a continuous surface because they typically use techniques that transform the problem from the field of view of a continuous raster surface to a virtual discrete vector network (Collischonn and Pilar 2000). However, their application is usually limited to a continuous raster surface without considering any discrete vector networks (Snyder et al. 2008). A few studies attempted to analyze least-cost paths across a continuous raster surface with considerations of discrete vector networks (Choi et al. 2009; Choi and Nieto 2011). In these studies, the vector networks were converted into cells in a raster data set and then, conventional raster-based least-cost path algorithms were applied. Few researchers attempted to develop a technique that can simultaneously consider a continuous raster surface and discrete vector networks to find least-cost paths. This solution is crucial for such applications as all-terrain vehicle (ATV) navigation, where least-cost paths need to be determined across continuous raster surfaces as well as along discrete vector networks.

This study presents an integrated technique that combines raster- and vector-based least-cost path algorithms to find least-cost paths across a continuous raster surface with discrete vector networks. The concept behind the integrated technique is presented, as are applications of the technique to synthetic and real-world data sets. Our research reveals that the integrated technique we developed can provide credible information for finding least-cost paths across a continuous raster surface with discrete vector networks.

Limitations of conventional raster-based least-cost path algorithms in handling a discrete vector network

Raster-based algorithms have advantages over vector-based algorithms for finding least-cost paths across a continuous raster surface (Wise 2002). However, they are unsuitable for finding least-cost paths along a discrete vector network because the jagged appearance of the discrete vector network in the raster surface often causes overestimation of the travel cost along a link (see Figure 1a and b). Tomlin (2010) proposed a method that eliminates this problem by keeping track of the locations at which propagated waves of accumulating travel cost either refract or diffract, however his method is only applicable to a continuous raster surface without any discrete vector networks. Another problem with raster-based least-cost path algorithms is that they usually restrict the number of connections between the cell of interest and other cells acting as virtual links (Xu and Lathrop 1995). For example, as shown in Figure 1c, the number of connections between cell O and other direct or indirect neighboring cells is limited to 16 when the Knight's pattern is used to define the move sets on the continuous raster surface. Last but not least, raster-based least-cost path algorithms provide no natural way to distinguish a point where traffic routes cross (Figure 1a) from an overpass (Figure 1d), even if a special code is used to identify certain cells as nodes (Wise 2002). This makes it difficult to trace the topological relationships among links in discrete vector network.

Development of an integrated technique

The integrated technique we developed combines raster-and vector-based least-cost path algorithms in order to overcome the limitations of conventional raster-based algorithms in handling a discrete vector network. Figure 2 illustrates its ten steps (or procedures).

In the first step, a continuous surface is divided into rows and columns to form a grid matrix. Each cell within the grid has location coordinates and attribute values. In the second step, a virtual network is established from the grid, by assuming that the center of each cell serves as the virtual node and that the connections between neighboring cell centers act as the virtual links. The virtual network is constructed using a definition of move sets such as the Rook's pattern, Bishop's pattern, Queen's pattern in a 3 x 3 cell window, Knight's pattern in a 5 x 5 cell window, Knight31's pattern, Knight32's pattern in a 7 x 7 cell window, and others in larger cell windows. As the size of the cell window increases, the turn-angle interval (angle between an incoming and outgoing path at a cell) for the path can be reduced. This will make the path smoother (Saha et al. 2005). The effects of different definitions of move sets on the least-cost path analysis have been discussed elsewhere (Xu and Lathop 1995; Yu, Lee, and Munro-Stasiuk 2003; Saha et al. 2005).

In the third step, the source of cells is identified where Dijkstra's algorithm will be initiated. The source raster data set provides information about the locations of source cells with unique IDs. In the fourth step, the integrated technique initializes the attribute values of each cell in the grid. It does so by (a) assigning a value of zero to the source cells and a value of infinity to other cells as an initial accumulated travel cost; (b) marking all cells as unvisited; and (c) selecting one of the source cells and setting it as the current cell.

In the fifth step, the integrated technique searches unvisited neighboring cells linked to the current cell in the virtual network, and then it calculates the travel costs from the current cell to the unvisited neighboring cells. In this study, the following cost function, suggested by Zhan, Menon, and Gao (1993) and employed by the PATH DISTANCE tool in ArcGIS software, was utilized to calculate the travel costs:

[Cost.sub.N[right arrow]S] = 0.5 x [SD.sub.N] x [VF.sub.N[right arrow]S] x ([C.sub.N] x [HF.sub.N] + [C.sub.S] x [HF.sub.S] (1)

where:

[Cost.sub.N[right arrow]S] is the travel cost from cell N to cell S;

[SD.sub.N-S] is the 2.5-dimensional (2.5D) physical distance (m) between the centers of cell N and cell S;

[VF.sub.N[right arrow]S] is the vertical factor taking into account the increasing/decreasing cost when moving uphill/downhill from cell N to cell S;

[C.sub.N] ([C.sub.s]) is the cost per unit length of passing through cell N (cell S); and [HF.sub.N] ([HF.sub.s]) is the horizontal factor which accounts for the increasing cost when moving with a small angle between the predominant horizontal direction and an outgoing path at the center of cell N (cell S) (Figure 3).

When the fifth step is completed, the integrated technique checks whether there are any nodes in the discrete vector network which are located in the current cell. These nodes are searched for by examining the Node data set that is provided as one of the ancillary vector data sets. The Node data set includes point features representing the nodes in the discrete vector network. The attribute table of the Node data set provides information about the ID, X and Y coordinates; the ID of the first outgoing link; and the access and egress costs at each node. If the current cell has one or more nodes, the integrated technique searches for the first outgoing link starting from each node using the Node data set and then, in the sixth step, identifies the travel costs from the nodes to other nodes linked in the discrete vector network using the attribute table of Link data set. The Link data set consists of polyline features representing the links in the discrete vector network. It includes information about the link ID, IDs of From and To nodes connected to the link, travel cost (correctly measured rather than overestimated owing to the jagged appearance of routes in the raster) along the link, and the ID of the next outgoing link. Details of the algorithm for searching the outgoing links starting from nodes and for identifying the travel costs along links using the Node and Link data sets have been described by Wise (2002).

Figure 4a shows a discrete vector network consisting of seven nodes (N1-N7) and eight directional links (1-8) on a continuous raster surface. The topological relationships among links in the network are managed by the Node and Link data sets, such that a distinction is made in the data sets between a route crossing (as at node N5) and an overpass between links 4 (5) and 7 (8).

The integrated technique examines the travel costs both across the continuous raster surface and along the discrete vector network if the current cell contains one or more nodes. For example, in Figure 4b, the current (gray) cell contains node N1. The technique calculates the travel costs from the current cell to the neighboring cells in the fifth step, and identifies the travel costs from node N1 to N5 along link 1 in the sixth step. The technique can handle several outgoing links starting from nodes in the current cell. In Figure 4c, node N5 in the current cell has three outgoing links in the discrete vector network. Thus, the technique considers both the eight neighboring cells virtually linked to the current cell on the continuous raster surface and the outgoing links 2, 3, and 5 starting from node N5 in the discrete vector network. In contrast, in Figure 4d, node N2 in the current cell has no outgoing links in the discrete vector network; therefore, only the neighboring cells virtually linked to the current cell on the continuous raster surface are used, and there is no sixth step.

In the seventh step, the integrated technique examines the patterns of possible paths traced in the current (gray) cell if this cell has one or more nodes in the discrete vector network (Figure 5). If the paths are traced from the node (s) to the center of the current cell center (as seen in Figure 5) or from the current cell's center to the node(s) (Figure 5c), the technique identifies the egress (access) cost at the node(s) using the attribute table of Node data set and adds to it the travel costs of possible paths calculated in the steps 5 and 6.

In the eighth step, Dijkstra's algorithm is used to calculate the accumulated travel costs from the source cells to unvisited candidate cells using the travel costs determined in the steps 5-7. The unvisited candidate cells include unvisited cells virtually linked to the current cell and those containing the To nodes of the outgoing links starting at the From node in the discrete vector network, if the current cell has the From node. For each unvisited candidate cell, if the accumulated travel cost is less than the previously recorded travel cost, the technique overwrites the previously recorded travel cost with the accumulated travel cost. Once the accumulated travel costs at the unvisited candidate cells have been determined, the technique confirms that the accumulated travel cost is minimized at the current cell, and it marks the current cell as visited. Subsequently, the unvisited candidate cell with the lowest accumulated travel cost is defined as the current cell.

Steps 5 to 8 are repeated from the newly defined current cell until all cells in the grid are marked as visited, and their lowest accumulated travel costs from one of the source cells are confirmed. When these optimization procedures are completed, each cell in the grid has three attributes: (a) the lowest accumulated travel cost, (b) a pointer indicating the direction for tracing the least-cost path, and (c) the ID of each source cell that could be reached with the lowest accumulated travel cost. Following the optimization procedure, the least-cost path from a source cell to a destination cell is traced using the back-link mechanism (Xu and Lathrop 1995).

Applications

Computations of least-cost paths from synthetic data sets

To demonstrate the improvement due to the integrated technique, four different computations were performed using synthetic data sets. For each computation, the Queen's pattern was used to define the move sets on the continuous raster surface because they are widely used in many GIS software packages. The cost function that considers the non-directional travel cost between cells was utilized to make the computations as simple as possible. For the same reason, the cost per unit length was assumed to be 1/m in every cell on the continuous raster surface. More complex cost functions will be considered in the following section. The access and egress costs at each node in the discrete vector network are presented in Table 1.

Figure 6a shows the result of the first computation performed to find the least-cost path across the continuous raster surface with a discrete vector network consisting of four nodes and four directional links. The least-cost path from the source cell S to the destination cell D consists of three segments: (a) from the source cell S to the cell containing node N1 across the continuous raster surface (travel cost = 54.14); (b) from the cell containing node N1 to the cell with node N2 along the directional link in the discrete vector network (access cost at N1 = 2.00, travel cost = 6.00); (c) from the cell containing node N2 to the destination cell D across the continuous raster surface (egress cost at N2 = 3.00, travel cost = 34.14). Therefore, the lowest accumulated travel cost is determined as 99.28.

In the second computation, the least-cost path across the continuous raster surface with a discrete vector network consisting of five nodes and eight directional links was analyzed (Figure 6b). As node N5 was used to represent the junction between directional links, the topological relationships of the discrete network considered in the second computation were distinct from those in the first computation. The least-cost path from the source cell S to the destination cell D was determined to be along the route consisting of four segments with the lowest accumulated travel cost of 91.43.

In the third computation, the directional link from node N4 to node N5 in the discrete vector network was removed so that five nodes and seven directional links were examined. Figure 6c shows the result of this computation. The least-cost path from the source cell S to the destination cell D was determined to lie along the route consisting of four segments: (a) from the source cell S to the cell containing node N1 across the continuous raster surface (travel cost = 54.14); (b) from the cell containing node N1 to the node N5 along the directional link in the discrete vector network (access cost at N1 = 2.00, travel cost = 4.00); (c) from the node N5 to the node N2 along the directional link in the network (travel cost = 2.00); and (d) from the node N2 to the destination cell D across the raster surface (egress cost at N2 = 3.00, travel cost = 34.14). Therefore, the lowest accumulated travel cost of the least-cost path was determined to be 99.28. This cost is higher than that from the second computation because the route along the directional link from node N4 to node N5 was not permitted.

In the fourth computation, the discrete vector network consisting of five nodes and eight directional links with high travel costs was considered. The least-cost path from the source cell S to the destination cell D was determined across the continuous raster surface (Figure 6d). Therefore, the lowest accumulated travel cost (123.14) is the same as the 2D fiat distance from the source cell S to the destination cell D that is constrained to orthogonal links of length 10.00 (m) and diagonal links of length 14.14 (m) in the virtual network of the continuous raster surface. It should be noted that the integrated technique considered possible paths both across the continuous raster surface and along the discrete vector network in the fourth computation; however, only the paths across the continuous raster surface were used as segments of the least-cost path because the travel costs along the links in the discrete vector network are high.

From the results of the synthetic data sets, we can confirm that the integrated technique can find least-cost paths across the continuous raster surfaces with different discrete vector networks. The integrated technique could calculate the travel costs between the cells on the raster surface using the cost function and identify the travel costs between nodes in the discrete network using the ancillary vector data set. Moreover, topological information about the discrete network could be examined during computations.

Computations of least-cost paths from real-world data sets

To demonstrate the integrated technique in a real-world situation, the technique was tested in a small town in South Korea. The study area was 2.8 [km.sup.2] (2000 m x 1400 km) in size, with both an unpaved continuous surface (including forest, farmland, grass, and a lake) and a transportation network consisting of one- and two-way roads and a road tunnel under a mountain (Figure 7). The least-cost paths of an ATV driven across the unpaved continuous surface and along the transportation network were analyzed using the integrated technique.

Three raster data sets with 10 m resolution were created to represent the characteristics of the ATV's movement on the unpaved continuous surface. Figure 7a shows the cost data set, where each cell represents the travel cost (time) per unit length (min/m) of passing through the cell on flat terrain. As the speed of the ATV on the farm (15 km/h) is usually higher than that in the forest (12 km/h), the travel cost per unit length assigned to the farm (0.004 min/m) is less than that assigned to the forest (0.005 min/m). In addition, a value of infinity was assigned to the cells representing the lake because the ATV is unable to traverse a lake. Figure 7b shows the digital elevation model (DEM) created from 1:25,000-scale topographical maps published by Korea's National Geographic Information Institute (http://www.ngi.go.kr). This data set was combined with the graph in Figure 7c to calculate the vertical factor that accounts for the travel cost necessary to overcome the slope of the hilly terrain.

The raster data set representing the predominant horizontal movement of the ATV at each cell is illustrated in Figure 7d. The horizontal factors in Equation (1) were determined by matching the RHMA (i.e., the angle between the predominant horizontal movement of the ATV and the horizontal direction of a possible path) with the horizontal factor graph (Figure 7e).

The transportation network (Figure 7f) was represented by a discrete vector network consisting of 31 nodes (including four junctions) and 53 directional links stored in the Node and Link data sets, respectively. The access and egress costs for each node were determined to be zero since the ATV does not increase the cost when moving between the cell on the continuous raster surface and the node in the discrete vector network. Using these vector data sets, the travel cost for the ATV, measured along each directional link, and the topological information of the network were analyzed by the integrated technique to determine the least-cost paths.

The Queen's anisotropic path considering the discrete vector network

In the first computation, the discrete vector network was used to determine the least-cost path. All factors in the cost function (Equation 1) were considered in order to calculate the travel costs between ceils, and the Queen's pattern was used to define the move sets. Figure 8a shows the least-cost path determined along the following three segments: (a) the Queen's anisotropic path on the continuous raster surface from the source cell to the cell containing the node with the lowest accumulated travel cost of 0.90 min; (b) the path along the discrete vector network including a tunnel; (c) the Queen's anisotropic path on the continuous raster surface from the cell containing the node with the lowest accumulated travel cost of 4.10 min to the destination cell. The lowest travel cost along the least-cost path was determined to be 5.14 min.

The Knight's anisotropic path considering the discrete vector network

The second computation was performed under parameter settings identical to those of the first computation, except that the move sets were defined by the Knight's pattern. As can be seen from Figure 8b, the anisotropic paths on the continuous raster surface are slightly different from those in Figure 8a. The lowest travel cost along the least-cost path was calculated to be 5.07 min, which is somewhat less than that from the first computation, because of the effect of the different move sets.

The Queen's anisotropic path from different source-to-destination cells considering the discrete vector network

In the third computation, the source and destination cells were reversed. Other parameter settings were identical to those in the first computation. Figure 8c shows the least-cost path consisting of five segments: (a) the Queen's anisotropic path on the continuous raster surface from the source cell to the cell containing the node with the lowest accumulated travel cost of 0.71 min; (b) the path along the discrete vector network to the node with the lowest accumulated travel cost of 1.76 min; (c) the Queen's anisotropic path on the continuous raster surface to the cell containing the node with the lowest accumulated travel cost of 6.91 min; (d) the path along the discrete vector network to the node with the lowest accumulated travel cost of 8.65 min; and (e) the Queen's anisotropic path on the continuous raster surface to the destination cell. The least-cost path in the third computation is different from that in the first computation because of the one-way road. Therefore, the total travel cost of 9.40 min along the least-cost path was greater than that in the first computation (i.e., 5.14 min).

The Queen's anisotropic path on the continuous raster surface with a different cell resolution

To examine the effect of cell resolution on the least-cost path, raster data sets with 40 m cell resolution were used in the fourth computation. Other parameter settings were identical to those in the first computation. As seen in Figure 8d, the accumulation of travel costs along the discrete vector network is identical, regardless of the cell resolution. However, the anisotropic paths on the continuous raster surfaces are slightly different from those in Figure 8a. Therefore, we can determine that the integrated technique is somewhat sensitive to the cell resolution of raster data sets representing the continuous raster surface.

Discussion

By applying the integrated technique to the synthetic and real-world data sets, we showed that it could provide credible information related to the least-cost paths across a continuous raster surface with discrete vector networks. However, it should be noted that the method of weighting the distance is critical in many applications, including ATV navigation. Different factors, such as slope and land use, and cost functions can affect the least-cost paths determined with the integrated technique.

The computational cost of integrated technique depends on the number of cells in the continuous raster surface (n1) and that of nodes in the discrete vector networks (n2). Suppose n is the sum of n1 and n2. The integrated algorithm requires O ([n.sup.2]) operations in the worst situation. If a heap data structure is used, it takes O (n log n) operations on average. Since the integrated technique is based on Dijkstra's algorithm which does not unitize any heuristics, it often explores unnecessary search areas both across the continuous raster surface and along the discrete vector networks before the optimization procedures are completed. Although Dijkstra's algorithm is guaranteed to find the least-cost path, it results in relatively high computational cost. In future work, the A* algorithm, one of the most well-known heuristic algorithms, can be implemented in the integrated technique to speed up the search process.

The integrated technique we developed assumes that the object can move freely on a continuous raster surface, and then uses the nodes of a discrete vector network as points for the object to access (or exit) the network. However, this assumption is inappropriate for some applications where the object can access (exit) the discrete vector network at any cell on the continuous raster surface. In the future, it would be interesting to study the possibility of accessing (exiting) the discrete vector network at any cell on the continuous raster surface in order to extend the range of applicability of the integrated technique.

Conclusions

In this study, an integrated technique was developed to analyze least-cost paths across a continuous raster surface with discrete vector networks. The technique determines the least-cost path from a source point to a destination point by considering the characteristics of an object's movement on the continuous raster surface as well as those in the discrete vector networks. Thus, information about the discrete vector networks, such as the travel cost at each link, remote connections between nodes, and the network topology, could be effectively used in conjunction with information for the continuous raster surface to find the least-cost paths.

The integrated technique described in this paper is best suited to ATV navigation where both an unpaved continuous surface and a paved transportation network need to be considered simultaneously to find the least-cost path. In addition, the technique can be utilized to support multimodal transportation planning in construction and mining sites where materials are transported by several different means such as off-road trucks on a continuous surface and rail, pipe or conveyor belt systems along discrete networks. Take for instance the multimodal transportation network in a coal mining site which comprises carriages of coal travelling (a) from a loading point to a stockpile across the continuous surface by off-road trucks, (b) from the stockpile to a mineral processing plant by a conveyor belt system, and (c) from the plant to a coal-shipping port by a rail system. Because the integrated technique can handle both continuous raster surfaces and discrete vector networks, it can be effectively applied to find the least-cost path for such a multimodal transportation system.

A relatively straightforward extension of the current work would involve: (a) the introduction of wide paths (i.e., paths or corridors with a fixed width larger than one cell) on the continuous raster surface, and (b) the development of functions to provide contextual information along least-cost paths, such as the location of landmarks, turning instructions, and details of the general layout of the surrounding area.

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

Acknowledgments

This work was supported by the KETEP grant funded by the Korea Government's Ministry of Trade, Industry and Energy (Project No. 2011201030006B).

References

Choi, Y., and A. Nieto. 2011. "Optimal Haulage Routing of Off-Road Dump Trucks in Construction and Mining Sites Using Google Earth and a Modified Least-Cost Path Algorithm." Automation in Construction 20 (7): 982-997.

Choi, Y., H. D. Park, C. Sunwoo, and K. C. Clarke. 2009. "Multi-Criteria Evaluation and Least-Cost Path Analysis for Optimal Haulage Routing of Dump Trucks in Large Scale Open-Pit Mines." International Journal of Geographical Information Science 23 (12): 1541-1567.

Collischonn, W., and J. V. Pilar. 2000. "A Direction Dependent Least-Cost Path Algorithm for Roads and Canals." International Journal of Geographical Information Science 14 (4): 397-406.

Dijkstra, E. W. 1959. "A Note on Two Problems in Connection with Graphs." Numerische Mathmatik 1: 269-271. Goncalves, A. B. 2010. "An Extension of GIS-Based Least-Cost Path Modelling to the Location of Wide Paths." International Journal of Geographical Information Science 24 (7): 983-996.

Hart, P. E., N. J. Nilsson, and B. Raphael. 1968. "A Formal Basis for the Heuristic Determination of Minimum Cost Paths." 1EEE Transactions on Systems Science and Cybernetics 4 (2): 100-107.

Huang, B., Q. Wu, and F. B. Zhan. 2007. "A Shortest Path Algorithm with Novel Heuristics for Dynamic Transportation Networks." International Journal of Geographical Information Science 21 (6): 625-644.

Lee, J., and D. Stucky. 1998. "On Applying Viewshed Analysis for Determining Least-Cost Paths on Digital Elevation Models." International Journal of Geographical Information Science 12 (8): 891-905.

Saha, A. K., M. K. Arora, R. P. Gupta, M. L. Virdi, and E. Csaplovics. 2005. "GIS-Based Route Planning in Landslide-Prone Areas." International Journal of Geographical Information Science 19 (10): 1149-1175.

Snyder, S. A., J. H. Whitmore, I. E. Schneider, and D. R. Becker. 2008. "Ecological Criteria, Participant Preferences and Location Models: A GIS Approach Toward ATV Trail Planning." Applied Geography 28 (4): 248-258.

Tomlin, D. 2010. "Propagating Radial Waves of Travel Cost in a Grid." International Journal of Geographical Information Science 24 (9): 1391-1413.

Wise, S. 2002. GIS Basics, 514 p. New York: Taylor & Francis.

Xu, J., and R. G. Lathrop. 1995. "Improving Simulation Accuracy of Spread Phenomena in a Raster-Based Geographic Information System." International Journal of Geographical Information Science 9 (2): 153-168.

Yu, C., J. Lee, and M. J. Munro-Stasiuk. 2003. "Extensions to Least-Cost Path Algorithms for Roadway Planning." International Journal of Geographical Information Science 17 (4): 361-376.

Zhan, C., S. Menon, and P. Gao. 1993. "A Directional Path Distance Model for Raster Distance Mapping." In Spatial Information Theory: A Theoretical Basis for GIS, edited by A. U. Frank and I. Campari, 434-443. Berlin: Springer-Verlag.

Yosoon Choi (a)*, Jeong-Gi Um (a) and Myong-Ho Park (b)

(a) Department of Energy Resources Engineering, Pukyong National University, Busan 608-737, South Korea; (b) E&p Technology Institute, Korea National Oil Corporation, Anyang 431-711, South Korea

(Received 3 October 2012; accepted 10 September 2013)

* Corresponding author. Emails: energy@pknu.ac.kr, yspower7@gmail.com

Table 1. Access and egress costs at each node in the discrete  network
shown in Figure 6.

Node ID    Access cost    Egress cost

N1         2              3
N2         4              3
N3         3              2
N4         2              1
N5         2              3
COPYRIGHT 2014 Taylor & Francis Group LLC
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2014 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Choi, Yosoon; Um, Jeong-Gi; Park, Myong-Ho
Publication:Cartography and Geographic Information Science
Article Type:Report
Date:Jan 1, 2014
Words:5294
Previous Article:Communicating climate change: spatial analog versus color-banded isoline maps with and without accompanying text.
Next Article:Mapping and spatial analysis of multiethnic toponyms in Yunnan, China.
Topics:

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