清華新聞網(wǎng)8月9日電 競(jìng)爭(zhēng)性設(shè)施選址問(wèn)題（Competitive Facility Location Problem, CFLP）是指在多個(gè)市場(chǎng)主體之間為了贏(yíng)得同類(lèi)產(chǎn)品或服務(wù)的市場(chǎng)份額而開(kāi)展的一種博弈決策問(wèn)題，它有著廣泛的應(yīng)用基礎(chǔ)，例如零售店、購(gòu)物中心、停車(chē)場(chǎng)、租車(chē)店、電動(dòng)車(chē)充電站的選址等。其中，序貫（Sequential）競(jìng)爭(zhēng)性設(shè)施選址問(wèn)題（S-CFLP）考慮一種更加復(fù)雜的決策環(huán)境，即市場(chǎng)中的主導(dǎo)方（leader）在進(jìn)行自己的選址決策時(shí)，還必須預(yù)計(jì)跟隨方（follower）在得知主導(dǎo)方?jīng)Q策后所做出的最優(yōu)反制決策，從而使主導(dǎo)方得到具有預(yù)見(jiàn)效果的最優(yōu)決策，屬于一種斯坦伯格博弈問(wèn)題。常規(guī)的CFLP問(wèn)題可以建模為一個(gè)單層的混合整數(shù)線(xiàn)性規(guī)劃（MILP），或者混合整數(shù)凹優(yōu)化模型，求解相對(duì)容易，而S-CFLP問(wèn)題則是一個(gè)上下兩層均為混合整數(shù)非線(xiàn)性規(guī)劃（MINLP）的雙層規(guī)劃問(wèn)題，其求解難度極大，除了暴力枚舉法之外，目前尚沒(méi)有能求解這一問(wèn)題的精確算法。
圖1. 序貫競(jìng)爭(zhēng)性設(shè)施選址問(wèn)題求解界面（圓點(diǎn)為顧客點(diǎn)，黑色方框?yàn)楹蜻x設(shè)施點(diǎn)，紅色方塊為領(lǐng)導(dǎo)者所選的設(shè)施，紅十字為跟隨者選擇的設(shè)施）
針對(duì)這一復(fù)雜的優(yōu)化問(wèn)題，清華大學(xué)深圳國(guó)際研究生院戚銘堯副教授與美國(guó)密歇根大學(xué)安娜堡分校江瑞威副教授和沈思倩副教授合作，提出了一種高效的精確算法。首先，將原始的雙層優(yōu)化問(wèn)題通過(guò)巧妙的數(shù)學(xué)變換，等價(jià)轉(zhuǎn)化為一種單層混合整數(shù)非線(xiàn)性規(guī)劃模型（MINLP）。其次，為了處理棘手的混合整數(shù)非線(xiàn)性約束，該研究推導(dǎo)出了兩類(lèi)有效不等式（線(xiàn)性約束）來(lái)代替非線(xiàn)性約束：一類(lèi)是將領(lǐng)導(dǎo)者的市場(chǎng)份額函數(shù)轉(zhuǎn)化為一個(gè)集合函數(shù)，并證明該函數(shù)具有次模性（Submodularity），從而推導(dǎo)出一種次模割（Submodular Cut）；另一類(lèi)是利用決策變量是0-1變量的特點(diǎn)，將原本非凸非凹的市場(chǎng)份額函數(shù)放大為一個(gè)凹函數(shù)，同時(shí)保持整數(shù)解上的值不變，從而在整數(shù)解上生成外逼近割（Outer Approximation Cut）。通過(guò)生成這兩種割，使得問(wèn)題的求解速度提高了至少兩個(gè)數(shù)量級(jí)。此外，由于生成有效不等式（割）需要求解出下層問(wèn)題，該研究進(jìn)一步提出了一種可以在多項(xiàng)式時(shí)間內(nèi)求解下層問(wèn)題的近似算法，使得算法速度再次提高2-3倍。最后，該研究還提出了一種近似求解模型，能把原問(wèn)題轉(zhuǎn)化為一個(gè)具有精度保證的混合整數(shù)二階錐規(guī)劃（MISOCP）問(wèn)題，從而可以直接用已有的求解器來(lái)求解。
圖2. 原始市場(chǎng)份額函數(shù)（左）和凹化后的市場(chǎng)份額函數(shù)（右），見(jiàn)曲面和平面的交線(xiàn)
數(shù)值實(shí)驗(yàn)表明，基于等價(jià)模型及其算法，可以求得最優(yōu)解的問(wèn)題規(guī)模達(dá)到100個(gè)候選設(shè)施、2000個(gè)顧客點(diǎn)，這個(gè)規(guī)模對(duì)于精確算法來(lái)說(shuō)已經(jīng)足夠大，甚至遠(yuǎn)高于已有的啟發(fā)式算法所能求解的規(guī)模。數(shù)值實(shí)驗(yàn)還表明，算法只需要用最初的幾次迭代（數(shù)秒內(nèi)），即可得到離最優(yōu)解非常接近的近似解（gap<3%），這表明算法還可以為實(shí)際應(yīng)用中可能出現(xiàn)的更大規(guī)模的問(wèn)題提供高質(zhì)量的近似解。利用所提出的理論方法，該研究還探討了用戶(hù)選擇模型的參數(shù)取值對(duì)選址行為的影響。研究發(fā)現(xiàn)，反映空間阻隔效應(yīng)的參數(shù)越小，領(lǐng)導(dǎo)者和跟隨者的設(shè)施選址都宜盡量靠近市場(chǎng)區(qū)域中心，而當(dāng)空間阻隔效應(yīng)較大時(shí)，二者的設(shè)施宜在區(qū)域內(nèi)相對(duì)分散。該研究還對(duì)問(wèn)題假設(shè)進(jìn)行了多方面的拓展，使得所提出的方法還可以適用于更多的場(chǎng)景，例如：同時(shí)決策設(shè)施的規(guī)模、考慮更多的市場(chǎng)競(jìng)爭(zhēng)者、市場(chǎng)聚集效應(yīng)等。
該研究工作以“序貫競(jìng)爭(zhēng)性設(shè)施選址：精確與近似算法”（Sequential Competitive Facility Location: Exact and Approximate Algorithms）為題，發(fā)表在國(guó)際學(xué)術(shù)期刊《運(yùn)籌學(xué)》（Operations Research）上。清華大學(xué)深圳國(guó)際研究生院戚銘堯副教授為文章的第一作者，美國(guó)密歇根大學(xué)安娜堡分校江瑞威副教授為第二作者，該校沈思倩副教授為第三作者兼通訊作者。該工作得到國(guó)家自然科學(xué)基金面上項(xiàng)目資助。
論文鏈接：
https://pubsonline.informs.org/doi/abs/10.1287/opre.2022.2339
供稿：深圳國(guó)際研究生院
編輯：李華山
審核：呂婷
