Advanced

Multi-objective optimisation algorithms for GIS-based multi-criteria decision analysis : an application for evacuation planning

Diaz Gonzalez, Jose Ignacio LU (2016) In Lund University GEM thesis series NGEM01 20161
Dept of Physical Geography and Ecosystem Science
Abstract
Geographic Information Systems (GIS) have acquired greater relevance as tools to support decision-making processes, and during the last decades they have been used in conjunction with Multi-Criteria Decision Analysis techniques (GIS-MCDA) to solve real-world spatial problems. GIS-MCDA can be generally divided in Multi-Attribute and Multi-Objective techniques. Until now most of the applications of GIS-MCDA have been focused only on using the Multi-Attribute approach, and less than 10% of the research has been related to a specific type of Multi-Objective technique: the use of heuristic algorithms.

The present study explores how different heuristic methods solve a spatial multi-objective optimisation problem. To achieve this, four... (More)
Geographic Information Systems (GIS) have acquired greater relevance as tools to support decision-making processes, and during the last decades they have been used in conjunction with Multi-Criteria Decision Analysis techniques (GIS-MCDA) to solve real-world spatial problems. GIS-MCDA can be generally divided in Multi-Attribute and Multi-Objective techniques. Until now most of the applications of GIS-MCDA have been focused only on using the Multi-Attribute approach, and less than 10% of the research has been related to a specific type of Multi-Objective technique: the use of heuristic algorithms.

The present study explores how different heuristic methods solve a spatial multi-objective optimisation problem. To achieve this, four algorithms representing different types of heuristics were implemented, and applied to solve the same problem related with an evacuation planning situation. The implemented algorithms were Standard Particle Swarm Optimisation (SPSO), Non-dominated Sorting Genetic Algorithm II (NSGA-II), Archived Multi-Objective Simulated Annealing (AMOSA) and Multi-Objective Grey Wolf Optimiser (MOGWO).

The results show that the four algorithms were effective on solving the given problem, although in general AMOSA and MOGWO had a higher performance in terms of number of solutions, effectiveness of the optimisation, diversity, execution time and repeatability. However, the differences in the results were not clear enough to state that one type of heuristic is superior than others. Since AMOSA and MOGWO are the most recent algorithms among the implemented ones, they include several improvements achieved by the latest research, and their superior performance could be linked to these improvements more than to the specific type of algorithms they belong to.

Further research is suggested to explore the suitability of these methods for many-objectives spatial problems, to consider the variability and dynamism of real-world situations, to create a standard set of algorithms to be used for benchmarking, and to integrate them with the currently available GIS-MCDA tools. Despite this, from the performed research it is possible to conclude that heuristics methods are reliable techniques for solving spatial problems with multiple and conflictive objectives, and future research and practical implementations in this field can strengthen the capacities of GIS as a multi-criteria decision-making support tool. (Less)
Popular Abstract
Geographic Information Systems (GIS) have acquired greater relevance as tools to support decision-making processes, and during the last decades they have been used in conjunction with Multi-Criteria Decision Analysis techniques (GIS-MCDA) to solve real-world spatial problems. GIS-MCDA includes several techniques and methods and one of the less studied branches is about using a type of computer programs called “heuristic algorithms” to solve the problems.

The present study explores how four different types “heuristic algorithms” solve a spatial problem related with an evacuation planning situation, where two main aspects need to be simultaneously optimised: the overall distance walked by people during the evacuation and the rate of use... (More)
Geographic Information Systems (GIS) have acquired greater relevance as tools to support decision-making processes, and during the last decades they have been used in conjunction with Multi-Criteria Decision Analysis techniques (GIS-MCDA) to solve real-world spatial problems. GIS-MCDA includes several techniques and methods and one of the less studied branches is about using a type of computer programs called “heuristic algorithms” to solve the problems.

The present study explores how four different types “heuristic algorithms” solve a spatial problem related with an evacuation planning situation, where two main aspects need to be simultaneously optimised: the overall distance walked by people during the evacuation and the rate of use of the safe areas where people is allocated. The name of the implemented algorithms are Standard Particle Swarm Optimisation (SPSO), Non-dominated Sorting Genetic Algorithm II (NSGA-II), Archived Multi-Objective Simulated Annealing (AMOSA) and Multi-Objective Grey Wolf Optimiser (MOGWO).

The results show that the four algorithms were effective on solving the given problem, although in general AMOSA and MOGWO had a higher performance in terms of quality and quantity of their solutions. However, the differences in the results were not clear enough to state that one type of heuristic is superior than others. Since AMOSA and MOGWO are the most recent algorithms among the implemented ones, they include several improvements achieved by the latest research about this topic, and their superior performance could be linked to these improvements more than to the specific type of algorithms they belong to.

Further research is suggested to explore the suitability of these methods to solve more complex spatial problems and to consider the variability and dynamism of real-world situations. Despite this, from the performed research it is possible to conclude that heuristics algorithms are reliable techniques for solving spatial problems with multiple, simultaneous and conflictive objectives, and future research and practical implementations in this field can strengthen the capacities of GIS as a multi-criteria decision-making support tool. (Less)
Please use this url to cite or link to this publication:
author
Diaz Gonzalez, Jose Ignacio LU
supervisor
organization
course
NGEM01 20161
year
type
H2 - Master's Degree (Two Years)
subject
keywords
decision-making, decision analysis, optimisation algorithm, multi-objective, multi-criteria, GIS, geography, physical geography, SPSO, NSGA-II, AMOSA, MOGWO, GEM
publication/series
Lund University GEM thesis series
report number
11
language
English
id
8884112
date added to LUP
2016-06-22 16:32:49
date last changed
2016-06-30 21:59:22
@misc{8884112,
  abstract     = {Geographic Information Systems (GIS) have acquired greater relevance as tools to support decision-making processes, and during the last decades they have been used in conjunction with Multi-Criteria Decision Analysis techniques (GIS-MCDA) to solve real-world spatial problems. GIS-MCDA can be generally divided in Multi-Attribute and Multi-Objective techniques. Until now most of the applications of GIS-MCDA have been focused only on using the Multi-Attribute approach, and less than 10% of the research has been related to a specific type of Multi-Objective technique: the use of heuristic algorithms.

The present study explores how different heuristic methods solve a spatial multi-objective optimisation problem. To achieve this, four algorithms representing different types of heuristics were implemented, and applied to solve the same problem related with an evacuation planning situation. The implemented algorithms were Standard Particle Swarm Optimisation (SPSO), Non-dominated Sorting Genetic Algorithm II (NSGA-II), Archived Multi-Objective Simulated Annealing (AMOSA) and Multi-Objective Grey Wolf Optimiser (MOGWO).

The results show that the four algorithms were effective on solving the given problem, although in general AMOSA and MOGWO had a higher performance in terms of number of solutions, effectiveness of the optimisation, diversity, execution time and repeatability. However, the differences in the results were not clear enough to state that one type of heuristic is superior than others. Since AMOSA and MOGWO are the most recent algorithms among the implemented ones, they include several improvements achieved by the latest research, and their superior performance could be linked to these improvements more than to the specific type of algorithms they belong to.

Further research is suggested to explore the suitability of these methods for many-objectives spatial problems, to consider the variability and dynamism of real-world situations, to create a standard set of algorithms to be used for benchmarking, and to integrate them with the currently available GIS-MCDA tools. Despite this, from the performed research it is possible to conclude that heuristics methods are reliable techniques for solving spatial problems with multiple and conflictive objectives, and future research and practical implementations in this field can strengthen the capacities of GIS as a multi-criteria decision-making support tool.},
  author       = {Diaz Gonzalez, Jose Ignacio},
  keyword      = {decision-making,decision analysis,optimisation algorithm,multi-objective,multi-criteria,GIS,geography,physical geography,SPSO,NSGA-II,AMOSA,MOGWO,GEM},
  language     = {eng},
  note         = {Student Paper},
  series       = {Lund University GEM thesis series},
  title        = {Multi-objective optimisation algorithms for GIS-based multi-criteria decision analysis : an application for evacuation planning},
  year         = {2016},
}