-
摘要: 设施服务分区问题(facility service districting problem，FSDP)是指在一个地理区域内，根据服务设施位置和服务能力为其划分服务区，满足供需平衡、形状紧凑和空间连续等要求。空间连续约束使FSDP能更好地满足学区划分、医疗区划分等问题的政策需求，但同时增加了它的求解难度。构造了一个FSDP混合整型线性规划模型，并设计了一个算法框架。框架包括问题定义、初始解、搜索算子和策略等基本模块，支持精确算法、元启发算法和混合算法设计。基于算法框架，实现了数学模型、模拟退火算法、迭代局部搜索算法和数学启发混合算法，并使用4个中大规模案例进行算法测试。实验结果表明，算法框架能够很好地处理空间连续约束的FSDP，支持多种算法快速实现，且求解质量接近案例目标值下界。Abstract:Objectives Facility service districting problem(FSDP) refers to the design of facility service areas according to the facility locations and service capacities in a geographical region. The design criteria for service areas include the balance of service demand and supply, the highest service accessibility, and the spatial contiguity. The spatial contiguity is a necessity for satisfying some policies on public services, such as school districting and medical districting. However, solving the FSDP with contiguity constraints is challenging. We present a hybrid algorithm framework for solving the FSDP.Methods The algorithm is proposed based on the general local search algorithm and furtherly enhanced by multi-start, ruin-recreate, set-partitioning and other optimization strategies. The basic modules such as initial solution generation method, local search operators, solution perturbation, model building and solving, and search strategies, are provided in the framework. Using these building blocks, some exact, metaheuristic and hybrid algorithms could be implemented effectively. Five algorithms are implemented for the FSDP: Exact method by solving a mixed integer linear programming model, simulated annealing (SA) algorithm, iterative local search (ILS) algorithm, SA with set-partitioning, and ILS with set-partitioning. In addition, four instances are designed to test the algorithms. The instance size, supply-demand ratio, and geographic environment are considered in the instance design.Results There are several findings from computing experimentation: Optimal or near-optimal solutions of the instances could be obtained by CPLEX optimizer; high-quality solutions could be found by SA and ILS algorithms much more efficiently; the set-partitioning procedure is capable of improving the solution quality.Conclusions Based on the proposed algorithm framework, it is easy and flexible to design local-search based matheuristics and hybrid algorithms for the FSDP. High quality solutions could be obtained by coupling the local search with ruin-recreate perturbation and set-partitioning.
-
随着全球导航卫星系统(Global Navigation Satellite System，GNSS)的飞速发展，已形成全球定位系统(Global Positioning System，GPS)、GLONASS、Galileo、BDS(BeiDou Navigation Satellite System)四系统并存的局面，预计到2020年将有超过120颗卫星在轨运行。采用多模GNSS数据可望显著改善观测几何结构，有利于改善导航定位精度[1-6]。由于不同星座的坐标和时间基准存在差异，相应的接收机硬件延迟也存在差异，在组合精密定位中必须考虑系统间偏差影响。
针对多模GNSS融合定位中的系统间偏差(inter-system bias, ISB)问题，许多研究者都做了比较深入的研究；EI-Mowafy[7]详细论述了系统间偏差的来源，但没有对ISB特性规律做进一步的研究。徐龙威等[8]、Torre等[9]利用伪距单点定位算法解算了GPS与GLONASS、Galileo、BDS之间的系统间偏差，并分析了ISB对单点定位的影响，但仅分析了一天内的ISB结果且解算精度较低。Gioia等[10]利用伪距解算了GPS与GLONASS、Galileo之间的ISB值，比较了不同接收机之间的ISB的差异性，但缺少对BDS的研究且解算精度较低；张清华等[11]和李敏[12]利用精密单点定位(precise point positioning, PPP)算法分析了GLONASS与GPS的ISB变化，验证了ISB的变化与接收机类型具有直接关系，且单天内ISB变化稳定，但没有对BDS与Galileo系统做进一步的研究；Liu等[13]利用PPP算法进一步分析了GPS与GLONASS、BDS之间的ISB变化，ISB单天内标准差(standard deviation, STD)分别为0.36 ns和0.38 ns，但缺少对Galileo系统的分析。
本文利用四系统观测数据进行多模GNSS融合PPP定位处理，同时得到同一测站中Galileo、GLONASS、BDS与GPS的ISB变化序列，并根据ISB单天内的短期变化、多天的长期变化及与接收机相关联的偏差序列分析其影响规律。
1 GNSS系统间偏差定义
GNSS系统间的坐标基准和时间基准存在定义差和实现误差[14], 但当采用多星座实验(the multi-GNSS experiment, MGEX)的四系统精密星历钟差产品时，可以不必考虑坐标和时间基准差异。虽然精密钟差产品的时间基准一般统一到GPS时间，但是不同系统在解算过程中选取的基准钟卫星不同，仍然会导致各个系统的卫星钟差基准存在差异。对于多模接收机来说，由于各个卫星导航信号的主要特征差异较大，特别是载波频率、信号带宽、调制方式、多址方式等与信号频谱特征相关的主要特征存在差异，而且不同的信号需要经过不同的通道，由不同的数字/模拟滤波器处理，造成不同系统在接收机内部的硬件延迟时间不同[14]。由此可知，ISB主要包含系统间接收机硬件延迟误差和不同系统的基准钟误差的差。根据定义可知，ISB对观测值的影响主要体现在时间误差上，因此其影响形式等同于不同系统包含无电离层组合硬件延迟的接收机钟差之差。
为研究ISB的变化特性，在多模融合PPP中，将ISB参数作为待定参数进行单历元解算，即在形式上独立解算各个系统的单历元接收机钟差。由于ISB即为各个系统接收机钟差相对于参考基准的差值，假设以GPS系统的接收机钟差为基准，则Galileo、GLONASS和BDS三系统相对GPS的ISB可表示成如下形式：
$$ \left\{ {\begin{array}{*{20}{c}} {{\rm{IS}}{{\rm{B}}_{E - G}} = {\rm{d}}{T_E} - {\rm{d}}{T_G}}\\ {{\rm{IS}}{{\rm{B}}_{R - G}} = {\rm{d}}{T_R} - {\rm{d}}{T_G}}\\ {{\rm{IS}}{{\rm{B}}_{C - G}} = {\rm{d}}{T_C} - {\rm{d}}{T_G}} \end{array}} \right. $$ (1) 式中，ISBE-G、ISBR-G、ISBC-G分别表示Galileo、GLONASS、BDS与GPS系统之间的系统间偏差；dTE、dTG、dTR、dTC分别表示对应Galileo、GPS、GLONASS、BDS的接收机钟差[7]。
2 多系统融合PPP定位算法
PPP以载波相位和伪距作为观测值，采用双频无电离层组合观测值消除电离层误差，而对流层延迟误差和接收机钟差则一般通过引入未知参数进行估计，观测方程为：
$$ \left\{ \begin{array}{l} P = \rho + c\left( {{\rm{d}}{T_j} - {\rm{d}}{T^i}} \right) + m \cdot {\rm{ZPD}} + {\varepsilon _P}\\ \varphi = \rho + c\left( {{\rm{d}}{T_j} - {\rm{d}}{T^i}} \right) + m \cdot {\rm{ZPD}} + {N^i} + {\varepsilon _\varphi } \end{array} \right. $$ (2) 式中，i为卫星；j为测站；P为消电离层伪距组合观测量；φ为消电离层载波相位组合观测量；ρ为测站(Xj, Yj, Zj)至卫星(Xi, Yi, Zi)的几何距离；c为光速；dTj为测站j的接收机钟差；dTi为卫星i的钟差；m是对流层映射函数；ZPD为接收机天顶对流层延迟；Ni为消电离层载波相位组合观测的整周模糊度参数；εP和εφ分别为消电离层伪距和载波相位组合观测的观测噪声与多路径误差，采用序贯最小二乘算法进行数据解算[15]。
将单模PPP定位模型扩展到多模融合PPP，考虑到系统间偏差，每个系统设置独立的接收机钟差参数进行解算，观测方程如下：
$$ \left\{ \begin{array}{l} {P_G} = {\rho _G} + c\left( {{\rm{d}}{T_{j, G}} - {\rm{d}}T_G^i} \right) + m \cdot {\rm{ZPD}} + {\varepsilon _{P, G}}\\ {\varphi _G} = {\rho _G} + c\left( {{\rm{d}}{T_{j, G}} - {\rm{d}}T_G^i} \right) + \\ \;\;\;m \cdot {\rm{ZPD}} + N_G^i + {\varepsilon _{\varphi , G}}\\ {P_R} = {\rho _R} + c\left( {{\rm{d}}{T_{j, R}} - {\rm{d}}T_R^i} \right) + m \cdot {\rm{ZPD}} + {\varepsilon _{P, R}}\\ {\varphi _R} = {\rho _R} + c\left( {{\rm{d}}{T_{j, R}} - {\rm{d}}T_R^i} \right) + \\ \;\;\;m \cdot {\rm{ZPD}} + N_R^i + {\varepsilon _{\varphi , R}}\\ {P_C} = {\rho _C} + c\left( {{\rm{d}}{T_{j, C}} - {\rm{d}}T_C^i} \right) + m \cdot {\rm{ZPD}} + {\varepsilon _{P, C}}\\ {\varphi _C} = {\rho _C} + c\left( {{\rm{d}}{T_{j, C}} - {\rm{d}}T_C^i} \right) + \\ \;\;\;m \cdot {\rm{ZPD}} + N_C^i + {\varepsilon _{\varphi , C}}\\ {P_E} = {\rho _E} + c\left( {{\rm{d}}{T_{j, E}} - {\rm{d}}T_E^i} \right) + m \cdot {\rm{ZPD}} + {\varepsilon _{P, E}}\\ {\varphi _E} = {\rho _E} + c\left( {{\rm{d}}{T_{j, E}} - {\rm{d}}T_E^i} \right) + \\ \;\;\;m \cdot {\rm{ZPD}} + N_E^i + {\varepsilon _{\varphi , E}} \end{array} \right. $$ (3) 式中，下标$G、R、C、E$分别代表GPS、GLONASS、BDS、Galileo系统。则对应矩阵形式的观测方程为：
$$ \mathit{\boldsymbol{V}} = \mathit{\boldsymbol{AX}} - \mathit{\boldsymbol{L}} $$ (4) 其中残差矩阵V为：
$$ \begin{array}{l} \mathit{\boldsymbol{V = }}\left[ {\mathit{v}_1^\mathit{G}\;\; \cdots \;\;\mathit{v}_k^\mathit{G}\;\;\mathit{v}_1^\mathit{R}\;\; \cdots \;\;\mathit{v}_l^\mathit{R}} \right.\\ \;\;\;\left. {\mathit{v}_1^\mathit{C}\;\; \cdots \;\;\mathit{v}_p^\mathit{G}\;\;\mathit{v}_1^\mathit{E}\;\; \cdots \;\;\mathit{v}_q^\mathit{E}} \right] \end{array} $$ (5) 式中，k、l、p、q分别表示GPS、GLONASS、BDS、Galileo系统对应的当前历元卫星数；未知参数向量X为：
$$ \begin{array}{l} \mathit{\boldsymbol{X = }}\left[ {{\rm{d}}x\;\;{\rm{d}}y\;\;{\rm{d}}z\;\;{\rm{ZPD}}\;\;{\rm{d}}{T_G}\;\;} \right.{\rm{d}}{T_R}\\ \;\;\;\left. {{\rm{d}}{T_C}\;\;{\rm{d}}{T_E}\;\;{\mathit{\boldsymbol{N}}_G}\;\;{\mathit{\boldsymbol{N}}_R}\;\;{\mathit{\boldsymbol{N}}_C}\;\;{\mathit{\boldsymbol{N}}_E}} \right] \end{array} $$ (6) 式中，${{\mathit{\boldsymbol{N}}_G}、{\mathit{\boldsymbol{N}}_R}、{\mathit{\boldsymbol{N}}_C}、{\mathit{\boldsymbol{N}}_E}}$分别代表四系统对应的模糊度参数向量；系数矩阵A可以表示为：
$$ \mathit{\boldsymbol{A}} = \left[ {{\mathit{\boldsymbol{A}}_1}\;\;{\mathit{\boldsymbol{A}}_2}\;\;{\mathit{\boldsymbol{A}}_3}} \right] $$ (7) 式中，A1表示位置参数和对流层参数系数矩阵；A2为接收机钟差系数矩阵；A3为模糊度系数矩阵，表示如下：
$$ \mathit{\boldsymbol{A}}_1^n = \left[ {\begin{array}{*{20}{c}} {a_{P, 1}^n}&{b_{P, 1}^n}&{c_{P, 1}^n}&{{m_1}}\\ {a_{\varphi , 1}^n}&{b_{\varphi , 1}^n}&{c_{\varphi , 1}^n}&{{m_1}}\\ \vdots&\vdots&\vdots&\vdots \\ {a_{P, i}^n}&{b_{P, i}^n}&{c_{P, i}^n}&{{m_i}}\\ {a_{\varphi , i}^n}&{b_{\varphi , i}^n}&{c_{\varphi , i}^n}&{{m_i}} \end{array}} \right];\mathit{\boldsymbol{A}}_2^n = \left[ \begin{array}{l} 1\\ 1\\ \vdots \\ 1\\ 1 \end{array} \right] $$ (8) $$ {\bf{A}}_3^n = {\left[ {\begin{array}{*{20}{c}} 0&{ - 1}&{}&{}&{}&{}&{}\\ {}&{}&0&{ - 1}&{}&{}&{}\\ {}&{}&{}&{}& \ddots &{}&{}\\ {}&{}&{}&{}&{}&0&{ - 1} \end{array}} \right]^{\rm{T}}} $$ (9) 式中, $n = G, R, C, E;i$表示对应卫星系统的卫星个数。则多模融合PPP观测方程的系数矩阵表示为：
$$ \mathit{\boldsymbol{A}} = \left[ {\begin{array}{*{20}{c}} {\mathit{\boldsymbol{A}}_1^G}&{\mathit{\boldsymbol{A}}_2^G}&0&0&0&{\mathit{\boldsymbol{A}}_3^G}&0&0&0\\ {\mathit{\boldsymbol{A}}_1^R}&0&{\mathit{\boldsymbol{A}}_2^R}&0&0&0&{\mathit{\boldsymbol{A}}_3^R}&0&0\\ {\mathit{\boldsymbol{A}}_1^C}&0&0&{\mathit{\boldsymbol{A}}_2^C}&0&0&0&{\mathit{\boldsymbol{A}}_3^C}&0\\ {\mathit{\boldsymbol{A}}_1^E}&0&0&0&{\mathit{\boldsymbol{A}}_2^E}&0&0&0&{\mathit{\boldsymbol{A}}_3^E} \end{array}} \right] $$ (10) 对应的L矩阵表示为：
$$ \begin{array}{l} \mathit{\boldsymbol{L}} = {\left[ {{\mathit{\boldsymbol{L}}^G}\;\;{\mathit{\boldsymbol{L}}^R}\;\;{\mathit{\boldsymbol{L}}^C}\;\;{\mathit{\boldsymbol{L}}^E}} \right]^{\rm{T}}}\\ {\mathit{\boldsymbol{L}}^n} = \left[ {\begin{array}{*{20}{c}} {P_1^n - \rho _1^n + C_{P, 1}^n}\\ {\varphi _1^n - \rho _1^n + C_{\varphi , 1}^n}\\ \vdots \\ {P_i^n - \rho _i^n + C_{P, i}^n}\\ {\varphi _i^n - \rho _i^n + C_{\varphi , i}^n} \end{array}} \right], n = G, R, C, E \end{array} $$ (11) 式中，i表示卫星数；${C_{P, i}^n} $、${C_{\varphi , i}^n}$分别表示伪距和载波相位观测量的误差改正值。
多模GNSS融合PPP中，按照单系统模式对各项误差进行改正，采用静态模式解算并固定测站坐标进行精度统计，其数据处理流程如图 1所示，所采用的数据处理策略见表 1。
表 1 多模融合PPP数据处理策略Table 1. Adopted Models and Strategies of Multi-GNSS PPP步骤 项目 数据处理策略 误差
处理轨道和卫星钟误差 德国地学中心事后精密星历、钟差产品(sp3、clk) 对流层 干延迟部分SAAS模型消除，湿延迟部分采用参数估计 电离层 采用无电离层组合观测值消除低阶误差 天线相位中心误差 采用IGS08.atx模型 其他误差 固体潮、海潮、极潮改正，相位解缠改正，相对论效应改正 解算
选项
设置频率 G/R: L1+L2；C: B1+B2；E: E1+E5a 导航系统 GPS+GLONASS+Galileo+BDS 采样率 30 s 截止高度角 7° 接收机钟差 作为白噪声，对每个系统进行参数估计 模糊度 浮点解估计，不固定 测站坐标 利用SNX文件坐标约束，采用静态模式解算 解算方式 采用最小二乘解算，正反滤波 3 系统间偏差特性规律分析
本文从MGEX观测网中选择7个能够同时接收到GPS、GLONASS、Galileo、BDS四系统信号的测站，对3周(2016年年积日200至220天)的数据进行多模融合PPP解算，得到ISBE-G、ISBR-G、ISBC-G的变化序列。在所选择的测站中包含了TRIMBLE NETR9、LEICA GR10、SEPT POLARX4这3种类型接收机，具体各测站接收机类型见表 2。
表 2 各测站接收机类型Table 2. Receiver Types of Stations测站名 接收机类型 CUT0 TRIMBLE NETR9 GMSD TRIMBLE NETR9 JFNG TRIMBLE NETR9 KRGG LEICA GR10 NNOR SEPT POLARX4 ONS1 TRIMBLE NETR9 TONG TRIMBLE NETR9 为了探究ISB的特性规律，本文首先验证分析了所有测站的多模融合PPP定位精度，然后分析单天内各个测站的ISB解算结果变化和多天连续的平均结果序列变化规律，最后对不同接收机类型、不同ISB之间的差异进行对比分析。
3.1 四系统组合PPP定位精度分析
为了保障ISB结果的高精度和高可靠性，首先利用本文算法自编软件对3周数据的多模融合PPP定位结果进行精度分析，GPS、GLONASS、BDS、Galileo四系统融合PPP定位结果平均精度如图 2所示。从图 2可以看出，融合PPP定位偏差结果在东西分量精度为8.9 mm，南北分量为5.3 mm，高程分量为10.9 mm。值得注意的是，对于CUT0测站，由于IGS未提供同时期的测站坐标，故采用较早时期的结果，但精度较低，与本文多模融合PPP结果存在一定系统性偏差，导致其水平分量低于高程分量精度。相对于单系统定位，多模融合PPP定位的显著优势是卫星数量增加和卫星观测星座几何结构的改善，图 3和图 4选择GMSD测站数据进行对比分析，比较了单系统和多系统卫星数和几何精度因子(dilution of precision, DOP)值的差异。图 3中Galileo、GPS、GLONASS、BDS四系统平均全天可用卫星数分别为3、9、6、9颗，总卫星数达到27颗，同时卫星星座几何精度因子PDOP (position dilution of precision)、VDOP (vertical dilution of precision)、HDOP (horizontal dilution of precision)值也从单GPS系统的2.75、1.45、2.06减小到四系统组合的0.27、0.15、0.22。卫星数目的增加有效增强了PPP定位的稳定性和可靠性。通过上述分析，本文实验定位结果的水平精度为mm级，高程精度约为1 cm，能够保证四系统接收机钟差求解精度，进而保证ISB结果具有可靠的精度。
3.2 单天内系统间偏差变化规律
通过对接收机钟差进行单历元求解，得到不同系统间的ISB结果，并对单天内的ISB变化进行分析，得到ISB在单天内的短期变化规律。图 5分别展示了Galileo、GLONASS、BDS三系统与GPS之间的系统间偏差(ISBE-G、ISBR-G、ISBC-G分别减去各自的平均值)在2016年年积日220天的变化序列，其STD分别为0.086 ns、0.115 ns、0.118 ns。三系统间偏差单天标准差均小于0.12 ns，具有较高的稳定性，且各ISB的变化波动均在[-0.5，0.5]ns内。值得注意的是，虽然Galileo系统目前卫星数较少，但是其卫星信号质量较好，ISBE-G最为稳定。
![]()
图 5 Galileo、GLONASS、BDS与GPS的ISB单天内变化序列图(减去平均值)Figure 5. The ISB Results of Galileo, GLONASS, BDS(Mean Removed) in One Day3.3 长时间序列的ISB变化
通过上述分析可知，单天内ISB具有较高的稳定性，但是不同测站ISB的平均值可能略有不同，图 6展示了2016年年积日200至220天3周的ISBE-G、ISBR-G、ISBC-G天平均值变化序列图。实验结果显示，ISB值在长时间序列中不具有规律性，对于不同类型接收机不同测站在相同天之间的ISB结果均存在跳动。通过对不同测站相邻天ISB的平均值作差，可分析ISB在长时间序列中的变化趋势，如图 7所示。尽管对于不同的卫星系统，ISB的变化趋势不相同，但是对于所有测站的同一种ISB，在同一天都具有相同变化趋势和相近的变化值。这表明，这种ISB的跳动与接收机类型无关，其影响因素可能来自于不同系统的卫星钟基准误差之差[13]。对于Galileo、GLONASS、BDS与GPS的ISB跳动最大值分别可达8.5 ns、18.2 ns、14.2 ns。
![]()
图 6 Galileo、GLONASS、BDS与GPS的每天ISB平均值变化序列Figure 6. The Daily Average ISB of Galileo, GLONASS, BDS![]()
图 7 Galileo、GLONASS、BDS与GPS在相邻天的ISB差异序列Figure 7. The Differences of ISB Between Adjacent Days for Galileo, GLONASS, BDS在同一天内，具有相同接收机类型测站的ISB值明显区别于其他类型的接收机，同类型内的接收机具有近似的系统间偏差。不同系统之间的系统间偏差具有明显的差异性，说明在融合定位中，系统间偏差是不可忽视的误差项，为了削弱ISB偏差的系统性影响，在融合定位中应采用模型参数法进行估计。
3.4 ISB与接收机类型的关系
由§3.3可知，即使是同一类型接收机，各个卫星系统之间的ISB仍具有不同的稳定性。为了进一步分析同一种接收机的ISB差异规律，本文选择具有相同接收机类型的5个测站(CUT0、GMSD、JFNG、ONS1、TONG)，比较7天的解算结果，并统计同一天内系统间偏差的最大值与最小值之差，如图 8所示。由图 8可知，对于Galileo系统，同类型接收机的ISB差异值最小，平均为4.27 ns，GLONASS和BDS系统具有较大的差异值，平均为7.17 ns和7.74 ns。分析认为，Galileo卫星具有高质量的信号特征，受频间偏差影响较小；由于GLONASS频分多址的特征，ISB值受到频间偏差影响而波动较大；对于北斗系统，由于地球同步卫星的存在，相应轨道精度较低，影响了ISB的精确求解，导致相同接收机类型不同测站之间ISB波动较大。另外，为了比较不同类型接收机之间的ISB量级差异，图 9展示了不同类型接收机(T-L为TRIMBLE NETR9-LEICA GR10，T-S为TRIMBLE NETR9-SEPT POLARX4，L-S为LEICA GR10-SEPT POLARX4)之间的ISB最小差值，除了T-L的GLONASS与GPS的ISB值小于10 ns之外，其他不同类型接收机之间的ISB最小差异值都远远大于同类型接收机之间的ISB最大差异值，结果表明ISB值大小与接收机类型有强相关性。
![]()
图 9 各类型接收机ISB之间最小差Figure 9. The ISB Minimum-Differences of the Different Types of Receivers4 结语
本文针对多模融合定位中存在的系统间偏差问题，利用高精度多模GNSS融合PPP算法求解了Galileo、GLONASS、BDS与GPS的ISB结果，综合分析了Galileo、GLONASS、BDS与GPS的ISB特性规律。对于多模GNSS融合PPP，其水平精度优于10.3 mm，高程分量精度优于10.9 mm。从单天内的短期变化来看，不同系统ISB在一天内具有较高的稳定性，可在多模融合PPP定位中将ISB当作一个稳定参数进行求解。对于多天连续的ISB变化，由于存在ISB不规律的跳变，因此不建议进行连续跨天多模融合PPP解算。不同类型接收机的ISB表现出较大的差异，这表明ISB与接收机类型具有较强的相关性。通过对ISBE-G、ISBR-G、ISBC-G的分析可知，相比于GLONASS和BDS，Galileo与GPS之间的ISB具有较高的稳定性。
-
表 1 4个测试案例的主要属性
Table 1 Attributes of Four Cases
案例 区域特征 地理单元数 邻接关系 设施数 设施容量 服务需求量 供需比 ZYA 城区 324 1 618 15 4 470 3 873 1.154 ZYB 城区 324 1 618 15 3 979 3 873 1.027 GY2A 县域 1 276 7 820 22 975 947 819 812 1.190 GY2B 县域 1 276 7 820 22 843 424 819 812 1.029 
下载: 导出CSV
表 2 5种算法求解服务分区结果统计
Table 2 Solution Results of Five Algorithms
算法 统计指标 ZYA ZYB GY2A GY2B CPLEX 总距离/km 1 656.53* 1 874.58* 1 875 355.92* 2 003 951.77 GAP/% 0 0 0 0.01 运行时间/s 83.00 112.70 401.82 7 204.54 SA 平均总距离/km 1 668.27 1 900.16 1 875 788.04 2 007 153.45 最好总距离/km 1 661.37 1 892.22 1 875 563.99 2 006 397.20 平均GAP/% 0.71 1.36 0.02 0.17 平均运行时间/s 53.81 54.03 252.06 224.45 SA-SPP 平均总距离/km 1 662.98 1 898.53 1 875 396.63 2 005 921.36 最好总距离/km 1 661.37 1 891.16 1 875 355.92* 2 004 889.09 平均GAP/% 0.39 1.28 0.00 0.11 平均运行时间/s 57.58 59.32 259.65 258.65 SPP改进/% 0.32 0.09 0.02 0.00 SPP平均运行时间/s 3.77 5.29 7.60 34.20 ILS 平均总距离/km 1 663.92 1 910.10 1 876 169.80 2 009 310.83 最好总距离/km 1 660.19 1 904.51 1 875 633.19 2 007 623.64 平均GAP/% 0.45 1.90 0.04 0.28 平均运行时间/s 53.13 60.62 140.63 224.80 ILS-SPP 平均总距离/km 1 657.08 1 905.24 1 875 476.09 2 006 901.47 最好总距离/km 1 656.53* 1 895.06 1 875 367.74 2 005 088.75 平均GAP/% 0.03 1.64 0.01 0.16 平均运行时间/s 58.56 153.64 145.04 267.03 SPP改进/% 0.41 0.23 0.04 0.12 SPP平均运行时间/s 5.43 93.02 4.41 42.23 注：*表示算法获得的最优解
下载: 导出CSV
-
[1] Gilbert L, Stefan N, Francisco S. Location Science[M]. Cham: Springer, 2015
[2] Tong D, Murray A T. Spatial Optimization in Geography[J]. Annals of the Association of American Geographers, 2012, 102(6): 1 290-1 309 doi: 10.1080/00045608.2012.685044
[3] 王铮, 吴静. 计算地理学[M]. 北京: 科学出版社, 2016 Wang Zheng, Wu Jing. Computation Geography[M]. Beijing: Science Press, 2016
[4] 黎夏, 刘小平, 李少英. 智能式GIS与空间优化[M]. 北京: 科学出版社, 2010 Li Xia, Liu Xiaoping, Li Shaoying. Intelligent GIS and Spatial Optimization[M]. Beijing: Science Press, 2010
[5] Hess S W, Weaver J B, Siegfeldt H J, et al. Nonpartisan Political Redistricting by Computer[J]. Operations Research, 1965, 13(6): 998-1 008 doi: 10.1287/opre.13.6.998
[6] Kalcsics J, Nickel S, Schröder M. Towards a Unified Territorial Design Approach: Applications, Algorithms and GIS Integration[J]. TOP, 2005, 13(1): 1-56 doi: 10.1007/BF02578982
[7] Xiao N. A Unified Conceptual Framework for Geographical Optimization Using Evolutionary Algorithms[J]. Annals of the Association of American Geographers, 2008, 98(4): 795-817 doi: 10.1080/00045600802232458
[8] Ricca F, Scozzari A, Simeone B. Political Districting: From Classical Models to Recent Approaches[J]. 4OR: A Quarterly Journal of Operations Research, 2011, 9(3): 223-254 doi: 10.1007/s10288-011-0177-5
[9] 孔云峰, 朱艳芳, 王玉璟. 学校分区问题混合元启发算法研究[J]. 地理学报, 2017(2): 256-268 https://www.cnki.com.cn/Article/CJFDTOTAL-DLXB201702007.htm Kong Yunfeng, Zhu Yanfang, Wang Yujing. A Hybrid Metaheuristic Algorithm for the School Districting Problem[J]. Acta Geographica Sinica, 2017(2): 256-268 https://www.cnki.com.cn/Article/CJFDTOTAL-DLXB201702007.htm
[10] Keane M. The Size of the Region-Building Problem[J]. Environment and Planning A, 1975, 7(5): 575-577 doi: 10.1068/a070575
[11] Bucarey V, Ordóñez F, Bassaletti E. Shape and Balance in Police Districting[M] // Eiselt H A, Marianov V. Applications of Location Analysis. Cham: Springer, 2015
[12] Duque J C, Ramos R. Design of Homogenous Territorial Units: A Methodological Proposal and Applications[J]. Working Papers in Economics, 2004, 70(3): 314-331 http://dialnet.unirioja.es/servlet/tesis?codigo=88133
[13] Ricca F, Simeone B. Local Search Algorithms for Political Districting[J]. European Journal of Operational Research, 2008, 189(3): 1 409-1 426 doi: 10.1016/j.ejor.2006.08.065
[14] Duque J C, Church R L, Middleton R S. The p-Regions Problem[J]. Geographical Analysis, 2011, 43(1): 104-126 doi: 10.1111/j.1538-4632.2010.00810.x
[15] Kong Y F, Zhu Y, Wang Y. A Center-Based Modeling Approach to Solve the Districting Problem[J]. International Journal of Geographical Information Science, 2018, 33(1/2): 368-384
[16] Minciardi R, Puliafito P P, Zoppoli R. A Districting Procedure for Social Organizations[J]. European Journal of Operational Research, 1981, 8(1): 47-57 doi: 10.1016/0377-2217(81)90028-X
[17] Ferland J A, Guénette G. Decision Support System for the School Districting Problem[J]. Operations Research, 1990, 38(1): 15-21 doi: 10.1287/opre.38.1.15
[18] Ko J, Nazarian E, Nam Y, et al. Integrated Redistricting, Location-allocation and Service Sharing with Intra-district Service Transfer to Reduce Demand Overload and Its Disparity[J]. Computers, Environment and Urban Systems, 2015, 54: 132-143 doi: 10.1016/j.compenvurbsys.2015.07.002
[19] 何雪, 韦波, 张晓宇, 等. 一种求解学区划分问题的混合启发式算法[J]. 测绘科学, 2020, 45(1): 163-170 https://www.cnki.com.cn/Article/CJFDTOTAL-CHKD202001023.htm He Xue, Wei Bo, Zhang Xiaoyu, et al. A Hybrid Heuristic Algorithm for Solving School District Division Problem[J]. Science of Surveying and Mapping, 2020, 45(1): 163-170 https://www.cnki.com.cn/Article/CJFDTOTAL-CHKD202001023.htm
[20] Kim K. A Spatial Optimization Approach for Simultaneously Districting Precincts and Locating Polling Places[J]. ISPRS International Journal of Geo-Information, 2020, 9(5): 301-317 doi: 10.3390/ijgi9050301
[21] 孔云峰. 利用GIS与线性规划学校最优学区划分[J]. 武汉大学学报∙信息科学版, 2012, 37(5): 513-515 https://www.cnki.com.cn/Article/CJFDTOTAL-WHCH201205003.htm Kong Yunfeng. Optimal School Allocation Using GIS and Linear Programming[J]. Geomatics and Information Science of Wuhan University, 2012, 37(5): 513-515 https://www.cnki.com.cn/Article/CJFDTOTAL-WHCH201205003.htm
[22] 孔云峰, 朱艳芳, 王玉璟. 整型规划求解空间连续约束学校分区问题[J]. 河南大学学报(自然版), 2017, 47(5): 13-20 https://www.cnki.com.cn/Article/CJFDTOTAL-HDZR201705002.htm Kong Yunfeng, Zhu Yanfang, Wang Yujing. Integer Programming for the Spatially-Contiguity Constrained School Districting Problem[J]. Journal of Henan University(Natural Science), 2017, 47(5): 13-20 https://www.cnki.com.cn/Article/CJFDTOTAL-HDZR201705002.htm
[23] Shirabe T. A Model of Contiguity for Spatial Unit Allocation[J]. Geographical Analysis, 2005, 37(1): 2-16 doi: 10.1111/j.1538-4632.2005.00605.x
[24] Maniezzo V, Stützle T, Voß S. Matheuristics: Hybridizing Metaheuristics and Mathematical Programming[M]. New York: Springer, 2010
[25] Lagos C, Guerrero G, Cabrera E, et al. A Matheuristic Approach Combining Local Search and Mathematical Programming[J]. Scientific Programming, 2016, 2016(Pt. 1): 1-7 doi: 10.1155/2016/1506084
-
期刊类型引用(17)
1. 冯晓亮，陈欢，李厚芝. 不同观测环境中的多模GNSS数据质量自动化检测方法. 测绘工程. 2024(06): 56-61 . 
百度学术
2. Jingxuan Guo，Weiping Jiang，Yan Chen，Xincheng Ma，Hua Chen. Long-term and short-term stability characteristics of receiver inter system bias for BDS3/BDS2. Geodesy and Geodynamics. 2023(02): 143-149 . 必应学术
3. 陈秀德，刘惠，惠沈盈，应俊俊，张京奎. GNSS兼容频点动态PPP性能分析. 无线电工程. 2023(05): 1078-1085 . 百度学术
4. 刘嘉伟，孙保琪，韩蕊，张喆，王侃，袁海波，杨旭海. GNSS多系统RTK授时性能分析. 导航定位与授时. 2023(03): 49-58 . 百度学术
5. 龙宸君，吴宗洲，申志恒. 基于原始观测值的UWB增强GNSS精密单点定位方法研究. 导航定位与授时. 2023(04): 123-131 . 百度学术
6. 朱亚兵，岳彩亚，施紫鹏，刘宗强，杨强. 三频非组合PPP模型系统间偏差特性分析. 导航定位学报. 2023(05): 92-100 . 百度学术
7. 叶少春，唐伟靖，徐文兵. 顾及DCB改正的伪距定位模型及动态性能评估. 全球定位系统. 2023(05): 64-70 . 百度学术
8. 许强，朱星，李为乐，董秀军，戴可人，蒋亚楠，陆会燕，郭晨. “天-空-地”协同滑坡监测技术进展. 测绘学报. 2022(07): 1416-1436 . 百度学术
9. 陈彦宇，周鸿喜，李皎，陈灿，田永和，任烨，王琦，李扬，唐佳，贾平. 电网卫星系统切换对授时性能的影响分析. 电力信息与通信技术. 2022(09): 93-99 . 百度学术
10. 田先才，张龙平，原亮，徐君毅，孙伟杰. 北斗三号系统PPP-B2b信号定位服务模型及性能分析. 导航定位与授时. 2022(05): 162-170 . 百度学术
11. 王含宇，宋淑丽，周伟莉，陈钦明. GNSS偏差及其研究进展. 天文学进展. 2021(01): 49-62 . 百度学术
12. 王思遥，涂锐，李琴，鲁洋为. GPS/Galileo组合区域增强PPP算法与评估. 东南大学学报(自然科学版). 2021(02): 357-364 . 百度学术
13. 杜祯强，柴洪洲，潘宗鹏，石明琛，齐文龙. 针对消电离层组合FCB的非组合PPP部分模糊度固定方法. 武汉大学学报(信息科学版). 2021(06): 913-919 . 百度学术
14. 郭磊，王甫红，桑吉章，张万威. 一种新的利用历元间位置变化量约束的GNSS导航算法. 武汉大学学报(信息科学版). 2020(01): 21-27 . 百度学术
15. 王勋，崔先强，高天杭. 城市环境下数据缺失定位算法比较. 导航定位学报. 2020(02): 43-48 . 百度学术
16. 王利华，周定杰，刘鸿飞，苏国田，宗云婷，陈世杰. GPS/GLONASS/BDS/Galileo动态精密单点定位精度及收敛时间分析. 测绘地理信息. 2020(04): 64-69 . 百度学术
17. 宋美慧，柴艳菊，张宝成. GPS/BDS系统间偏差特性及其对PPP影响分析. 导航定位学报. 2020(06): 46-52 . 百度学术
其他类型引用(19)
计量
- 文章访问数: 1135
- HTML全文浏览量: 403
- PDF下载量: 64
- 被引次数: 36
