Robust Ring-Star Problem

Definition of Ring-Star Problem

对于混合图, 设, 顶点表示depot, 无向边集, 有向边集.

Ring-Star problem分为ring part和star part, 即需要构造一个包括下面两部分的网络:

• ring part: 从 中选出一个子集 作为hub的集合, 用无向边连接选出的所有的hub构成一个cycle. 打开hub 的代价为; 连接hub 和hub 的代价为, 保证depot在中.
• star part: 除了hub以外的顶点作为terminal, 记作 , 保证terminal必须恰好与 中的一个hub使用有向边相连(由terminal指向hub), 对于 , 连接 的代价为. 即构造星型拓扑.

RSP的目的就是最小化构造Ring-Star网络的代价.

上述定义中的“一个terminal必须恰好与一个hub连接”可以推广为 个, 表示 edge-connected, 即每两个terminal之间恰有 条path.

RSP是NP-hard的, 如果assignment cost ring cost, 那么TSP将是RSP的一个特例.

Robust RSP

Robust RSP记作-RSP, 相比RSP增加一个输入表示如果 被选中作为hub, 那么它是不稳定的, 即可能会fail, 于是为了保证网络的健壮性, 需要将不稳定的hub的neighbors相连.

ILP表述

Notation

• 表示连接hub 的花费
• 用来描述不考虑hub的不稳定性时hub之间是否有边相连, 由于hub之间相连构成的子图是一个无向图, 因此约定 .
• 表示是否将terminal 连到hub 上, 保证 .
• 为 是表示结点 为termianl, 为 表示结点 是 hub.
• 表示考虑hub的不稳定时, 若 , 则 , 否则为 .

下面是问题的ILP描述: 下面一一叙述优化问题的约束条件:

• 首先需要保证所有的hub恰好形成一个环, 于是每个hub的度数应恰好为 , 于是对任意 , 都有
• 保证最终的RS网络只有一个hub形成的环, 而不会出现孤立的环, 考虑subtour elimination, 对任意 的子集 , 有 , 但是如果所有的hub都在 里. 那么上述约束的和式可以取到 , 考虑将不等式右边的 改为 , 于是得到最终的subtour elimination: . 在实际问题中hub和terminal的数量应合理, 这里设置成 .
• 保证每个terminal要么与一个稳定的hub连接, 要么与两个不稳定的hub连接, 于是对任意结点 都有 . 上个式子保证了如果结点 是hub则 则对任意 都有 .
• 由于最小的环需要有三个边, 且若存在不稳定的hub, 则最终的RS网络的hub形成的子图应至少有4条边, 于是设置一个 , 那么有 其中 .
• 与同一个不稳定的hub相连的两个hub需要增加一条边来确保稳定性, 对 , , 若 都与 相连, 则应有 , 于是 .
• 不需要将任何terminal或者hub连接terminal上, 于是 . 这保证了若 即结点 为terminal, 则 .
• 还有其他简单的约束, 包括将第一个点作为depot: , 以及各个变量为01变量的约束.

使用Benders Decomposition

子问题的对偶问题

一个算法