European Journal of Operational Research · 1996 · 216 citations · 12 references
ComputingComputer ScienceHigh-performance ComputingAlgorithmsFacility LocationOptimizationCombinatorial OptimizationHeuristic OptimizationHeuristic SearchNetwork OptimizationCovering ProblemsHeuristic AlgorithmsHeuristic ComputationLocation-allocation ProblemsLower BoundsMaximal Covering Location ModelMaximal Covering Location ProblemUpper Bounds
We develop a Lagrangean heuristic for the maximal covering location problem. The heuristic employs a vertex‑addition/substitution upper‑bound routine and a subgradient optimization lower‑bound routine, was tested on networks up to 150 vertices on an IBM 3090‑600J super‑computer, and kept maximum CPU time below three minutes. A duality gap remained at the end of the heuristic for the larger problems.
We develop a Lagrangean heuristic for the maximal covering location problem. Upper bounds are given by a vertex addition and substitution heuristic and lower bounds are produced through a subgradient optimization algorithm. The procedure was tested in networks of up to 150 vertices. A duality gap was generally present at the end of the heuristic for the larger problems. The test problems were run in an IBM 3090-600J ‘super-computer’; the maximum computing time was kept below three minutes of CPU.
12
Computer Solutions of the Traveling Salesman Problem
Shen Lin · Bell System Technical Journal · 1965 · 2K citations