魏露

摘 ? 要：設施選址問題是組合優(yōu)化問題的經(jīng)典問題，是NP-困難問題，一般設計近似算法進行求解。文章研究的線性開設費用的在線設施選址問題是在線設施選址問題的變形問題。利用對偶擬合的技巧，給出了競爭比為4Hn的在線算法，其中n為出現(xiàn)的顧客個數(shù)。

關鍵詞：在線;設施選址;線性開設費用;競爭比

1 ? ?問題描述

線性開設費用的在線設施選址問題可描述為：給定設施集F，顧客集D，任意設施i∈F，開設費用為fi;任意顧客j∈D，服務需求量為dj，通常考慮dj=1的情形。設施i∈F為顧客j∈D提供一個單位服務量的費用為cij，稱為連接費用。假定連接費用cij是可度量的，即滿足（1）非負性cij≥0。（2）對稱性cij=cji。（3）三角不等式cij≤cik+cki。目標是選擇F的子集，開設中的設施，確定函數(shù)，依據(jù)函數(shù)將D中顧客連接到相應的設施上，在保證滿足D中所有顧客需求的前提下，使開設費用和連接費用總和達到最小[1]。

2 ? ?算法

將對偶規(guī)劃中的變量υjt看作是顧客（j，t）對總費用的貢獻，假設存在算法得到的解的費用為R，變量υjt的值滿足，若對于任意的O，有，其中，γ≥1是常數(shù)，那么該算法的近似比最多為γ。因為對于每一個在最優(yōu)解中開設的設施i以及在最優(yōu)解中連接到它上的顧客集合P，有，將該式對最優(yōu)解中的設施求和得到，算法得到解的費用不超過最優(yōu)解費用的γ倍，故算法的近似比為γ。也可以從原始對偶的角度來解釋近似比，不等式，表明如果將變量υjt一致放縮γ倍可以得到對偶問題的一個可行解且費用為，這個費用也是該問題最優(yōu)值的下界，這種方法稱為對偶擬合（Dual Fitting，DF）。

顧客的到達時間是未知的，當顧客到達時必須有開設的設施為其提供服務，并且一旦顧客連接到某個開設的設施上后，不能再改連其他設施上。根據(jù)這樣的思想設計算法，對每一個出現(xiàn)的顧客設置一個對偶變量υjt（可能是對偶不可行的），用Dt表示時刻t出現(xiàn)的顧客的集合，X表示已經(jīng)開設的設施的集合，且最初為空集。對于每一個先前出現(xiàn)的顧客（j，t）肯定已經(jīng)連接到X中某個開設的設施上，那么它對未開設的設施的預算為[C（X， j）-cij]，其中C（X， j）表示顧客j到集合X中的設施最近的距離，即;對于當前出現(xiàn)的顧客，它對未開設設施的預算為（υjt-cij）。用Si表示設施i當前服務的顧客集合。由于設置的對偶變量可能是不可行的，所以為了對算法的競爭比進行分析，利用對偶擬合的技巧將對偶變量一致縮小某一系數(shù)使得新的對偶變量可行。

4 ? ?結(jié)語

在線設施選址問題有機器廣泛的應用，線性開設費用的在線設施選址問題是其變形問題。本文根據(jù)問題的特殊性利用對偶擬合的技巧設計了競爭比為4Hn的算法，并且對算法進行了理論分析證明了競爭比。

本文只考慮了線性開設費用的在線設施選址問題，但在實際的生產(chǎn)和管理中，所遇到的問題會受到很多條件的約束，這使得設施選址問題存在大量的變形問題，例如在線的凹設施選址問題等。

[參考文獻]

[1]Hochbaum D S.Heuristics for the fixed cost median problem[J].Mathematical Programming，1982（1）：148-162.

[2]Guha S，Khuller S.Greedy strikes back：improved facility location algorithms[J].Jo-urnal of Algorithms，1999（31）：228-248.

[3]徐大川，張家偉.設施選址問題的近似算法[M].北京：科學出版社，2013.