| 摘要 |
Minimum cost networks, such as cellular networks, able to supply k-fold coverage to users, are obtained by defining potential network elements having cost and coverage parameters, and selecting from these available network elements using an iterative approximation method or system that first constructs a k-set coverage formulation incorporating the cost and coverage parameters of the available network elements, and then finds an optimal solution to the k-set coverage formulation using applications of GRASP (greedy randomized adaptive search procedure) and path-relinking heuristics. In one version, GRASP and path-relinking start from a random choice of a network element and build feasible solutions using greedy construction, local search and path-relinking heuristics that are iteratively applied to find an approximate solution. In a second version, a Lagrangian relaxation formulation of the k-set coverage formulation is solved with iterative subgradient optimization methods, and a Lagrangian heuristic that finds a feasible solution at each iteration of the subgradient optimization method, to modify the subgradient optimization and find an approximate feasible solution. The Lagrangian heuristic may be a greedy construction heuristic applied at each iteration of the subgradient optimization method, or may be a GRASP with path-relinking heuristic applied at each iteration of the subgradient optimization method to find an approximate feasible solution. The approximate solutions to the k-set coverage formulation are then used to select at least some of the potential network elements for use in a minimum cost network. The method and system may be software or hardware implementations of conventional computer equipment enabling good approximate solutions to be obtained in reasonable times.
|
