Location Allocation Problem

Location Allocation Problem(Facility Location Problem)

給定許多個地點,設立p個聯絡站,使得每一個地點皆可被其中一間聯絡站聯絡到,而且越有效率越好。

深入地定義「效率」的意義,得以細分許多問題:令聯絡站離各地點的距離總和最小(p-Median Problem)。令聯絡站離各地點的距離最大值最小(p-Center Problem)。在各地設立聯絡站需要成本,但建立聯絡站後會從周遭地點獲得利益,令設立聯絡站後利益最大(Uncapacitated Facility Location Problem)。令各地點離聯絡站的中繼點不超過一定數量(Range Assignment Problem)。

這些問題在現實生活中的應用,例如超商的物流通路、有線電視的纜線鋪設、基地台的設立位置等等。可惜這些問題已經被證明是NP-hard問題,無法快速得到精準解答。

以下只討論一維版本。所有的地點和連絡站都在數線上。

p-Median Problem

p-Median Problem

給定許多個地點,設立p個聯絡站,使得每一個地點皆可被其中一間聯絡站聯絡到。令聯絡距離的總和最小。

此處討論一維版本,地點和連絡站落於數線上。

簡化問題、觀察問題:只有一個連絡站

將聯絡站放在中位數是最好的。如果中位數是在兩個位置中間的話,則聯絡站可以游移於兩個位置之間、其上,都不會改變聯絡距離的總和。所有的聯絡站都可以挪至地點之上!

證明不難。試著移動聯絡站,讓各個地點的聯絡距離此消彼長,觀察一下就會明白了。動手試試看吧!

另外也得到一個重要的結論:所有的聯絡站都可以挪至地點之上,而不會改變聯絡距離的總和。

簡化問題、觀察問題:只有一個地點

將全部的聯絡站放在該地點上是最好的。

聯絡站全部疊在一起,有摩肩接踵、水洩不通的感覺,理當好好分配才對。說到分配,如果聯絡站數量大於等於地點數量,只要將聯絡站安排在各個地點上,聯絡距離的總和就是零了。

簡化問題、觀察問題:地緣

為了拉近聯絡距離,所有地點都會連向最近的聯絡站,而不會有捨近求遠的情形。換個角度來看,一個聯絡站只會連向鄰近的地點,而不會有捨近求遠的情形。

p-Median Problem可以重新想成:依照地緣,所有地點分配成p個區域,每一區自行設立一個聯絡站,位於中位數,可挪至鄰近地點。

至此,p-Median Problem就成了如何分區的問題。

簡化問題、觀察問題:分區

如果有地點選擇聯絡站時捨近求遠,表示這種分區方式不好。

各個區域之間相鄰越遠越好?大家自行觀察看看吧。

動態規劃

聯絡距離的總和,可以以區為單位,分別計算,最後再統計——這就是在分割問題。

拿掉最邊邊的一區、拿掉該區的聯絡站,如此便縮小了問題範疇,讓小問題與原問題類似。接著窮舉該區的各種大小,求得遞迴式。

注意別讓剩下來的地點太少、剩下的聯絡站太多,而導致連絡站重疊。妥善分配重疊的聯絡站,一定能使聯絡距離的總和更小。沒有必要枚舉出讓聯絡站重疊的分區方式。

f(p, n) = 
 { min( f(p-1, p-1) + d(p  , n) ,
 {      f(p-1, p  ) + d(p+1, n) ,
 {      ...                     ,
 {      f(p-1, n-2) + d(n-1, n) ,
 {      f(p-1, n-1) + d(n  , n) )  if p < n  && n >= 0
 {
 { 0                               if p >= n && n >= 0
 { +inf                            otherwise

p:已設立了p個聯絡站。
n:已涵蓋了第1個到第n個地點。
f(p, n):設立p個聯絡站,涵蓋第1個到第n個地點時,其聯絡距離的總和。
d(i, j):第i個地點到第j個地點所構成的區域,其聯絡距離的總和最小值。
         可利用中位數算得。

N為地點個數,P為聯絡站個數。總共O(NP)個子問題,計算一個子問題需時O(N),時間複雜度為O(N²P)。

動態規劃:Monotonicity

不難發現,分界線位於最適中、最均衡的位置,讓聯絡距離的總和最小。

觀察地點逐步增加的問題們。最佳分界線漸漸右移。

觀察聯絡站逐步增加的問題們。最佳分界線漸漸右移。

因此我們不必窮舉所有的區域大小!但是時間複雜度仍然是O(N²P)。

UVa 662

動態規劃:Convex Hull

採用凸包優化,斜率皆是1,可視作deque優化,時間複雜度是O(NP)。

p-Center Problem

p-Center Problem

給定許多個地點,設立p個聯絡站,使得每一個地點皆可被其中一間聯絡站聯絡到。令聯絡距離的最大值最小。

也可以想做是:各個聯絡站各自使用一個圓,以自己為圓心,向外擴張以包住其負責的地點,然後讓最大的圓的半徑越小越好。

p-Center Problem的主要應用是設立基地台。基地台放送電波,地點距離越遠,就需要越多能量、耗費越多電能;跟地點個數無關。為了節省電能,所以要適當的安排基地台的位置,縮短電波的放送距離。

此處依舊討論一維版本。

簡化問題、觀察問題:只有一個連絡站

聯絡站放在相離最遠的兩個地點的正中央是最好的。應該不用證明了吧?

其他性質皆與p-Median Problem類似,不再複述。

p-Center Problem可以重新想成:依照地緣,所有地點分配成p個區域,找出最寬的區域,其寬度的一半,即是答案。

簡化問題、觀察問題:分區

p-Center Problem只關心最寬的區域,其餘區域的寬度根本無所謂,不要超過最寬的區域就好了。

動態規劃:Monotonicity

p-Center Problem特性更強。分界線往右移動,一旦左方最寬的區域的寬度(的一半),大於等於右方區域的寬度(的一半),分界線就沒有必要繼續往右移動。往右移動只會讓答案更大。

p-Median Problem僅掌握分界線的起點。p-Center Problem同時掌握起點與終點,時間複雜度為O(NP)。

試誤法:窮舉最寬的區域的寬度

p-Center Problem只關心最寬的區域。這種情況下,可以直接令每個區域都一樣大,跟最寬的區域一樣大,從第一個地點開始分區,儘量涵蓋越多地點。若能涵蓋全部地點,表示此寬度可行。

「最寬的區域」寬度適中,區域數量正確,可能是答案。

「最寬的區域」寬度太大,區域數量太少,可能是答案。

「最寬的區域」寬度太小,區域數量太多,不可能是答案。

寬度總共O(N²)種,驗證一種寬度需時O(N),時間複雜度為O(N³)。

或者實施排序、二分搜尋,時間複雜度為O(N²logN)。

或者length(i,j)是已排序矩陣,樓梯搜尋,時間複雜度為O(N²);二維二分搜尋,時間複雜度為O(NlogN)。

或者寬度取實際數值。下限是0,上限是最遠的兩個地點的距離L。時間複雜度為O(NlogL)。

UVa 714 11413 907

p-Coverage Problem

每個地點有半徑、支出、收入。連絡站建好後,涵蓋範圍為半徑、涵蓋到的地點有收入、沒涵蓋到的地點須支出,令總金額最高。