Premium
A MORE EFFICIENT HEURISTIC FOR SOLVING LARGE P ‐MEDIAN PROBLEMS
Author(s) -
Densham Paul J.,
Rushton Gerard
Publication year - 1992
Publication title -
papers in regional science
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.937
H-Index - 64
eISSN - 1435-5957
pISSN - 1056-8190
DOI - 10.1111/j.1435-5597.1992.tb01849.x
Subject(s) - heuristic , computation , implementation , vertex (graph theory) , mathematical optimization , computer science , algorithm , mathematics , theoretical computer science , graph , programming language
The Teitz and Bart (1968) vertex substitution heuristic is more robust than competing algorithms and yields solutions with properties that are necessary, but not sufficient, for a global optimum solution. All documented implementations of this algorithm, however, use a naive spatial search procedure, whereas a more informed spatial search procedure, requiring considerably less computation to solve any given problem, is possible. An algorithm incorporating this new search procedure, called the global/regional interchange algorithm, is described. As problem size increases, proportionally larger reductions in processing costs occur.