社会化多模式路径规划服务中的数据模型与算法研究

The idea of socially-enabled multimodal route planning is driven by the interdisciplinary combination of mobile computing, social network service and navigation. To accomplish a socially-enabled multimodal routing request, the underlying data model and path-finding algorithms need improvements to adapt to such newly emerged routing problem because traditional solutions cannot be directly applied. To cope with the problem, an appropriate data model and effective route-planning algorithms should be properly designed especially when taking the social network into account. The essential work of the project includes the formally description of a socially-enabled multimodal routing problem, as well as the design of a general-purpose route-planning method by taking advantage of both high-performance geo-computation and mobile computing technologies. The research work is supposed to provide supports to the next-generation intelligent navigation service in both theory and practice.

智能移动平台与社会化网络服务的快速发展推动了多模式导航路径规划与社会化应用的融合。具有社会化特点的多模式路径规划应用对基础网络模型与路径搜索算法提出了更高的要求。用于传统导航应用的网络数据模型与路径搜索算法难以直接用于解决这种新型路径规划问题。因此，就需要研究如何针对社会化条件下多模式路径规划的特点对问题进行建模，以及如何设计高效的路径规划算法。本项目重点研究对于社会化多模式路径规划问题的需求建模，以及针对一般性多模式路径规划问题基于高性能计算基础设施与智能移动终端平台的解决方法。本项目通过探索社会化多模式路径规划问题的高效解决方案，为下一代智能导航应用服务提供基础性的理论与技术支持。

路径规划问题是一个被研究了很多年的经典问题。它既简单又复杂，简单到可以用一张图加一个60年前就已经成熟的算法来解决，也复杂到即使今天最先进的手机导航应用也有时会无法给出一条令人满意的路径。正是由于具有这种神奇的特质，路径规划问题每年都吸引着无数研究者投身其中，为哪怕是一个数据结构的小改进，或是路径搜索算法的小优化而兴奋不已。在路径规划问题中，融合多种交通方式的多模式路径规划又让这个问题的复杂程度变得更高，而如果再把人类的社交团体因素考虑进去，那么它将难倒任何一个现存的机器路径规划引擎。即便是一个经验十足的当地居民，也很难立即对这种问题给出最佳答案。而本课题恰恰就是要去啃这块硬骨头。经过三年的理论研究与实践，我们厘清了问题，给出了形式化的描述，构建了基于切换点的数据模型，并设计了适用于多层次网络的最短路径算法；通过对内外存数据的再平衡与应用分层压缩，有效提高了多模式路径规划的执行效率；设计了一种基于规则的推理机，可根据用户的出行条件给出各种可能而合理的交通模式组合；探索了人机路径规划结果的差异性以及通过路径规划方法探查众包地理信息质量的可行性，为进一步立足于众包地理空间大数据分析的多模式路径规划研究工作奠定了基础。课题按照预订计划完成并达到预期目标，所取得的成果以及在线原型演示系统均可通过互联网访问。