物流配送中心選址問題的0—1規劃并行算法
2012-04-29 00:00:00沈萍陳燕李捷楊雪君
計算技術與自動化 2012年3期
摘要：建立物流配送中心選址問題的0—1混合整數規劃模型，并結合目標排序法和改進的PSRS設計求解0—1規劃的并行算法。改進PSRS可將各個目標的驗證任務進行均衡劃分，并提交給各個處理器并行進行可行性驗證，算法理論上具有接近處理器個數p的加速比。
關鍵詞：配送中心選址；0—1整數規劃；并行算法；PSRS
中圖分類號：TP301.6 文獻標識碼：A
0—1 Integer Programming Model and Parallel Algorithm for Location of Logistics Distribution Centers
SHEN Ping1，2，CHEN Yan1，LI Jie2，YANG Xuejun3
（1.School of Computer， Electronics and Information， Guangxi University， Nanning530004， Guangxi， China；
2. Department of Computer， Electronics and Information Engineering， Guangxi Polytechnic， Nanning530226， Guangxi， China；
3.Guangxi Electronic Products Supervising And Testing Institude，Nanning530031，China）
Abstract：According to the theory of 0—1 programming， this paper presents the model for the problem of logistics distribution centers location. And a new parallel algorithm for the proposed model is given based on objective values sorting and improved PSRS. The tasks of verify solutions have been partitioned and submited to p processors， which verify solutions in parallel. The proposed method have excellent speed up in p.
Key words：location of logistics distribution centers；0—1 integer programming；parallel algorithm；PSRS
1引言
在物流網絡中，配送中心是供需雙方的連接紐帶，是整個物流系統的核心。如何有效的進行配送中心的選址是物流網絡系統規劃的核心問題，往往決定物流配送網絡系統的結構、形狀和配送模式，進而對物流系統的運作效率乃至物流行業經濟效益的提高有重大影響。
針對配送中心選址的研究，國內外的學者主要圍繞配送中心選址模型的建立和求解兩方面展開研究，在理論和實踐上都取得了較大的成果。目前物流中心選址模型大致可分為連續性模型和離散性模型兩類。連續性模型對備選地點沒有特別限制，但是有可能得出沒有實際意義的選址結果，其代表性的方法是重心法；離散性模型則是在有限的備選地點中選擇最佳的地點，獲得的選址結果較符合實際情況，其代表性的方法有整數或混合整數規劃法、運輸規劃法、Cluster 法、KuehnHamburger模型、Elson模型等[1—3]。由于離散型方法在理論和應用上的顯著優勢，是目前物流配送中心選址問題的主要研究方向[1]。而0—1規劃是整數規劃中的一種特殊的形式，這種規劃決策變量僅取值0或者1。0—1規劃非常適合描述和解決配送中心選址問題。
隨著應用問題的規模和精度要求越來越高，在單一處理器上進行大規模和超大規模的0—1規劃問題求解所需計算時間越來越長，因此尋求縮短計算時間以提升計算效益成為當務之急。分布式并行計算技術的產生與發展，為進一步提高LP求解速度帶來了契機[4，5]。
本文首先采用0—1規劃模型對物流配送中心選址問題進行描述，并基于改進的PSRS（正則采樣排序算法）[5，6]給出了一種求解物流配送中心的0—1規劃模型的并行算法。仿真結果表明，算法能有效求解中大規模物流配送中心選址問題，且具有較好的加速比和可擴展性。
2配送中心選址問題的0—1規劃模型
設m表示需求點的數量；（xi，yi）表示第i個需求點的坐標（i=1，2，…，m）；Si表示第i個需求點的需求量；n表示物流中心的數量；（xj，yj）表示第j個物流中心的坐標；uj表示第j個物流中心的流量限制；rj表示第j個物流中心的容量限制；Lij表示第i個物流中心到第j個需求點的距離；Sij表示由產品運輸了L距離時的剩余量；θ表示產品在運輸過程中，物流中心向需求點配送的產品單位距離內的衰減率；fij表示由第j個物流中心向第i個需求點配送農產品所需的運費；ω表示單位農產品的價值。同時定義以下符號：
計算技術與自動化2012年9月
第31卷第3期沈萍等：物流配送中心選址問題的0—1規劃并行算法
xij=1 supply i from j0 otherwise
Lij=（xj—xi）2+（yj—yi）2
由于產品以恒定速率衰減，因此：
Sij（0）（1—θ）Lij=Sij（Lij），Sij（Lij）=Si
由上式顯然有：Sij（0）=Si/（1—θ）Lij
由于產品在運輸過程中的衰減，若要滿足第i個需求點的需求，就必須要從第Si個物流中心補運TD個單位產品，其中：TD=Si/（1—θ）Lij
因而對應運費為：fij=LijSi/（1—θ）Lij
當產品由第j個物流中心送至第i個需求點時，價值為：ω[Si（1—θ）Lij—Si]=ωSi[1/（1—θ）Lij—1]
則物流中心總費用為：
z=∑nj=1∑mi=1[LijSi/（1—θ）Lij+ωSi[1/（1—θ）Lij—1]]xij
從而得到物流配送中心問題的數學模型為：
min z=∑nj=1∑mi=1[Si/（1—θ）Lij+（Lij+ωSi）]xij
s.t.∑mi=1Sixij≤rj∑mi=1Sixij/T≤ujj=1，2，…n
為方便討論本文將以上模型表示為以下一般形式：
max z=f（X）
s.t.hi（X）=0，i=1，2，…，mgj（X）≥0，j=1，2，…lxk∈{0，1}，k=1，2，…n
30—1規劃模型的并行求解
3.1目標排序法
目標排序法是求解0—1整數規劃問題的有效方法。大致的思路為：把所有可能的解都代入目標函數算出值，然后把這些目標函數值進行排序，如果是求最大值，則降序排列，反之則升序。然后按這個順序逐個檢驗對應的解的可行性，當碰到第一個可行解時即得到最優解。該方法通過快速提高約束門檻可以大規模的減少檢查的數量。具體步驟如下：
1）首先求出所有的解（包括可行解和非可行解）對應的目標函數值Z向量。
2）然后將Z向量進行按大到小排序。
3）最后按順序對每個解的可行性進行檢查。若極大化則從大到小檢查，若極小化則從小到大檢查。檢查中發現的第一個可行解就是最優解。
該方法其本質依然是窮舉法，當問題規模較大時，依然會遇到計算量極大的問題：如果變量為N個，則需求2N個目標函數值，然后還要進行排序，這是工作量很大的問題，再一個就是，如果排序結果是把最優解排在最后一個，那還得進行2N次檢驗。所以通過并行計算加快其求解速度十分有必要。
3.2改進的PSRS算法
PSRS是一種基于均勻劃分原理的負載均衡的并行排序算法[5，6]。待排序元素為n個，系統有處理器p個，系統先將n個元素均勻地分割成p段，每段指派一個處理器，然后各個處理器并行進行局部排序。然后從各個處理器中抽取p—1個樣本，再對樣本元素排序，然后從有序的樣本元素中抽取劃分元素共p—1個將樣本均分為p段，有理由相信這些樣本元素的劃分元素也近似的將原來的序列均分為p段，接著通過全局交換將各個段中的對應部分集合在一起，最后將這些集合在一起的各部分采用多路歸并的方法進行排序，這些有序段匯合起來就自然成為全局有序序列了。
由于目標排序法中需要用有序的Z值序列來控制整個約束條件的檢查，假設Z的有序序列為（z1，z2，z3，…zγ）其中γ=2n且z1≥z2≥z3，…≥zγ。如果并行環境下有p個處理器，那么我們希望經過排序以后的Z''為：
c1，cp+1，c2p+1，…c（γ/p—1）p+1P1，
c2，cp+2，c2p+2，…c（γ/p—1）p+2P2，
cp，c2p，c3p，…，cγPP
圖1排序后的新序列
上述情況中，假設目標函數值個數r剛好可以被處理器個數p整除，若不能整除，可以按照上述序列依次分配給各個處理器，并不要求各個處理器上的個數嚴格相同。
3.3求解0—1規劃的并行算法
第一步：計算函數值任務分發。把求解函數值的任務分給各個處理器來做。各個處理器平均要計算r/p個函數值（γ=2n）；
第二步：采用改進的PSRS算法對各個處理器上的函數值進行\"排序\"，得到圖1所示的序列；
第三步：各處理器按函數值Zi從大到小檢查所對應的決策變量xi是否滿足約束條件，若不滿足，則i++，轉到第四步；若滿足約束條件則把Zi和Xi發給其他的處理器，并停止計算；
第四步：若處理器pj接收到其他處理器發送來的數據時，則將數據和當前的檢查的數據進行對比：如果當前檢查的函數值比發送來的函數值小，則停止本進程，并發消息通知p0，本進程已經結束；轉到第五步；
第五步：對于處理器p0，若接收到了所有的結束的通知，則找出了最優值和最優值所對應的最優解。
4數值實驗
數值實驗中本文在我國的20個大中城市中，選擇出10個以下的城市做為配送中心。要求如下：
1）我國的20個備選的大中城市是：北京、上海、廣州、南京、武漢、成都、重慶、沈陽、深圳、杭州、長沙、南寧、福州、南昌、昆明、長春、石家莊、香港、澳門、臺北。
2）在20個城市中選出10個以下（含10）城市做為配送中心。
3）市場需求指數之和超過3。
4）城市交通便利指數和超過30。
5）可開發市場潛力指數和大于3.5。
6）總的建設利益Z=∑2011000q—c+10*t+100f最大。
實驗平臺：集群環境由2臺PC機搭建，2臺PC機各擁有2.99GHz和3.00GHz的處理器和512MB和1GB內存。編程環境為VC++6.0下調用MPI接口。
表1給出了算法串并行執行結果比較。并行環境下運行時間為1.284秒，比串行程序的2.203秒快0.919秒。加速比為1.716。
表1執行結果比較
比較項目
串行
并行
運行前內存使用
293MB
293MB
1.02GB
運行時內存使用
593MB
454MB
1.14GB
程序凈使用內存
300MB
161MB
120MB
執行時間
2.203秒
1.284秒
總內存
300MB
281MB
5結論
本文給出了物流配送中心選址問題的0—1整數規劃模型，并結合改進PSRS以及目標排序法設計了一個物流配送中心選址問題的的并行求解算法。算法通過改進PSRS將問題求解中的主要工作進行均衡的任務劃分，理論上可以得到接近p的加速比。數值實驗結果有效驗證了本文所提算法的有效性。
參考文獻
[1]Byrka J，Aaprdal K. An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem[J].SIAM Journal on Computing，2010，39（ 6） ： 2212—2231.
[2]Fellowsa M R，Fernau H. Facility location problems： a parameterized view[J].Discrete Applied Mathematics，2011，159（11）： 1118—1130.
[3]孫會軍，高自友.供應鏈分銷系統雙層優化模型[J].管理科學學報，2003，6（ 3）： 66—70.
[4]陳國良. 并行算法的設計與分析（修訂版）[M]. 高等教育出版社， 2002.11
[5]楊林峰，李捷，陳燕. 基于改進PSRS的并行0—1規劃算法. 計算機工程與設計. 2008.9， 29（17）： 4491—4493.
[6]H. Shi and J.Schaeffer. Parallel Sorting by Regular Sampling[J]. Journal of Parallel and Distributed Computing，14（4）， 1992.
