線性開設(shè)費(fèi)用在線設(shè)施選址問題的算法研究

魏露

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

關(guān)鍵詞：在線;設(shè)施選址;線性開設(shè)費(fèi)用;競(jìng)爭(zhēng)比

1 ? ?問題描述

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

2 ? ?算法

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

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

4 ? ?結(jié)語

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

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

[參考文獻(xià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]徐大川，張家偉.設(shè)施選址問題的近似算法[M].北京：科學(xué)出版社，2013.