选址问题作为空间决策领域的基石,在诸如城市规划、物流、商业、基于位置服务等应用场景中都发挥着不可替代的作用。选址技术旨在通过选择最优位置建立设施使得收益最大化:一方面降低对象获取服务的代价,另一方面使设施能够服务更多的对象。在高速发展的定位技术和硬件技术推动下,面向运动对象的应用在当今信息时代已随处可见。然而,由于传统选址问题仅针对静态对象,其单点模型无法描述对象的运动特性,导致现有选址技术难以适应日益普遍的运动场景。为弥补选址问题在应对运动对象时存在的缺陷,针对三类重要的选址问题,即最大化影响力选址、最小化距离选址和迁址问题,本文首次提出了面向对象运动性的选址解决方案。通过对运动数据的分析,利用不同概率模型从多个角度描绘运动对象的空间运动特征,重新刻画了设施位置和运动对象间的距离尺度和影响关系。在此基础上,本文设计了针对运动对象选址的完整解决方案,包括新的剪枝算法、空间索引结构、距离边界、优化策略等,以高效处理对象运动性带来的计算开销问题。所提出的模型和方法能够有效提高空间选址决策的合理性,搭建起解决面向运动对象选址问题的桥梁。本研究工作的主要贡献如下:本文首先关注于面向对象运动性的最大影响力选址问题PRIME-LS。区别于传统最大影响力选址,PRIME-LS将运动对象建模为多个点,其中每个运动点都将影响最终选址结果。为描述设施对运动对象的影响行为,提出基于距离的多概率累加影响模型。该影响模型同时还符合现实中对象能被多个设施影响的情况。为度量此概率影响关系,本文设计了一种新的距离尺度minMaxRadius,并基于该尺度创建新的剪枝方法Influence Arcs和Non-influence Boundary。为高效处理PRIME-LS问题,在剪枝技术的基础上结合两个优化策略设计了PINOCCHIO算法。仿真结果显示,相比于传统基于范围影响和基于最近邻影响两种模型,PRIME-LS模型在选址结果的有效性上显著提高了10%到35%。所设计剪枝方法可以有效的剔除超过67%的冗余计算。结合优化策略,PINOCCHIO算法的效率相比基准算法大幅提高了近两个数量级。此外,本文还就PRIME-LS问题给出两个深层的理解:一方面,对象包含运动点数量的区间建议选择24到48个点之间,这一选择在保证对象运动性精度的前提下,也能有效的降低计算开销;另一方面,当期望影响的对象数量给定时,无论怎样选择PRIME-LS问题的参数,最终选择的位置间距离相差很小。为解决面向对象运动性的最小距离选址问题,本文设计了一个完整的解决框架MILE-RUN。首先为筛除对选址决策没有意义的运动点,如GPS错误点、偶发性位置点等,在概率化参考位置(Reference Location)概念基础上采用Kernel方法建模用户的频繁活动区域。对运动不确定性的建模遵循可能世界(Possible World)范式,并用期望值作为度量依据。利用基于参考位置的变换策略,可以将期望值估计的计算复杂度从指数级降为线性。为克服路网的高昂计算,本文设计了两组方法。其中一组基于空间局部性原则,利用R-tree和巧妙设计的局部路网索引,结合一系列新证明的期望边界值,避免大量不必要的计算。另一组方法利用路网扩展机制无需任何索引。对于MILE-RUN的群组位置选择问题,基于贪心算法的扩展方案可以在多项式时间内解决该NP-hard问题并保证[(k-1)k]~k的近似边界。仿真实验表明所提出的框架适用于有向和无向路网,并且相比基准算法效率上显著提高几个数量级,其中在期望边界值的帮助下接近95%的候选能被成功剪枝。与现有基于路网的最佳算法相比,提出的解决方案在绝大多数情况下性能更优。本文最后关注面向对象运动性且基于最小距离的迁址问题,称为MOTION-FR。鉴于该问题仍针对运动对象和最小距离,采用与MILE-RUN类似的框架,包括参考位置和可能世界基础上的运动对象模型。相比选址问题,迁址问题需要考虑额外的废弃设施。为解决这一变化引起的挑战,本文深入研究了废弃设施、候选地址与参考位置间的关系,并以此构建基于索引和无索引的算法。前者用于具备设施和运动数据先验的情况,后者可以应对在线场景。迁址问题的通用化扩展k-MOTIONFR同样为NP-hard问题,利用基于次局部路网索引的贪心算法,可以在多项式时间内求解。本文还从理论和实验两方面证明贪心算法的每一步收益在绝大多数情况下呈单调递减性。仿真结果验证了框架的高效性,以及在运动场景中相比静态迁址模型的性能优势。值得一提的是,MOTION-FR和MILE-RUN的实验都表明,用户日常活动的参考位置确实与最优结果的选择息息相关。