本文讨论了有向超图嵌入路问题和恢复鲁棒带惩罚费用呼叫控制问题。(1)有向超图嵌入路问题可以简单描述如下:给定一个双向路和有向超图,对于双向路中任意一条弧都含有一个权重,超图中任意一条有向超边都含有一个需求和惩罚费用,这里任意一条有向超边可以选择接受或者拒绝,若有向超边被拒绝,则产生惩罚费用,否则,有向超边所经过的双向路中每一条弧上都产生需求,双向路中任意一条弧的负载是指在该弧上产生的所有需求之和与该弧权重的乘积。该问题的目标是寻找一个被接受的有向超边子集合,使得双向路上最大负载加上所有被拒绝有向超边的惩罚费用之和达到最小。(2)恢复鲁棒带惩罚费用呼叫控制问题可以简单描述如下:给定一个线路图和点对集合,线路图上任意一条边都含有一个权重,点对集合中任意一点对都含有一个需求和惩罚费用,但具体数值不确定,这里任意一点对可以选择接受或者拒绝,若点对被拒绝,则产生惩罚费用,否则,点对所经过的线路图中每一条边上都产生需求,线路图中任意一条边的负载是指在该边上产生的所有需求之和与该边权重的乘积。该问题的目标是寻找一个点对子集合,使得线路图上最大负载加上所有被拒绝点对的惩罚费用之和达到最小。针对有向超图嵌入路问题,本文首先证明了该问题是一个NP-困难问题,并设计了一个1.58-近似算法解决该问题。对于恢复鲁棒带惩罚费用呼叫控制问题,本文设计了一个1.58-近似的随机舍入算法解决该问题。特别地,当线路边数为2,情景数为2时,设计了一个精确的动态规划算法,同时基于该算法思想,我们又设计了一个全多项式时间近似方案解决此特殊情形下的恢复鲁棒带惩罚费用的呼叫控制问题。