Last April, Prof. Fernando Sanchez-Trigueros took part in the GeoAI and Deep Learning Symposium, which was part of the 2019 Annual Meeting of the American Association of Geographers.

With a presentation entitled "Evolving three genetic algorithms to solve a multiple knapsack optimization problem with allocation frictions", Prof. Sanchez-Trigueros demonstrated the use of Genetic Algorithms to spatial optimization problems aiming to maximize the spatial accessibility to services with minimal reallocation costs. Maximizing spatial accessibility to services puts the emphasis on the benefits gained by reducing the travel costs of potential demand to use available supply. If this cost reduction on the user end requires reallocating services in a way that generates relocation costs on the supplier end, however, the net worth of maximizing accessibility diminishes with implementing the reallocation, which could eventually compromise the economic sustainability of the solution implemented. In cases where benefits are to remain above a viability floor, therefore, minimizing reallocation costs becomes a key objective to maximize the profits expected from the reallocation.

To solve this optimization problem, a Prof. Sanchez-Trigueros has designed a multiple knapsack heuristic with a genetic algorithm that allocates services to supply sites. In this design, alternative allocations are represented in a chromosomal form and fitness of the solutions are a function of the global accessibility they could generate (to be maximized) and the relocation costs they would require (to be minimized). The model presumes that both potential demand and suppliers aim to minimize travel and relocation costs, so such costs are computed with the Dijkstra’s least-cost path algorithm. Multiobjective fitness is measured as proximity of a solution to the utopian point in a Pareto field.

The algorithm was demonstrated to explore alternative plans for optimal accessibility to public library services by pedestrian users in the City of Alicante, Spain. Additionally, the example demonstrated the Two-Step Floating Catchment Area (2SFCA) method with graph-based distances, to take account of potential competition among users that access  services across the transportation network. Algorithm performance has been assessed for several mutation rates, several sizes of the chromosomal population, and three survival rules (full replacement, ranking, or tournament), as regards runtime and the algorithm's capacity to summarize the space of feasible solutions.