不确定环境下鲁棒网络设计优化模型的研究及应用

不确定环境下的优化问题一直是一个研究热点和难题，而网络设计问题作为与实际生活的各个方面息息相关的一个经典数学问题，一直受到研究者的关注。但是网络设计的优劣受到多种不确定因素的影响，例如不确定的流量需求或者突发事件造成的网络局部中断等，这些不利影响会对网络的使用者造成一定的困扰，因此不确定环境下的网络设计问题成为了新的研究热点。而近十年来兴起的鲁棒优化技术为解决不确定数据下的优化问题提供了一个崭新的思路和方法。本项目就将利用鲁棒优化技术对不确定环境下的网络设计问题进行研究。 本项目将利用理论分析和实例分析相结合的方法，提取不确定环境中的关键参数和数据，定义输入数据的不确定集合，提出并依据相应的鲁棒优化准则，建立网络设计问题的鲁棒优化模型，设计快速有效的算法，并利用轨道交通网络为背景的实例对模型与算法进行测试。本项目将为网络设计者提供应对不确定环境的优化决策，具有重要的理论价值和实际意义。

在项目支持的这三年，一共完成论文3篇，其中发表两篇，投稿后修改一篇。第一篇是研究的wireless mesh network的优化问题，具体通过改变网关的数目或者位置来优化网络的结构，使得网络的数据传输效率得到提高。我们建立了数学规划模型，并且设计了基于k-median的算法来求解问题，最后通过数值模拟展示了算法的有效性。第二篇是研究的环状网路中的不对称原子的自私路由问题，即在有线性延迟的情况下，链接上的收发点之间的最小化最大延迟。通过分析我们发现，存在一个9-近似的纳什均衡的最优解，而且通过设计的算法，我们把稳定代价的上下界的差距缩小至0.7436。第三篇研究的是网络突发障碍情形下的轨道交通网络的鲁棒设计问题。我们使用区间集合来刻画不确定的输入数据，然后用两种鲁棒准则——最小化和最小最大，建立了相应的数学规划模型，然后设计了求解模型的启发式算法。最后我们以京广线中部主要城市的铁路交通网络为例对算法进行了数值模拟。我们给出了网络中某段铁路断线情形下的模拟方案，实验结果标明，如果网络中运行列车的数目在10^2量级上，网络中支线中断时间在4、8、12、24小时时，算法都能在10分钟内给出列车调整方案。