最小化最大距离位置的动态监控方法及系统

摘要

本发明提供了一种查询最小化最大距离位置的动态监控方法及系统，包括：给定一个客户点的集合C和一个设施点的集合F，以及一个候选位置集合P,最小化最大距离位置为$p={\arg \min }_{p\in P}\left({\max }_{c\in C}\right\{\hat{a}\left(c\right)|F=F\cup \{p\left\}\right\})$；通过向表示路网的无向连通图G^o=(V^o,E^o)插入所有的设施点f和客户点c来将E^o中的边划分成新的边，对于每一个点ρ∈C∪F，先考虑ρ所在的边e∈E^o，令e的两个端点为v_l和v_r，然后将e分为两部分即从v_l到ρ和从ρ到v_r，以使ρ成为无向连通图的一个新顶点，加入所有的新顶点以生成了一个新的无向连通图G=(V,E)；把G按照边划分为n个子图G₁…G_n，其中，n的值根据用户的需要设置；根据G中初始的设施点集合F和客户点集合C获取p;根据G中设施点集合F或客户点集合C发生的更新随时动态监控p。本发明能够快速和动态地查询最小化最大距离位置。

主权项

一种查询最小化最大距离位置的动态监控方法，其特征在于，包括：给定一个客户点的集合C和一个设施点的集合F，以及一个候选位置集合P,最小化最大距离位置为其中为客户点c的加权吸引距离，w(c)是客户点c的权重，如果客户点c和设施点f在道路网络中的距离d(c,f)是c和F中的点的极小值，则定义f是c的吸引者，c被f吸引，a(c)＝d(c,f)为c的吸引距离；通过向表示路网的无向连通图G^o＝(V^o,E^o)插入所有的设施点f和客户点c来将E^o中的边划分成新的边，对于每一个点ρ∈C∪F，先考虑ρ所在的边e∈E^o，令e的两个端点为v_l和v_r，然后将e分为两部分即从v_l到ρ和从ρ到v_r，以使ρ成为无向连通图的一个新顶点，加入所有的新顶点以生成了一个新的无向连通图G＝(V,E)，且V＝V^o∪C∪F；把G按照边划分为n个子图G₁...G_n，其中，n的值根据用户的需要设置，把G按照边划分为n个子图G₁...G_n的步骤包括：从V中随机选取n个顶点作为顶点集合V_△；建立n个空的子图G₁...G_n，将顶点集合V_Δ中的点分别设为每个子图的中心；把G和V_△作为Erwig和Hagen算法的输入，计算出对于G中每一个v，V_△中距离v最近的v′和两者的距离d(v,v′)；对于G中的每一条边e，如果e的两个端点到V_Δ中最近的点是同一个，则把e加入到对应的子图里，否则把e加入到其任意一个端点到V_Δ中最近的点对应的子图里；根据G中初始的设施点集合F和客户点集合C获取p；根据G中设施点集合F或客户点集合C发生的更新随时动态监控p，步骤包括：路网中设施点和客户点的更新可以归结为增加一个客户点AddC(c)，减少一个客户点DelC(c)，增加一个设施点AddF(f)，减少一个设施点DelF(f)共四种基本操作；当一个更新操作到来的时候，首先计算吸引距离会被更新所影响的客户点的集合V_c，如果操作是AddC(c)或DelC(c)，则V_c＝{c}；如果操作是AddF(f)或DelF(f)，则V_c＝{c|<c,d(c,v)>∈A(f)}；对于每一个客户点c∈V_c，找出该客户点之前的吸引距离a⁰(c)和新的吸引距离a'(c)，并建立两个集合和对于每一个客户点c∈V_c，根据a⁰(c)，a'(c)，来更新所有已经被计算的子图中的每一条边e的局部最佳位置I以及对应的收益值m，令更新前的局部最佳位置以及对应的收益值分别为I₀和m₀；更新所有子图的收益值上限；根据新的上限对所有子图进行从高到低排序，之后按这个顺序遍历所有子图：对于被访问的子图，如果该子图未被计算，则初始计算该子图的局部最佳位置并获取对应收益值，如果该子图已被计算，则直接读取该子图的局部最佳位置和对应收益值；如果在某一时刻当前获得的最大收益值已经大于下一个待访问子图的收益值上限，则停止遍历，将这个最大收益值对应的位置作为最小化最大距离位置p；对于未遍历到的子图，把其中已经计算的子图改为未计算，以为下一次更新做准备；其中，v为无向连通图G中的一个顶点，d(c,ν)是顶点v在道路网络中的距离，A(f)是设施点f的吸引集合。