[發(fā)明專利]一種用于解決供求關(guān)系平衡的區(qū)域劃分方法及系統(tǒng)

有效

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

1.一種用于解決供求關(guān)系平衡的區(qū)域劃分方法，其特征在于，包括以下步驟：

S1、獲取區(qū)域內(nèi)每個供給方的地理位置點(diǎn)數(shù)據(jù)，且，針對每個供給方，以其能夠容納的人數(shù)，確定每個供給方的容量限度；

S2、對區(qū)域內(nèi)的需求方進(jìn)行匯總，且，確定每個需求方的地理位置坐標(biāo)點(diǎn)和需求數(shù)量；

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

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

S5、移除已經(jīng)參與分配過的供給方和需求方，基于剩余供給方的地理位置點(diǎn)重新生成相應(yīng)的Voronoi圖，重復(fù)步驟S4-S5；當(dāng)供給方或需求方均分配完畢時，輸出區(qū)域劃分結(jié)果。

2.根據(jù)權(quán)利要求1所述的區(qū)域劃分方法，其特征在于，步驟S3中，所述取出外包矩形的對應(yīng)點(diǎn)坐標(biāo)，按照坐標(biāo)的經(jīng)緯度以及取值大小，對所述生成相應(yīng)的Voronoi圖進(jìn)行排序具體為：

計算Voronoi圖所有多邊形的外包矩形，取外包矩形的左下角坐標(biāo)點(diǎn)，按照先經(jīng)度后緯度的順序，由低值到高值將所述生成相應(yīng)的Voronoi圖按照由西到東由南到北的順序排序。

3.根據(jù)權(quán)利要求1所述的區(qū)域劃分方法，其特征在于，步驟S4中，所述在供給方的容量限度范圍內(nèi)，完成需求方的分配具體為：

計算Voronoi圖內(nèi)每個需求方的重心坐標(biāo)，按步驟S3中對所述生成相應(yīng)的Voronoi圖進(jìn)行排序的方式，完成圖中多個需求方的排序；

基于需求方的排序結(jié)果，按順序進(jìn)行需求方的選擇，并對所選需求方的需求數(shù)量進(jìn)行累加，直到累加所得的需求總數(shù)量達(dá)到供給方的容量限度為止；

將參與累加的需求方分配到該多邊形內(nèi)的供給方。

4.根據(jù)權(quán)利要求1所述的區(qū)域劃分方法，其特征在于，步驟S4中，所述在現(xiàn)有的邊界上擴(kuò)大搜索范圍直到找到滿足條件的邊界范圍具體為：

采取逐步擴(kuò)大搜索范圍的方式搜索最優(yōu)區(qū)域，包括：

在現(xiàn)有邊界的基礎(chǔ)上分別設(shè)定第一擴(kuò)大范圍和第一搜索步長，在第一擴(kuò)大范圍的基礎(chǔ)上逐步按照第一搜索步長來擴(kuò)大搜索范圍，當(dāng)搜索范圍內(nèi)所選的需求方的需求總數(shù)量大于等于供給方的容量限度時，停止搜索。

5.根據(jù)權(quán)利要求1所述的區(qū)域劃分方法，其特征在于，步驟S5中，在確

定供給方或需求方是否分配完畢時，還包括：

當(dāng)無法按照剩余供給方的地理位置點(diǎn)構(gòu)建Voronoi圖時，則任選一個供給方，確定其地理位置坐標(biāo)點(diǎn)后，按預(yù)設(shè)的第二擴(kuò)大范圍和第二搜索步長來搜索區(qū)域范圍內(nèi)的需求方，并進(jìn)行需求總數(shù)量的計算；

將所得的需求總數(shù)量和所選供給方的容量限度進(jìn)行比較，直到達(dá)到需求方的分配條件時，停止搜索，并進(jìn)行下一供給方的選擇，直到供給方或需求方分配完畢時，輸出區(qū)域劃分結(jié)果。