Int. Arch. Photogramm. Remote Sens. Spatial Inf. Sci., XXXIX-B2, 157-159, 2012
https://doi.org/10.5194/isprsarchives-XXXIX-B2-157-2012
© Author(s) 2012. This work is distributed under
the Creative Commons Attribution 3.0 License.
 
27 Jul 2012
MULTI-CRITERIA PATH FINDING
E. Mohammadi and A. Hunter Geomatics Department, Schulich School of Engineering, University of Calgary, 2500 University Drive NW, Calgary, Alberta, Canada T2N 1N4
Keywords: GIS, Analysis, Network, Databases, Query, Parameters Abstract. Path finding solutions are becoming a major part of many GIS applications including location based services and web-based GIS services. Most traditional path finding solutions are based on shortest path algorithms that tend to minimize the cost of travel from one point to another. These algorithms make use of some cost criteria that is usually an attribute of the edges in the graph network. Providing one shortest path limits user's flexibility when choosing a possible route, especially when more than one parameter is utilized to calculate cost (e.g., when length, number of traffic lights, and number of turns are used to calculate network cost.) K shortest path solutions tend to overcome this problem by providing second, third, and Kth shortest paths. These algorithms are efficient as long as the graphs edge weight does not change dynamically and no other parameters affect edge weights. In this paper we try to go beyond finding shortest paths based on some cost value, and provide all possible paths disregarding any parameter that may affect total cost. After finding all possible paths, we can rank the results by any parameter or combination of parameters, without a substantial increase in time complexity.
Conference paper (PDF, 699 KB)


Citation: Mohammadi, E. and Hunter, A.: MULTI-CRITERIA PATH FINDING, Int. Arch. Photogramm. Remote Sens. Spatial Inf. Sci., XXXIX-B2, 157-159, https://doi.org/10.5194/isprsarchives-XXXIX-B2-157-2012, 2012.

BibTeX EndNote Reference Manager XML