面向位置服务的动态阻滞网络流模型及算法研究

The research on location services has attracted increasing interest, due to its great potential in many important real applications, such as mobile networks, intelligent transportation systems, digital city, emergency management and digital battlefield, etc.. As a theoretical tool for network analysis and modeling, the theory of network flow plays a fundamental role in the study on mobile object query, indexing and trend forecasting in the area of location services. In this project, based on the network flow theory, we will devote our research efforts in the problem of dynamic network flow with the characteristics of time-varying and congested to meet the requirements of the real applications of location service. Specifically, our research will focus on the following topics: the mathematical model and algorithm of dynamic block network flow for theoretical analysis and model construction; The "divided" dynamic block network flow model; Time-varying and congested dynamic network on the fast flow and the minimum cost flow problem of nonlinear optimization models. The algorithms based on local expansion, and local search for location service to congested flow allocation algorithm, as well as the position of the mobile object prediction technology will also be studied in this project. Based on the innovative theory and technology as well as the understanding of the essential problem of the location services, we expect to make some breakthroughs on the above research topics, and get a number of high quality research publications.

位置服务技术在移动网络、智能交通、数字城市、应急管理以及数字战场等领域具有广阔的应用前景。网络流理论作为网络分析与建模的理论工具在面向位置服务的移动对象的查询、索引及趋势预测等研究中发挥着重要的基础作用。本项目将在深入理解位置服务应用需求与特点的基础上，充分借鉴已有网络流研究的成熟理论与方法，从位置服务应用中动态网络流的时变性、阻滞性特点出发，着力解决动态阻滞网络流的数学模型及其优化算法的理论分析与构建问题。重点开展对"可划分"的动态阻滞网络流模型，时变性与阻滞性动态网络上的最速流、最小费用流等问题的非线性优化模型及算法，基于局部扩张与局部搜索的面向位置服务的阻滞流分配算法，以及移动对象的位置预测技术等的研究。课题组力争在上述研究中获得突破，取得一批创新性成果。

本项目结合位置服务应用的需求，对具有阻滞作用的网络流模型和相关算法，以及相关领域进行了系统研究。重点研究了阻滞网络流模型中的最小饱和流问题、最小覆盖流问题，网络规划中的最小控制树问题，网络布局中的带宽和割宽问题等。对于NP-困难的最小饱和流问题、最小控制树问题，针对某些特殊情形，我们建立了多项式时间算法；对于最小覆盖流问题，我们证明了一个对偶关系；对于NP-困难的边-带宽问题，我们给出了更加精确的估计。本项目同时还对图像分割与深度网络开展了研究，并取得了一批研究成果。课题组共发表SCI/EI/核心刊物及会议论文13篇，已培养3名硕士毕业生。