Steven D. Prager
ABSTRACT
In this paper we consider the concept of functional paths through network datasets. Functional paths are paths that may be suboptimal in terms of cumulative edge weight, but in which the morphology of the route may serve a specific functional purpose (e.g., detection avoidance). Such routes may tend toward optimal in terms of minimizing for edge weight, but not at the expense of the functional purpose of the route. We present this class of routing problems and illustrate how evolutionary approaches used in conjunction with more traditional graph-based computation offers a great deal of flexibility in finding feasible solutions. Using both synthetic graphs and real-world road networks, we present a hybrid evolutionary and graph-based approach for discovering routes with specific functional characteristics. The presented evolutionary algorithm represents a novel solution to a challenging class of problems not readily solved by more traditional approaches.
- S. Davis and R. Impagliazzo. Models of greedy algorithms for graph problems. Algorithmica, 54(3):269--317, 2009. Google Scholar
Digital Library
- K. A. De Jong and W. M. Spears. Using genetic algorithms to solve NP-complete problems. In Proceedings of the Third International Conference on Genetic Algorithms, Morgan Kaufmann, 1989. Google ScholarDigital Library
- R. Dechter and J. Pearl. Generalized best-first search strategies and the optimality of A*. J. ACM, 32(3):505--536, 1985. Google ScholarDigital Library
- C. Demetrescu. DIMACS Challenge Benchmarks: Colorado, USA. http://www.dis.uniroma1.it/~challenge9/download.shtml.Google Scholar
- E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1(1):269--271, 1959.Google ScholarDigital Library
- M. Gen, R. Cheng, and D. Wang. Genetic algorithms for solving shortest path problems. In International Conference on Evolutionary Computation, pages 401--406. IEEE, 1997.Google ScholarCross Ref
- M. Gen and L. Lin. Multi-objective hybrid genetic algorithm for bicriteria network design problem. Complexity International, 11:73--83, 2005.Google Scholar
- M. F. Goodchild. An evaluation of lattice solutions to the problem of corridor location. Environment and Planning A, 9(7):727--738, 1977.Google ScholarCross Ref
- P. Hart, N. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics, 4(2):100--107, 1968.Google Scholar
- B. Huang, R. L. Cheu, and Y. S. Liew. GIS and genetic algorithms for HAZMAT route planning with security considerations. International Journal of Geographical Information Science, 18(8):769--787, 2004.Google ScholarCross Ref
- B. Huang, Q. Wu, and F. B. Zhan. A shortest path algorithm with novel heuristics for dynamic transportation networks. International Journal of Geographical Information Science, 21(6):625--644, 2007. Google ScholarDigital Library
- Y. Li, R. He, and Y. Guo. Faster genetic algorithm for network paths. In The 6th International Symposium on Operations Research and Its Applications, (ISORA'06). August, pages 380--389, 2006.Google Scholar
- S. Lin, and B. Kernighan. An Effective Heuristic Algorithm for the Traveling-Salesman Problem. Operations Research, 21:498--516, 1973.Google ScholarDigital Library
- P. Mooney and A. Winstanley. An evolutionary algorithm for multicriteria path optimization problems. International Journal of Geographical Information Science, 20(4):401--423, 2006.Google ScholarCross Ref
- K. O'Grady and L. Godwin. The positional accuracy of MAF/TIGER. Technical report, United States Department of Commerce, Bureau of the Census, 2000.Google Scholar
- W. M. Spears. Evolutionary Algorithms: The Role of Mutation and Recombination. Springer, 2000. Google ScholarDigital Library
Index Terms
- A hybrid evolutionary-graph approach for finding functional network paths
Recommendations
Finding min-sum disjoint shortest paths from a single source to all pairs of destinations
TAMC'06: Proceedings of the Third international conference on Theory and Applications of Models of ComputationGiven a graph G = (V, E) with |V| = n, |E| = m, and a source node s, we consider the problem of finding two disjoint paths from s to two destination nodes t1 and t2 with minimum total length, for every pair nodes t1, t2 ∈ V–{s}. One efficient solution ...
BGP add-paths: the scaling/performance tradeoffs
Special issue title on scaling the internet routing system: an interim reportInternet Service Providers design their network with resiliency in mind, having multiple paths towards external IP subnets available at the borders of their network. However, with the current internal Border Gateway Protocol, BGP routers and route ...
An Algorithm for Dynamic Routing Based on Multi-paths in Wireless Sensor Networks
CSSE '08: Proceedings of the 2008 International Conference on Computer Science and Software Engineering - Volume 03According to the traditional network routing mechanisms, the path with the minimal hops is often chosen to transmit data from source node to destination node. However, frequent communication requests along one path in wireless sensor network result a ...
Comments