基于0-1整數規(guī)劃算法的城市地下物流系統(tǒng)網絡節(jié)點選址

方龍祥，于雪雨

(安徽師范大學 數學與統(tǒng)計學院，安徽 蕪湖 241002)

城市地下物流系統(tǒng)是通過城市地下隧道或管道進行固體貨物運輸的系統(tǒng)，該系統(tǒng)將存儲在物流園區(qū)、物流基地的貨物智能配送到各個終端[1]，“及時配送”是地下物流系統(tǒng)的重要特征。城市地下物流系統(tǒng)具有廣闊的發(fā)展前景，它的數字化、智能化、自動化、網絡化程度較高，可以很好地解決目前物流業(yè)制約電子商務發(fā)展的問題[2]。構建城市地下物流系統(tǒng)有利于經濟的快速增長與環(huán)境的可持續(xù)發(fā)展。從城市地下物流系統(tǒng)網絡節(jié)點的選址入手構建合肥市地下物流系統(tǒng)，探索一種較為新穎的貨物運輸方式，從而提高城市物流效率，緩解城市交通擁堵，實現城市的可持續(xù)發(fā)展。

1 數據來源

地下物流系統(tǒng)還處于理論分析與預測階段，較難獲得精確的數據資料。研究的實證分析部分主要是對合肥市較為擁堵區(qū)域(合肥二環(huán)及周邊區(qū)域)的地下物流系統(tǒng)網絡進行初步探索，所以物流供需點多選在合肥市二環(huán)及周邊人流量較大的區(qū)域如生產用地、倉儲用地、居民區(qū)、商業(yè)中心等。選中的供需點分布情況如圖1所示。為了實證分析的需要提取了各點的經緯度坐標如表1所示。其中，Si(i=1,2,3,…,21)為貨物供應點；ei(i=1,2,3,…,21)為貨物需求點。

表1 各貨物供應點與需求點經緯度坐標

圖1 貨物供應點與需求點分布

2 數據處理

根據表1中合肥市供應點與需求點的分布經緯度坐標，在地圖上進一步測量了供應點與需求點的距離如表2所示。

由以往研究可知，地下物流系統(tǒng)網絡節(jié)點的服務半徑為3～5 km,這里假定節(jié)點的服務范圍為3 km[3]。結合表2得到各貨物供應點到需求點的可達矩陣如表3所示。令可達矩陣為Aij=aij，其中，aij=1或aij=0表示第j列供應點覆蓋了第i行需求點或者第j列供應點沒有覆蓋第i行需求點。

3 問題描述

研究是在已知一組貨物需求點與貨物供應點的情況下，要求從上述供應點中選擇一組貨物供應點為所有需求點提供服務，且為了節(jié)省前期的建設成本，選中的這組貨物供應點的數量要盡可能的少，這是典型的集合覆蓋問題[4]。

4 模型構建

集合覆蓋模型是一種典型的組合優(yōu)化模型，它要求用最少的網絡節(jié)點將所有需求點全覆蓋[5]。當問題的規(guī)模較小時求解這類問題可以使用0-1整數線性規(guī)劃的方法。

表2 貨物供應點與需求點的距離

表3 供應點到需求點的可達矩陣

xj=0,1；J=1,2,…,m

為了便于討論，放松IP變量的整數性要求，得到了它的松弛線性規(guī)劃問題，令LP代表此規(guī)劃問題的模型[7]：

xj=0,1；J=1,2,…,m

顯然，由IP和LP之間的松弛關系可知，OPTLP≤OPTIP、其中OPTLP、OPTIP分別為LP、IP的最優(yōu)值。

再由線性規(guī)劃的對偶理論可知LP的對偶問題，這里將其設為DP：

yi=0,i=1,2,…,n

5 模型求解

由于數據量較少所以采用較為精確的模型求解算法即0-1整數規(guī)劃算法。同樣根據表3供應點到需求點的可達矩陣，找到給每一個需求點提供服務的所有候選的貨物供應點集合，如表4所示。

研究0-1整數規(guī)劃算法的實現使用了LINGO軟件。LINGO軟件是常見求解線性規(guī)劃問題的軟件，下面是使用LINGO軟件實現此算法的主要程序代碼，運行結果如表5所示。

min=x1+x2+x3+x4+x5+x6+x7+x8+x9+

x10+x11+x12+x13+x14+x15+

x16+x17+x18+x19+x20+x21;

x4+x14+x17>=1;

x1>=1;

x2>=1;

x5+x6+x13>=1;

x5+x13+x14+x15>=1;

x2+x5+x13+x14+x15>=1;

x14+x15+x17>=1;

x12+x13+x14+x15+x17>=1;

x5+x12+x13+x14+x20>=1;

x12+x13+x20>=1;

x3+x7+x15+x17>=1;

x10+x16+x19>=1;

x10+x14+x17+x19>=1;

x10>=1;

x8+x9+x18>=1;

x3+x8+x9+x18>=1;

x10+x11+x12+x19>=1;

x3>=1;

x6+x21>=1;

@bin(x1);

@bin(x2);

@bin(x3);

@bin(x4);

@bin(x5);

@bin(x6);

@bin(x7);

@bin(x8);

@bin(x9);

@bin(x10);

@bin(x11);

@bin(x12);

@bin(x13);

@bin(x14);

@bin(x15);

@bin(x16);

@bin(x17);

@bin(x18);

@bin(x19);

@bin(x20);

@bin(x21);

End

表4 貨物供應點集合

表5 Lingo運行結果

變量取值成本X111X211X311X401X501X611X701X801X901X1011X1101

變量取值成本X1201X1311X1401X1501X1601X1711X1811X1901X2001X2101

由上面0-1整數規(guī)劃算法的求解結果可以看出，最少需要S1、S2、S3、S6、S10、S13、S17、S18這8個物流供應點才能全覆蓋所有貨物需求點。最終選中的網絡節(jié)點分布情況如圖2所示。

圖2 最終網絡節(jié)點分布圖

6 結論

通過分析以往文獻了解到選址問題所用的模型及相關算法，在對比分析各種算法優(yōu)缺點的基礎上，采用0-1整數規(guī)劃算法對模型進行求解。以合肥市二環(huán)及周邊區(qū)域的數據為例進行了實證分析，最終得到了地下物流系統(tǒng)網絡節(jié)點分布圖。城市地下物流系統(tǒng)網絡節(jié)點的選址涉及到多方面的因素，包括當地物流業(yè)的分布、商品流向、政府政策、科技水平等。研究考慮的范圍有限，在現實的網絡節(jié)點選址中應該集多人的力量從更多的角度剖析問題，這樣才能做出更加科學、全面的考慮。