[發(fā)明專利]一種用于選址問題的魯棒優(yōu)化模型求解方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201810293335.5
• 申請(qǐng)日: 2018-04-04
• 公開（公告）號(hào): CN108665089B
• 公開（公告）日: 2022-04-15
• 發(fā)明（設(shè)計(jì)）人: 游科友;謝佩;宋士吉;吳澄
• 申請(qǐng)（專利權(quán)）人: 清華大學(xué)
• 主分類號(hào): G06Q10/04
• 分類號(hào): G06Q10/04;G06Q10/06
• 代理公司: 北京清亦華知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11201
• 代理人: 廖元秋

本發(fā)明提出一種用于選址問題的魯棒優(yōu)化模型求解方法，屬于運(yùn)籌學(xué)與優(yōu)化算法的應(yīng)用技術(shù)領(lǐng)域。該方法首先建立用于選址問題的魯棒凸優(yōu)化模型，并轉(zhuǎn)化為對(duì)應(yīng)的參數(shù)約束模型；然后參數(shù)約束模型轉(zhuǎn)化為近似模型，確定該近似模型不確定集采樣的樣本個(gè)數(shù)，將約束條件分配到相應(yīng)進(jìn)程上并構(gòu)建進(jìn)程之間的通信的權(quán)重矩陣；根據(jù)進(jìn)程間通信方式為無向通信或有向通信設(shè)計(jì)了兩種分布式算法，通過迭代求解，得到選址問題的最優(yōu)結(jié)果。本發(fā)明可以在面臨大量服務(wù)對(duì)象構(gòu)成的復(fù)雜且不確定需求的條件下做出更加魯棒的選址決策，有助于各應(yīng)用領(lǐng)域由于優(yōu)化選址而產(chǎn)生良好的技術(shù)效果，最小化由于選址不當(dāng)帶來的潛在風(fēng)險(xiǎn)。

技術(shù)領(lǐng)域

本發(fā)明屬于運(yùn)籌學(xué)與優(yōu)化算法的應(yīng)用技術(shù)領(lǐng)域，具體涉及一種用于選址問題的魯棒優(yōu)化模型求解方法。

背景技術(shù)

選址問題是運(yùn)籌學(xué)中經(jīng)典的問題之一。選址作為一類重要的長(zhǎng)期決策問題，在生產(chǎn)、生活、物流中都有著非常廣泛的應(yīng)用，如工廠、物流中心、醫(yī)院、消防站的選址等。以消防站的選址為例，為提高消防站對(duì)于火災(zāi)發(fā)生的救災(zāi)效率，通常希望消防站離火災(zāi)發(fā)生概率較高的服務(wù)對(duì)象更近。然而實(shí)際情況是，服務(wù)對(duì)象發(fā)生火災(zāi)的概率是存在不確定性的，且消防站到服務(wù)對(duì)象這一段路程可能存在其他不確定事件，如堵車等。因此常規(guī)的確定性選址模型無法得到魯棒的解，使得在某些最壞的情況下消防站無法及時(shí)趕到火災(zāi)現(xiàn)場(chǎng)進(jìn)行及時(shí)的救災(zāi)。因此需要考慮參數(shù)的不確定性，包括服務(wù)對(duì)象位置的不確定性、服務(wù)對(duì)象對(duì)服務(wù)距離的代價(jià)系數(shù)的不確定性等，從而建立新的不確定性模型。

早出現(xiàn)的針對(duì)模型不確定性的研究是隨機(jī)優(yōu)化模型。在隨機(jī)優(yōu)化模型中，不確定參數(shù)被看作是一個(gè)分布已知的隨機(jī)變量，隨機(jī)規(guī)劃的三個(gè)分支是期望值模型、機(jī)會(huì)約束規(guī)劃和相關(guān)機(jī)會(huì)規(guī)劃，均為在一定的概率意義下達(dá)到最優(yōu)的理論。其中機(jī)會(huì)約束規(guī)劃考慮到所做決策在不利的情況發(fā)生時(shí)可能不滿足約束條件，即允許所做決策在一定程度上不滿足約束條件，但該決策使約束條件成立的概率不小于某一個(gè)足夠小的置信水平。隨機(jī)優(yōu)化的缺點(diǎn)主要體現(xiàn)在以下幾個(gè)方面：1)在隨機(jī)優(yōu)化模型中，不確定參數(shù)的分布是需要精確知道的；2)在隨機(jī)優(yōu)化模型中，一般采用某種系統(tǒng)性能的期望作為優(yōu)化目標(biāo)，具有一定局限性；3)當(dāng)問題比較復(fù)雜是，隨機(jī)優(yōu)化模型難以建立，且求解困難，甚至只能使用某些啟發(fā)式算法。

由于隨機(jī)優(yōu)化模型具有以上缺點(diǎn)，另一種處理參數(shù)不確定性的魯棒優(yōu)化模型得到了研究者的關(guān)注。魯棒優(yōu)化模型的不確定參數(shù)通過區(qū)間數(shù)據(jù)情景進(jìn)行刻畫(一個(gè)情景代表不確定參數(shù)的一種可能的取值)，相較于隨機(jī)模型，魯棒模型面對(duì)不確定參數(shù)分布未知的情況更有效。魯棒優(yōu)化的理論由90年代末Ben-Tal引領(lǐng)，在最近十幾年內(nèi)得到長(zhǎng)足的發(fā)展。其基本思想是解決魯棒可行問題，求解最壞情況下的最優(yōu)值。針對(duì)目標(biāo)函數(shù)和約束為凸函數(shù)的問題，通過簡(jiǎn)單的松弛技術(shù)可將魯棒凸優(yōu)化問題轉(zhuǎn)化為目標(biāo)函數(shù)為線性，約束為包含不確定參數(shù)的凸不等式的問題。求解魯棒優(yōu)化問題的關(guān)鍵是計(jì)算魯棒可行集，但在大多數(shù)情況下不確定參數(shù)集合的復(fù)雜性會(huì)導(dǎo)致魯棒可行集難以計(jì)算。因此Campi等提出一種近似求解魯棒優(yōu)化問題的方法——場(chǎng)景建模法，參數(shù)在不確定集中進(jìn)行隨機(jī)采樣得到許多個(gè)場(chǎng)景約束，最終解決包含所有場(chǎng)景約束的一般優(yōu)化問題。顯然采樣的場(chǎng)景約束越多，新問題越接近精確魯棒優(yōu)化問題，新問題的可行解不滿足魯棒約束的概率和采樣場(chǎng)景約束個(gè)數(shù)之間的關(guān)系也在Campi的工作中得到定量刻畫。

使用場(chǎng)景建模法求解魯棒優(yōu)化問題最大的挑戰(zhàn)是：要獲得精度足夠高的魯棒解需要生成大量的約束，因而需要很長(zhǎng)的求解時(shí)間。

發(fā)明內(nèi)容

本發(fā)明的目的是為克服已有技術(shù)的不足之處，提出一種用于選址問題的魯棒優(yōu)化模型求解方法。本發(fā)明可以在面臨大量服務(wù)對(duì)象構(gòu)成的復(fù)雜且不確定需求的條件下做出更加魯棒的選址決策，使得在某服務(wù)對(duì)象在最糟糕的情況下也可以被選定地址的服務(wù)中心所快速響應(yīng)。同時(shí)，基于分布式求解的構(gòu)架，所有服務(wù)對(duì)象可以通過和相鄰的服務(wù)對(duì)象交換信息來分布式地進(jìn)行最優(yōu)決策，即使服務(wù)對(duì)象的相關(guān)信息無法全局獲得，也能求得全局魯棒最優(yōu)的選址，有助于各應(yīng)用領(lǐng)域由于優(yōu)化選址而產(chǎn)生良好的技術(shù)效果，最小化由于選址不當(dāng)帶來的潛在風(fēng)險(xiǎn)。

本發(fā)明提出一種用于選址問題的魯棒優(yōu)化模型求解方法，其特征在于，該方法包括以下步驟：