一种求解带宽限制的中位问题的启发式算法∗

陈丽丰 金 忠

（南京理工大学计算机科学与工程学院 南京 210094）

1 引言

设施选址问题是一类被广泛研究的组合优化的问题，此类问题在物流运输、规划设计、运筹管理等领域都有广泛的应用［1］。问题的模型一般是在给定的网络拓扑图上，从候选设施集中选择一部分设施点构成设施集，将需求点与设施点相连接，并使两者之间的连接代价可能小。设施选址问题大部分是NP-hard 问题，因此一般采用启发式算法在有限的时间计算得到近似解作为结果，常用于设施选址问题的启发式算法有禁忌搜索算法、蚁群算法、局部搜索算法、遗传算法［2～3］和模拟退火算法［4～5］等。设施选址问题主要有三大研究分支，即覆盖问题、中位问题和中心问题。其中，中位问题是一类典型的NP-hard［6］的设施选址问题，由Hakimi［7］最早提出，其假设每个节点既是需求点也是设施候选点，对于给定设施数P，目标是求取所有需求点到所分配设施的平均权重距离最小。由于其模型较为简单，也有许多学者研究了添加了限制条件的中位问题，如动态P 中位问题［8］，条件中位问题［9～10］，可靠中位问题［11～12］等。

2 带宽限制的中位问题

本文研究的问题是结合了费用流问题的中位问题，即带宽限制的中位问题。该问题对网络图中的每条边都添加了带宽的限制，每个需求点都需求一定量的流量，设施点能通过到需求点的一系列边连接成的路径向需求点传输流量，但每条边传输的流量不能超过其带宽上限。

设网络图G=(V，E，I，J，u，c，f)，V 为点集，E为边集，I 为设施候选点集合，J 为需求点集合，且有I ⊆V ，J ⊆V ，I ∩J=∅，uij和cij分别表示边(i，j)的带宽和费用，若(i，j)∉E ，则uij=0，fi表示点vi的需求流量，若vi∉J ，则fi=0，w 表示设施费用。当设施集S ⊆I 及各边的流量消耗u*确定时，则可以得到该方案的费用W 。

带宽限制的中位问题的模型如下：

式（1）为费用函数，包括总设施费用和总路径费用，总设施费用为设施费用w 与设施个数 ||S 之积，总路径费用为每条边的流量消耗与边的单位费用积的总和。式（2）表明每条边的流量消耗不能超过其带宽上限。式（3）表明了对于非需求点，若其不是S 中的元素，则输向该点的流量必须等于该点输出的流量。式（4）表明输向需求点的流量与需求点输出的流量之差必须等于其需求量。

由于当设施集S 确定后，该问题转化为最小费用流问题，用最小费用流算法［13］能得到唯一的路径总费用最小值。因此可以把式（1）看成一个基于S的函数W(S)，即式（1）改写为

最小费用流算法是一种计算最小费用流问题的算法。该算法引入了反向边和残余网络，算法思想是每次选择当前网络图中源点到汇点的最短通路传输流量，直到达到满流或无法再找出这样的通路，并且每次传输的流量不超过通路上的任意边。若传输的流量为u*，对于通路上的所有边(i，j)，其带宽uij减少u*，其反向边的带宽uji增加u*，带宽发生变化后的网络图即为残余网络，且后续的算法将在残余网络上继续迭代。

3 基于广义需求点思想的带宽限制的中位问题的启发式算法

3.1 广义需求点思想

在用启发式算法求解设施选址问题的过程中，会运用领域搜索的方法［14］尝试对当前的解进行转变，邻域即为与当前设施集仅有一个元素差异的设施集。对于给定的设施集S ，为了方便描述，令S-为比S 少一个元素的设施集，S+为比S 多一个元素的设施集。

在邻域搜索中，由于可行解需要用最小费用流算法才能得到其费用，而最小费用流算法求解的时间花费难以接受。但是如果新的设施集是当前设施集的邻域，就意味着两者用最小费用流对应的残余网络是非常相似的。因此，可以尝试通过对当前设施集的残余网络进行转变得到邻域的残余网络。具体方法为通过将某些设施点视为广义的需求点，并用其它设施点对其传输流量，以此得到邻域的最小费用流。由于传输的流量一般来说非常少，而费用流算法的时间花费与总需求流量成正比，因此这种方法的时间花费是远远少于直接计算费用流的。

3.2 广义需求点思想求解邻域的最小费用流

3.2.1 理论证明

由文献［15］可知，在残余网络图中若不存在负环路，则当前的费用流为最小费用流。因此当得到了当前设施集的最小费用流的残余网络，通过计算广义需求点的费用流问题时，需要对增流的路径进行选择，使得达到满流后的残余网络中依然不存在负环路。为了确定增流的路径，首先需要证明一个引理。

引理：在残余网络中若不存在负环路，选择设施点到需求点的最短路径进行增流，则增流后的残余网络也不存在负环路。

证明：假设图G=(V，E，s，t，u，c，f) 不存在负环路，对G 中从s 到t 的最短路L 进行增流后的残余网络图为G'，且G'中存在负环路C 。不失一般性，假设C 的环路不会经过重复的点（若负环路经过重复的点，则一定可以拆分出一个不经过重复点的负环路）。易知，C 至少经过L 中的2个点。

设L 的路径为(a1，a2，…，al)，∀0 ＜i ＜j ＜l ，定义Dai，aj为沿着L 从ai到aj的距离，另外定义Daj，ai=-Dai，aj。此时根据定义，给定任意3 个不大于l 的正整数i，j，k ，有：

设C 沿着其环路的方向经过L 上的点的序列为(b1，b2，…，bc)，且C 上从bc到b1的路径不经过L，定义映射关系φ(i)，使：∀0 ＜i ≤c，∃0 ＜j ≤l ，且bi=aj，并使φ( )i =j。由于C 不经过重复的点，故φ(i)为单射。另外，定义dbi，bj为沿着C 从bi到bj的距离。

对 于 给 定 的 正 整 数 i ＜c ，则 bi=aφ(i)，bi+1=aφ(i+1)，此时有：

若φ( i )＜φ( i +1) ，则：

当φ( i )+1 ＜φ( i +1) 时，由于C 中bi到bi+1的路径不经过L 中除这两点之外的其他点，因此这段路径在对L 增流之前就存在，由于L 是最短路径，因此有dbi，bi+1≥Daφ(i)，aφ(i+1)。

当φ( i )+1=φ(i +1) 时，即L 中从aφ(i)到aφ(i+1)的路径为一条边，若C 中从bi到bi+1的路径也为这 条 边，则 有 dbi，bi+1=Daφ(i)，aφ(i+1)，否 则 同 理 有dbi，bi+1≥Daφ(i)，aφ(i+1)。

因此，当φ( i )＜φ( i +1) 时，有dbi，bi+1≥Daφ(i)，aφ(i+1)。若φ( i )＞φ( i +1) ，则：

当φ( i )＞φ( i +1) +1时，同理可知C 中bi到bi+1的路径在对L 增流之前就存在，且该路径与L 中从aφ(i+1)到aφ(i)的路径构成了环路。由于对L 增流前的残余网络不存在负环路，因此dbi，bi+1+Daφ(i)，aφ(i+1)≥0。

当φ( i )=φ( i +1) +1 时，即L 中从aφ(i+1)到aφ(i)的路径为一条边，若C 中从bi到bi+1的路径为这条边的反向边，则有dbi，bi+1+Daφ(i)，aφ(i+1)=0，否则同理有dbi，bi+1+Daφ(i)，aφ(i+1)≥0。

因 此 ，当 φ( i )＞φ( i +1) 时 ，有 dbi，bi+1+Daφ(i)，aφ(i+1)≥0，即dbi，bi+1≥Daφ(i)，aφ(i+1)。

综上可得，有：

根据式（6）、（7），且C 为负环路，有：

根据式（8）、（9）可得：

由于C 中从bc到b1的路径在对L 增流前就存在。若φ(1)＞φ(c)，则该路径和L 中从aφ(1)到aφ(c)的路径构成了环路，由式（10）得，该环路为负环路，而对L 增流前的残余网络中不存在负环路，因此矛盾。若φ(1) ＜φ(c)，由于L是最短路，因此有Daφ(c)，aφ(1)≤dbc，b1，因此和式（11）存在矛盾。

由反证法可知，引理得证。

3.2.2 计算S+的最小费用流

设S+相比S 增加的设施点为vk，S 的最小费用流的残余网络为G'。易知S+的最小费用流的费用必定小于S ，否则vk的存在就没有意义，因此可以把vk视为一个减小当前残余网络的费用的设施点。因为G'同样对应S+的可行费用流，所以只需要考虑如何利用vk减少路径费用。在G'通过vk向S 的元素的费用为负的通路传输流量，可以使路径费用减小，并最终得到S+的最小费用流。

vk到其它设施点的负费用通路可能有很多，可以采用贪心的思想，每次选择所有通路中费用最小的进行增流。可以证明最终得到残余网络一定对应S+的最小费用流。由于G'对应S 的最小费用流，由文献［15］的结论可以知道，G'中不含有费用为负的环路，而将vk加入设施集的行为可以视为在G'中添加了由总源点连向vk的边。若G'不对应S+的最小费用流，那么可知正是这条边使图中产生了负环路，即所有的负环路均经过这条边。而由引理可知，当无视这条边的存在时，对vk到广义需求点的最短路径传输流量，并不会使原本不存在负环路的G'在增流后产生负环路。因此，增流后的残余网络依然保持所有负环路经过总源点连向vk的边这条性质，而这种增流行为会使这种性质的负环路逐渐减少，直至消失，即得到S+的最小费用流。

3.2.3 计算S-的最小费用流

与计算S+的最小费用流不同的是，S 的最小费用流不是S-的可行费用流，那么需要对残余网络进行调整，使其转变为S-的可行费用流。从约束式的角度来看，需要在满足其它约束式保持成立的条件下，使得式（3）也对S-成立。设S-相比S缺少的元素为vk，从广义需求点的思想来看，需要将vk视为需求点，需求的流量为其原本输出的流量，并用S-的设施点对vk传输流量，使其达到满流。由引理可知，在不存在负环路的残余网络中，每次选择从S-的设施点到vk的最短路进行增流，则增流后的残余网络中依然不存负环路。因此当vk达到满流后，此时的残余网络即为S-的最小费用流。

3.3 基于广义需求点思想的启发式算法

给定图G=(V，E，I，J，u，c，f)，及可行解S ，首先用基于spfa 最短路算法［16］的最小费用流算法得到S 的最小费用流对应的残余网络G'。则算法分为2个步骤交替进行。

1）贪心步骤。将设施候选集I 的元素随机排列并遍历，设当前的设施候选点为vk，当vk∈S 时，在G'上计算S-=S-{vk}的最小费用流，得到的残余网络为G'-，若S-为可行解，且W( )S-＜W(S)，则接受改动；当vk∉S 时，在G'上计算S+=S+{vk}的最小费用流，得到的残余网络为G'+，若W( )S+＜W(S)，则接受改动。若接受改动，则直接用G'-或者G'+作为当前的残余网络。

2）退火步骤。将当前的设施集S 里的元素随机排列并遍历，设当前的设施点为vk，以随机的顺序遍历与vk连接的点。设连接的点为vj，在G'上用广义需求点思想计算S+=S+{vj}的最小费用流，得到的残余网络为G'+。然后在G'+上用广义需求点思想计算S+-=S+-{vk}的最小费用流，得到的残余网络为G'+，若S+-是可行解且W(S+-)＜W(S)，则接受改动；若S+-是可行解且W(S+-) ≥W(S)，则依据两者的差距和当前的退火温度以一定概率接受改动。接受改动的操作同于贪心步骤。

在退火步骤中，S+-被接受的概率为

在第t 轮的退火温度T 的设定如下：

4 实验结果与分析

本节实验的数据集来自华为软件精英挑战赛，数据集总共包含9 个样例，每个样例均为由800 个设施候选点与360 个需求点组成的网络图，平均边数约为3000 条。此外，每个设施候选点仅与一个设施候选点连接，连接的边的费用为0，且带宽为其需求流量。

在本文的实验中，设置设施费用w=400，算法中退火步骤的初始退火温度T0=0.5，初始解为所有设施点候选点构成的集合。此外，每个样例均限定150s 的时间，并用模拟退火算法和遗传算法作为对比。实验结果如表1所示。

表1 9个样例可行解的费用对比

可以看出，在相同的时间限定内，本文的算法在9 个样例上均得到了比传统的启发式算法更好的解，解的费用相比两种启发式算法减少了500～1500，这说明本文的算法有着明显优于传统启发式算法的性能。

5 结语

本文提出了一种基于广义需求点思想的启发式算法，通过设施点之间流量传输的方法，大幅度提高了邻域最小费用流的计算速度，这使得算法在有限的时间能进行更多次的搜索。实验证明，在带宽限制的设施选址问题的求解上，本文的方法相较于传统用于求解设施选址问题的启发式算法有着更好的寻优性能。但是算法缺少筛选较优邻域的方法，因此是以遍历的方式搜索邻域，这使得算法会在一些较差的邻域上花费较多无用的时间，因此本文的算法仍有改进空间。