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

方龍祥，于雪雨

(安徽師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，安徽 蕪湖 241002)

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

1 數(shù)據(jù)來源

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

表1 各貨物供應(yīng)點(diǎn)與需求點(diǎn)經(jīng)緯度坐標(biāo)

圖1 貨物供應(yīng)點(diǎn)與需求點(diǎn)分布

2 數(shù)據(jù)處理

根據(jù)表1中合肥市供應(yīng)點(diǎn)與需求點(diǎn)的分布經(jīng)緯度坐標(biāo)，在地圖上進(jìn)一步測量了供應(yīng)點(diǎn)與需求點(diǎn)的距離如表2所示。

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

3 問題描述

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

4 模型構(gòu)建

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

表2 貨物供應(yīng)點(diǎn)與需求點(diǎn)的距離

表3 供應(yīng)點(diǎn)到需求點(diǎn)的可達(dá)矩陣

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

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

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

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

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

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

5 模型求解

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

研究0-1整數(shù)規(guī)劃算法的實(shí)現(xiàn)使用了LINGO軟件。LINGO軟件是常見求解線性規(guī)劃問題的軟件，下面是使用LINGO軟件實(shí)現(xiàn)此算法的主要程序代碼，運(yùn)行結(jié)果如表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 貨物供應(yīng)點(diǎn)集合

表5 Lingo運(yùn)行結(jié)果

變量取值成本X111X211X311X401X501X611X701X801X901X1011X1101

變量取值成本X1201X1311X1401X1501X1601X1711X1811X1901X2001X2101

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

圖2 最終網(wǎng)絡(luò)節(jié)點(diǎn)分布圖

6 結(jié)論

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