[發明專利]一種連續空間的位置分配問題的優化計算方法

有效

• 申請號: 202110337845.X
• 申請日: 2021-03-30
• 公開（公告）號: CN113159392B
• 公開（公告）日: 2022-06-24
• 發明（設計）人: 劉昊戈
• 申請（專利權）人: 劉昊戈;托爾·伯格·斯特雷·雅仕維克
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/02
• 代理公司: 青島高曉專利事務所(普通合伙) 37104
• 代理人: 白瑩;于正河

本發明屬于工程布局系統中的優化計算技術領域，具體涉及一種連續空間的位置分配問題的優化計算方法，先根據聯系成本的定義找到潛在簇，再計算每個潛在簇的供給點位置和該簇的聯系成本，然后建立潛在簇的等價有損ILP模型，最后通過ILP求解器求解等價有損ILP模型的全局最優解，能夠有效提高連續空間位置分配問題全局最優解的計算效率，更加穩定和快速地得到全局最優解，降低實際工程面對此類問題時的時間成本和經濟成本，滿足實際工程需求，為實際工程系統的分析和優化提供了算法保障；其設計理念先進，計算方法科學，計算手段簡單，應用于各種油氣田開發布局優化、通信基站選址和數據工程聚類等場合的位置分配的優化計算。

技術領域：

本發明屬于工程布局系統中的優化計算技術領域，具體涉及一種連續空間的位置分配問題的優化計算方法，應用于各種油氣田開發布局優化、通信基站選址和數據工程聚類等場合的位置分配的優化計算。

背景技術：

在現有的工程技術領域中，位置分配問題是一個經典的組合優化問題，也是公認的NP-Hard問題。NP-Hard問題的特點在于隨著問題規模的增加，計算量會急劇增加，以至于某些日常生產生活中常見規模的問題都難以求得精確解。目前常見的位置分配問題可以抽象化描述為：已知n個需求點位置，欲找尋k個(1≤k≤n)供給點位置，將供給點與需求點建立聯系，使所有需求點有且僅有一個供給點與之聯系，并且聯系成本總和最小。其中一個供給點與需求點之間的聯系成本可以是關于供給點和需求點的位置和數量的任何函數，可用如下公式所示的數學模型表達：

s.t.C∈R，δ∈Binary (1.b)

其中，C為成本矩陣，維度是K×n,K為不小于k的任意整數，c_i,j代表第i個供給點與第j個需求點之間的聯系成本，c_i,j的值可以是任意實數；δ為“供給點-需求點”關系矩陣，是一個二值決策矩陣，維度是K×n，用以表征需求點與供給點是否有聯系：δ_i,j＝1代表第i個供給點與第j個需求點之間有聯系，δ_i,j＝0代表第i個供給點與第j個需求點之間不聯系。

公式(1.a)表示模型優化的目標函數，即需求點與供給點之間聯系成本總和最小；公式(1.b)和(1.c)為模型的約束條件，根據實際問題進行改動。比如，在原有模型基礎上再要求每個供給點最多只能與m個需求點聯系，則需增加公式(1.d)：

無論約束條件如何變化，位置分配問題的本質是在滿足各種約束條件下，求得決策矩陣δ的取值，即確定好最優的“需求點-供給點”關系，實現目標函數。從公式(2.b)可以看出此類問題的計算復雜度非常高：在沒有任何約束條件下，所有可能的組合數是2^Kn。

當存在有限K個(k≤K)候選供給點位置時，即k個最佳供給點的位置只能從K個候選供給點位置中做出選擇時，化歸為離散空間的位置分配問題。由于每個候選供給點與任意指定的需求點之間的聯系成本因為候選供給點位置的確認可以明確地計算得出，使得公式(1.a)中的C成為與δ無關的常數項，從而將問題歸結為相對簡易的線性優化(LinearProgramming,簡稱LP)模型。這種情況下，LP模型中未知項僅含有整數型未知量δ，因而又被稱為整型線性優化(Integer Linear Programming,簡稱ILP)模型。