基于貪心算法的城市地下物流系統網絡節(jié)點選址

方龍祥 于雪雨

（安徽師范大學 數學與統計學院，安徽 蕪湖 241002）

0 引言

當今社會，貨物運輸占公路交通的比例較大，極大的增加了交通壓力。僅僅擴充地面路網等措施面臨解決不了本質問題，亟需創(chuàng)新型的解決思路。“城市地下物流”雖然沒有大范圍普及,但是已有部分學者已經分析了城市地下物流系統的各方面優(yōu)勢[1-5]。一方面，地下物流系統項目多使用專門的貨物運輸線路，可以避免外界的干擾。同時，貨物在地下運輸噪音較小，對居民干擾較低，居民生活品質可以得到一定的提升。另一方面，地下物流系統在提升城市物流效率方面的作用也很顯著，將城市大型零售企業(yè)的貨物配送交給城市內部的地下物流系統來完成，這樣可以實現網絡相互連接。顯然，構建城市內部的地下物流系統對于解決城市交通擁堵、環(huán)境惡化等問題十分有必要。近些年來我國的物流行業(yè)伴隨著電子商務的興起得到了迅猛發(fā)展，但是市場倒逼的發(fā)展缺少規(guī)劃，物流行業(yè)的矛盾問題依然較多。競爭無序、基礎設施落后、物流網絡混亂、經驗管理粗放等現象明顯。像荷蘭、美國、日本等世界上一些較為發(fā)達的國家已經對城市地下物流系統有了較為深入的研究和實踐，對城市地下物流系統的數字化搭建、網絡構架、工程技術等板塊，都有了一定的研究成果[2]。這些研究在理論層面論證了城市地下物流系統具有運行速度快、準確率高的特點。由此，基于改善和緩解城市問題，實現城市可持續(xù)發(fā)展基礎上，以合肥市二環(huán)及周邊區(qū)域的數據為例，通過構建集合覆蓋模型并采用貪心算法研究了城市地下物流系統網絡節(jié)點的選擇。

1 問題的提出

網絡節(jié)點是整個地下物流系統網絡的核心，節(jié)點的選擇最終將會影響到整個物流系統的效率，所以在確定節(jié)點時要充分考慮各種因素，不僅要與商品的流向一致，而且也要考慮建立的網絡節(jié)點與現有地面物流節(jié)點的競爭情況。地下物流系統網絡節(jié)點選擇應遵循：（1）盡可能的將節(jié)點選在靠近用戶的地區(qū)；（2）物流節(jié)點不能選在地面建筑物下方，以免破壞現有建筑物的基礎；（3）地下物流節(jié)點的最小深度要有明確的規(guī)定；（4）工業(yè)用地、商業(yè)用地的邊緣可以選為物流節(jié)點，且應該盡量靠近工業(yè)區(qū)或商業(yè)區(qū)；（5）可以在農業(yè)區(qū)或者未開發(fā)的區(qū)域選擇網絡節(jié)點。因此在規(guī)劃網絡節(jié)點的時候要具有前瞻性，要與城市的發(fā)展規(guī)劃相結合。網絡路線要連接城市的港口、碼頭、辦公區(qū)域、大型生活居民區(qū)、商圈等平時貨流量較大的區(qū)域。另外還要考慮城市目前的輕軌建設及地面物流中心、物流基地的規(guī)劃情況等。

本研究是已知一組貨物需求點與貨物供應點，網絡節(jié)點是從貨物供應點中選擇，要求選中的網絡節(jié)點數最少且能夠輻射所有的需求點，以節(jié)省項目前期的建設成本，這是典型的集合覆蓋問題。集合覆蓋模型指的是：在已知一組需求點和供應點的情況下，建立目標函數并設定約束條件，用最少數量的供應點為這些需求點提供服務[3]。

2 研究設計

2.1 模型構建

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

2.2 模型求解

集合覆蓋模型是一種典型的組合優(yōu)化模型，它要求用最少的網絡節(jié)點將所有需求點實現全覆蓋。遺憾的是集合覆蓋問題在算法復雜性上屬于非確定性多項式難題（NP-hard），即它不存在多項式時間復雜度內的精確算法[5]。當問題的規(guī)模較大時求解這類問題大多采用近似算法如0-1算法、貪心算法等。

貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，而是在某種意義上的局部最優(yōu)解。其基本思路是從問題的某一個初始解出發(fā)一步一步地進行，根據某個優(yōu)化測度，每一步都要確保能獲得局部最優(yōu)解。每一步只考慮一個數據，選取應該滿足局部優(yōu)化的條件。若下一個數據和部分最優(yōu)解連在一起不再是可行解時，就不把該數據添加到部分解中，直到把所有數據枚舉完，或者不能再添加算法停止。我們?yōu)槟Ｐ驮O計如下貪心算法[6]：

上述算法可以描述為：從給出的貨物供應點中選擇一個點，使它覆蓋最多的需求點，即便這些需求點已經被一些供應點覆蓋也無妨。重復第一步，直到覆蓋了所有的需求點[6]。可以看出貪心算法的求解過程是一種從局部最優(yōu)解到全局最優(yōu)解的逼近過程。

2.3 數據來源

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

圖1 貨物供應點與需求點坐標

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

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

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

由以往研究可知，地下物流系統網絡節(jié)點的服務半徑為3 km～5 km，這里假定節(jié)點的服務范圍為3 km，結合表2（貨物供應點到需求點的距離）得到各貨物供應點到需求點的可達矩陣如表3：

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

令可達矩陣為A=aij，其中aij=1或aij=0，表示第j列供應點覆蓋了第i行需求點或者第j列供應點沒有覆蓋第i行需求點。

2.4 實證分析

根據上面的各貨物供應點到需求點的可達矩陣，找到所有候選的貨物供應點可以提供服務的所有需求點的集合，它們到達貨物供應點的距離均小于等于3 km。如表4所示：

表4 需求點集合

從上面給出的貨物供應點中選擇一個點，使它覆蓋最多的需求點，即便這些需求點已經被一些供應點覆蓋也無妨。重復第一步，直到覆蓋了所有的需求點。這是一種從局部最優(yōu)解到全局最優(yōu)解的逼近過程。貪心算法的實現我們這里借助python2.7，求解程序及結果截圖如下：

圖2 貪心算法運行結果圖

從上面的運行結果可知貪心算法最終得到的結果是從21個供應節(jié)點中選擇8個供應節(jié)點，這8 個供應節(jié)點分別是 S1，S2，S3，S6，S9，S10，S13，S14，確定的網絡節(jié)點如圖3（注：小紅旗代表選中的網絡節(jié)點）。

圖3 貪心算法確定的網絡節(jié)點分布圖

3 研究結論

根據已有研究[7]，基于0-1整數規(guī)劃算法得到最少需要 S1，S2，S3，S6，S10，S13，S17，S18 這 8 個網絡節(jié)點才能全覆蓋所有貨物需求點。對比上述兩種算法的求解結果可知，貪心算法與0-1整數規(guī)劃算法都選擇了8個網絡節(jié)點。兩種算法均選擇的網絡節(jié)點是 S1，S2，S3，S5，S10，S13， 選擇的網絡節(jié)點僅在S18與S9，S17與S14上存在區(qū)別。在選擇網絡節(jié)點時，要將合肥市目前物流企業(yè)的分布情況考慮進來：合肥市的物流基地及物流園大部分分布在離兩環(huán)較遠的西南方向，一小部分分布在合肥市的東北方向及其他各處。大型的物流園及物流基地離合肥市中心較遠，且大多數物流園、物流中心、物流基地離合肥市中心的距離相比于備選節(jié)點之間的距離要遠的多。為了節(jié)省后期的運輸成本，在選擇網絡節(jié)點時要盡可能的靠近上述兩個方向。所以貪心算法在西南方向選擇的網絡節(jié)點S9比0-1整數規(guī)劃算法選擇的節(jié)點S18合適。同時，也不能忽略合肥市一環(huán)最為繁華、人流量最大的區(qū)域是淮海路步行街。這里在相同情況下會比其他地方的人流量、貨流量大，在此建設網絡節(jié)點會大大降低后期的貨物周轉成本。所以，貪心算法在此模型中選擇的網絡節(jié)點S14較0-1整數線性規(guī)劃算法選取的節(jié)點S17更可取。綜上，本文選擇貪心算法確定的貨物供應點作為合肥市二環(huán)及周邊地下物流系統網絡節(jié)點更合理，更符合實際。