Genetic-algorithm-based path optimization methodology for spatial decision

Liang Yu; Fuling Bian

doi:10.1117/12.713022

28 October 2006 Genetic-algorithm-based path optimization methodology for spatial decision

Liang Yu, Fuling Bian

Proceedings Volume 6420, Geoinformatics 2006: Geospatial Information Science; 64201M (2006) https://doi.org/10.1117/12.713022
Event: Geoinformatics 2006: GNSS and Integrated Geospatial Applications, 2006, Wuhan, China

Abstract

In this paper, we proposed a method based on GA to solve the path-optimization problem. Unlike the traditional methods, it considers many other factors besides the road length including the task assignment and its balance, which are beyond the capability of path analysis and make this problem a Combinatorial Optimization problem. It can't be solved by a traditional graph-based algorithm. This paper proposes a new algorithm that integrates the Graph Algorithm and Genetic Algorithm together to solve this problem. The traditional Graph-Algorithm is responsible for preprocessing data and GA is responsible for the global optimization. The goal is to find the best combination of paths to meet the requirement of time, cost and the reasonable task assignment. The prototype of this problem is named the TSP (Traveling Salesman Problem) problem and known as NP-Hard Problem. However, we demonstrate how these problems are resolved by the GA without complicated programming, the result proves it's effective. The technique presented in this paper is helpful to those GIS developer working on an intelligent system to provide more effective decision-making.

Citation Download Citation

Liang Yu and Fuling Bian "Genetic-algorithm-based path optimization methodology for spatial decision", Proc. SPIE 6420, Geoinformatics 2006: Geospatial Information Science, 64201M (28 October 2006); https://doi.org/10.1117/12.713022

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available