Evolving a genetic algorithm to solve a multiple knapsack optimization problem with allocation frictions, and its application to maximizing spatial accessibility to services with minimal reallocation costs

Authors: Fernando Sanchez-Trigueros*, University of Arizona - Geography & Development
Topics: Quantitative Methods, Spatial Analysis & Modeling, Urban and Regional Planning
Keywords: spatial accessibility, competition, two-step floating catchment area, multiple knapsack optimization, Pareto optimization, genetic algorithms, transport geography
Session Type: Paper
Day: 4/4/2019
Start / End Time: 5:00 PM / 6:40 PM
Room: Capitol Room, Omni, East
Presentation File: No File Uploaded


Maximizing spatial accessibility to services puts the emphasis on the benefits gained by reducing the travel and transport costs of potential demand to use available supply. If this reduction requires reallocating services in a way that generates relocation costs, however, the net worth of maximizing accessibility diminishes with implementing the reallocation, which could eventually compromise the economic sustainability of the solution. In cases where benefits are to remain above a sustainability floor, consequently, minimizing reallocation costs becomes a key objective to maximize the profits expected from the reallocation. To solve this optimization problem, a multiple knapsack heuristic is designed with a genetic algorithm that represents alternative allocations of services to supply points in a genotypic form, coupled with a single-linkage iterator that computes the minimal cost of transferring services across a transport network when replacing preexisting distributions of services with alternative allocation patterns. Genotype evolution includes a “fragmentation, bottleneck, colonization and speciation” mechanism that helps the algorithm explore the space of feasible solutions by splitting up homogeneous genotype populations. The algorithm is demonstrated by modeling alternative plans for optimal access to public library services by potential users that travel across the City of Alicante pedestrian network (Spain). Additionally, the example adapts the Two-Step Floating Catchment Area (2SFCA) index to network distances, to take account of competition on accessing limited services across the built environment. Algorithm performance is assessed for several geodatabase sizes and parameter specifications with regard to runtime and the algorithm's capacity to summarize the space of feasible solutions.

Abstract Information

This abstract is already part of a session. View the session here.

To access contact information login