[發明專利]一種用于解決供求關系平衡的區域劃分方法及系統

有效

• 申請號: 202010696450.4
• 申請日: 2020-07-20
• 公開（公告）號: CN111738624B
• 公開（公告）日: 2020-11-13
• 發明（設計）人: 陳西亮;劉鑫;李鵬程;陳奇;吳杰;賀楷鍇
• 申請（專利權）人: 武大吉奧信息技術有限公司
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06Q50/20;G06F16/9537
• 代理公司: 武漢知產時代知識產權代理有限公司 42238
• 代理人: 彭建怡

本發明公開了一種用于解決供求關系平衡的區域劃分方法及系統，該方法包括獲取區域內每個供給方的地理位置點數據，確定每個供給方的容量限度；對區域內的需求方進行匯總，確定每個需求方的地理位置坐標點和需求數量；針對每個供給方的地理位置點，生成相應的Voronoi圖，按照所選坐標點的經緯度、取值大小，對Voronoi圖進行排序；基于排好序的Voronoi圖確定起始邊界，通過疊加分析判斷：當需求方的需求總數量大于等于供給方容量限度時，進行需求方的分配；若無法分配，則重新劃分邊界范圍，繼續執行所選邊界范圍下供給方和需求方的疊加分析；移除已分配的供給方和需求方，重新生成Voronoi圖，進行需求方的分配；若供給方或需求方均分配完畢，輸出區域劃分結果。

技術領域

本發明涉及空間規劃運籌領域，更具體地說，涉及一種基于動態Voronoi圖解決供求關系平衡的區域劃分方法及系統。

背景技術

隨著我國城鎮化步伐加快，越來越多的人口流向城市，伴隨而來的教育資源分配不均衡的問題也越來越突出。為確保義務教育免試就近入學政策的全覆蓋，各地教育部門在遵循“學校劃片招生，生源就近入學”的總體目標的前提下進行學區劃分。目前中小學學區劃分的方式主要是單片劃分和多片劃分，然而學區劃分是一個很復雜的過程。在學區劃分前，教育部門要充分掌握好片區內的需求和供給，既要進行摸底掌握好片區內戶籍人數和學生數，也要掌握片區內各個學校的畢業班數、教室數，另外還要統籌考慮學校位置、交通因素等以便于確定合理的招生范圍和招生計劃。這個過程需要耗費大量的時間、人力和物力。

近年來，國內外學者也對學區劃分方法進行了大量的研究，以便于提高學區劃分的效率。這些方法主要集中在數學模型法、GIS劃分法和啟發式算法優化法，然而諸多方法只能起到一定的輔助作用，沒有一種方法能夠直接投入到實際應用當中。數學模型法要么是簡單的資料統計對比，無法考慮空間布局的問題，要么屬于NP-Hard問題，很難得到穩定的有效解。GIS劃分法主要包括緩沖區分析法、泰森多邊形劃分法、路網距離分析法等，主要聚焦在距離問題上。緩沖區分析能一定程度上考慮到距離覆蓋問題，然而難以構成連續的空間；泰森多邊形法雖然能覆蓋全部空間，但是無法解決供需平衡問題；路網距離法能考慮到實際交通狀況，最小化通行成本，但是也難以兼顧到供需矛盾問題。因此，學區劃分方法需要進一步優化，統籌考慮距離問題和供需平衡問題。

發明內容

本發明要解決的技術問題在于，針對現有技術無法解決供需平衡的缺陷，提供一種用于解決供求關系平衡的區域劃分方法及系統。

本發明解決其技術問題所采用的技術方案是：構造一種用于解決供求關系平衡的區域劃分方法，包括以下步驟：

S1、獲取區域內每個供給方的地理位置點數據，且，針對每個供給方，以其能夠容納的人數，確定每個供給方的容量限度；

S2、對區域內的需求方進行匯總，且，確定每個需求方的地理位置坐標點和需求數量；

S3、針對每個供給方的地理位置點，生成相應的Voronoi圖；其中，針對所得的每個Voronoi圖，計算Voronoi圖所有多邊形的外包矩形，取出外包矩形的對應點坐標，按照坐標的經緯度以及取值大小，對所述生成相應的Voronoi圖進行排序；

S4、基于排好序的Voronoi圖，將左下角的Voronoi圖作為起始邊界，在確定了圖中包括的供給方和多個需求方后，將當前的Voronoi圖分別與供給方、每個需求方做疊加分析，判斷需求方的需求總數量是否大于等于供給方的容量限度；若是，則在供給方的容量限度范圍內，完成需求方的分配；若否，則在現有的邊界上擴大搜索范圍直到找到滿足條件的邊界范圍后，繼續執行所選邊界范圍下Voronoi圖內供給方和需求方的疊加分析，直到完成需求方的分配；

S5、移除已經參與分配過的供給方和需求方，基于剩余供給方的地理位置點重新生成相應的Voronoi圖，重復步驟S4-S5；當供給方或需求方均分配完畢時，輸出區域劃分結果。