枢纽港选址及相关问题的算法设计

枢纽港选址问题(hub location problem) 是一个中心辐射型(hub-and-spoke)物流运输与网络管理的普适模型。作为运筹学的一个经典问题，对其及相关问题的研究有着重要的应用价值和理论意义。本项目计划对枢纽港选址与相关的理论模型进行以下几个方面的探讨：首次提出讨论发展其半正定规划松弛的紧致下界(Lower bounds based on Semidefinite Programming(SDP) relaxation)。对枢纽港选址及其相关的多个问题可能的近似算法进行讨论，首次理论上对某些问题提出可证明的近似界。结合中国目前航空业发展的实际情况，为我国的航路设计和机场建设，以及各种物流网络运行探求成本节约的方法。

背景：本项目以枢纽港选址与分流问题为基础，研究了与其相关的算法设计问题，特别是涉及到的整数规划问题，二次规划问题，以及稀疏优化问题。.枢纽港的选址与分流问题是在现实中非常重要的运筹学问题，问题的模型也具有广泛的普适性，存在于航空，物流，通信等多个领域。.Background: .方向：枢纽港选址与分流问题的模型本质上是一个线性约束的二次非凸整数规划问题，在难度上是一个NP-难问题。因此我们在项目开初，以及随着进行，提出了如下的研究方向：.1).对问题的难度分析。以及如何寻求比较好的可解的松弛下界。.2).结合实际数据的随机优化问题。.3).我们注意到问题的最优解具有稀疏化的特点，如何针对这一特点，开展相关的稀疏优化理论分析？.4).还有哪些相关问题值得研究？.主要内容与结果：针对以上的几个问题，进行了深入研究：.1).我们证明了对于此类问题常规的快速矩阵提升SDP和向量提升SDP发展出的下界一致(Mathematics of Operations research，2011)。.2).随机需求下的枢纽港选址问题。我们着重关注于鲁棒优化，将问题松弛为一个二次锥优化问题， 目前正在进行最后的数据测算。.3).稀疏优化。我们在2011年首次考虑引入稀疏解重建的方法，对问题的复杂度和算法的收敛性进行了深入理论分析(mathematical programming,2011)。在2012年里，对结合了p模与二次函数的模型进行了复杂度分析( Mathematical Programming,2012)。论文在谷歌学术上被引用67次。.4).我们也对在一个枢纽港上有飞机进出时的调度问题的随机优化做了研究，证明了在某些情况下，整数解存在，并且问题可以归结为一个存在多项式算法的确定性优化问题。已经被Mathematics of Operations Research接受。.科学意义：我们的研究已经产生的结果均发表在优化与运筹的旗舰期刊上。已经涉及到的问题，在理论意义上，对二次矩阵规划，整数规划，Co-positive规划，稀疏优化，都有着一流结果产生。在运筹学的实际模型上，对定港分流问题，调度问题，工程的信号处理问题，生产调度问题，都有指导意义。作为上海数策公司的运筹学顾问（义务咨询），根据稀疏优化方法，为上海通用设计的生产调度方案，较通用传统做法有了较大提高。