邱 恋，李秦伟

0 引 言

设站问题是网络规划过程中的关键问题，不仅影响用户的通信质量，而且影响运营商的运营利润。网络规划过程中的设站问题，实质是从多个候选基站中选择既满足通信质量要求又能使运营商设站成本最低的一组若干个基站。

1 通信网规划简介

通信网络规划的目标，是在要提供业务的区域里，根据所要保证的业务、所要支持的业务量、所需服务的用户数量，通过采用一系列理论分析、工具仿真与预测，获得支持相应用户数量所需的网络设备的数量、配置和部属地点[1]，以供核算网络投资，并为未来的工程设计提供参考。下面以WCDMA系统的网络规划为例进行说明。

无线网络规划是WCDMA系统走向商用的关键工作，直接影响网络建设成本、网络容量、服务质量以及设备性能的发挥。WCDMA无线网络规划的工作分为初步规划和详细规划两阶段[2]。初步规划的结果通常是对网络规模有一个数量上的认识，而基站站址选择则是详细规划的重要内容[3]。

通信网规划中，设站问题的关键主要有两个：一是所需站的数量，二是站点设置的位置。如何确定站点数量和站点对应设置位置，可归类为组合优化问题。

组合优化问题可以用一个包含三个参数的关系式表示即(D,F,f)，其中D表示决策变量的定义域，设站问题中相当于需要规划的区域；F表示可行解区域，设站问题中相当于候选站址集合，F中的任何一个元素称为该问题的可行解；f表示目标函数，设站问题中等同于满足基站建站成本和满足通信质量要求的代价函数。……