物流配送網點選址PSO算法的研究

李穎

(陜西交通職業技術學院 經濟管理學院， 西安 710018)

0 引言

快速發展和完善的電子商務與信息技術推動了物流業的發展，物流業在日常生產生活中的重要性日益凸顯，除第三方快遞企業外，很多企業對物流體系建設的重視程度不斷提高，不斷增加在物流方面的投入，開始發展本企業的物流體系。電子商務促使快遞行業的物流系統幾乎覆蓋全國地區，從上到下涉及到多個層級。作為物流體系的基礎，物流網點具有重要作用，物流網點布局問題已經成為物流領域的研究熱點之一，為實現資源節約、最大程度降低物流成本，需對物流網點進行科學合理的布局，本文主要對物流網點選址進行了研究，基于改進PSO算法研究物流網點選址問題構建模型，將分散在一定區域內的客戶視為具體發生點，針對已知備選網點不確定網點選擇數目的情況下，在建立物流網點時采用改進后?P-中值選址模型研究選址問題，使中轉倉庫的覆蓋范圍更加合理，使物流網點的布局及數量分布更加合理，提高物流效率。

1 現狀分析

作為設施選址問題的一種，物流網點選址問題的研究過程可以設施選址方法作為借鑒，目前對對設施選址模型及快遞網點布局的研究國內外學者已經取得了一定的成果，例如，通過P-中值模型的使用完成了對需求量同服務站距離間關系的研究即二者乘積之和最小(Hakimi S L)；通過改進P-中值問題后，對帶機會約束的需求量情形(服從多變量正態分布)進行研究，公共設施網絡在不確定情況下通過非線性模型的建立實現選址問題的解決(Carbone R)；對于物流網點的備選地點通過使用重心法獲取，在此基礎上將配送中心通過離散模型的引用解決最佳地點選取問題(楊茂盛等)。算法研究最初采用較簡單的算法(包括網絡規劃、線性及非線性規劃等)，隨著模型復雜化程度的不斷提升智能算法得到了普遍應用(包括遺傳算法、模擬退火、蟻群優化等)。上述研究多以候選地點個數已知作為假設條件，但在實際工作過程中，物流網點的建立個數很難在選址初期做到準確確定，需在不斷測算進行驗證的基礎上完成建立設施數量的推算。因此本文主要對物流網點選址進行了研究，將分散在一定區域內的客戶視為具體發生點，針對已知備選網點不確定網點選擇數目的情況下，在建立物流網點時將選址個數作為上層目標，采用改進后?P-中值選址模型研究選址問題，下層目標基于上層目標完成包括運輸、建設及維護費用等在內的總運輸費用最低情況的計算最低，使物流網點的布局及數量分布更加合理[1]。

2 模型構建

目前研究物流網點問題的主要難點在于客戶分布相對分散且總體分布不足，為有效解決這一問題，本文先以客戶為研究對象完成聚類分析，建設物流網點時，將分散于某一區域內的客戶視為具體的發生點，假設條件為已知發生點，以發生點的分布為依據完成一定數量的候選網點的建立，以在最小化配送成本的情況使選擇物流網點數量盡可能少作為物流網點選址目標[2]。據此描述物流網點選址問題為：發生點的數量為已知條件，并給定相關集合(包括發生點和候選網點)，基于最小化總配送成本的方案，確定發生點、候選網點同運量間的距離，據此完成合理物流網點數量的確定。假設發生點及服務能力已知的備選物流網點分別為m個、n個，建設物流網點需花費建造費用，為使該區域全部發生點的需求均得到有效滿足，需從備選網點(最大服務能力超過其最大吞吐量)中選取數目不確定的網點p個，發生點數目及運量固定，僅能通過一個物流網點為各發生點提供服務。分析問題可知其包含求解目標兩個，網點數目及選址未知(選址結果以網點數目為依據)，因此對兩個求解目標(即最小化網點數量及選址目標總配送成本，)通過雙層模型的建立進行表示，具體模型計算如式(1)[3]。

f(x)=

min ∑i∈N ∑j∈Mwicij+c′ij(dij-L)yij+∑j∈Mδjxj

(1)

備選網點的最大吞吐量需小于其最大服務能力的表達式如式(2)。

(2)

僅能通過一個物流網點為各發生點提供服務的表達式如式(3)。

(3)

擬建立物流網點表達式如式(4)。

(4)

yij≤xj(由選中的物流網點向發送點提供服務)

3 試驗環境及求解算法

作為智能優化算法的一種，粒子群優化算法(由Kennedy、Eberhart提出)具有參數設置簡單和較快的收斂速度等優點，能夠高效的尋找到最優解，在求解選址問題中發揮重要作用。但在實際物流網點較多的情況下，具備較大優勢的粒子本身信息和極值信息易使算法陷入局部最優解，為提高計算質量和速度，本文在此基礎上對粒子編碼方式和混沌變異算子進行優化設計，對算法的局部性和并行性通過CUDA并行編程模型的使用實現分離。

3.1 編碼粒子

編碼方式根據P-中值模型特點表示為：P= [p1，p2，…，pn]，選中第n個備選網點的概率由pn表示，取值范圍在?[ 0，1]間；備選網點的個數由n(粒子長度)表示，最終的物流網點選擇p為1的備選網點，例如P= (0，1，0，0，1，1，0，0)，則最終的物流網點為第 2，5，6備選網點[5]。

3.2 混沌變異操作

廣泛存在的混沌狀態具有隨機性、遍歷性等特點，使混沌運動能夠不重復遍歷所有狀態(在一定范圍內)，在搜索過程中通過運用遍歷性特點能夠使陷入局部極值的優化得到有效避免，混沌變異算子的構造過程如下[6]。

3.3 算法步驟

4 實例分析

(1) 算例情況描述

某區域為滿足物流運輸需求需對網絡網點進行規劃，備選網點作業里程為10 km，已知備選網點集、發生點(分別由N1—N5、M1—M10表示)，運輸費率為20元/t，超出10 km的運輸費率為0.5元/t。圖1為備選網點及發生點位置，發生點位置及發生量如表1所示，備選網點位置及服務能力如表2所示，最大服務能力及固定成本如表3所示[8]。

圖1 備選網點及發生點位置示意圖

發生點橫坐標/km縱坐標/km發生量/(t/d)M120.215.35M27.411.34M311.312.33M445.38.94M527.637.63M646.736.33M737.427.64M819.332.32M97.538.54M1028.941.63

表2 位置及服務能力

(2) 結果分析

算法的參數為：粒子群規模為10，權重r1，r2均為1，閥值thre為0.2，實驗在前后Fitness差值<0.2時結束，基于改進PSO算法的選址結果如表4所示。以此種發生點同網點選址位置網點對應方式下，總運輸費用最小(320.4 萬)，此時N1的服務能力能夠有效滿足第1、5、6、7、10發生點的需求總和(18 t)，網點 N5的服務能力能夠有效滿足2、3、4、8、9的需求總和(17 t)。實驗結果證明了本文所設計的基于改進PSO算法的物流網點選址模型的可行性。

表3 最大服務能力和固定成本

表4 選址結果

5 總結

物流網點的科學合理的選址是物流企業的重要工作內容，本文主要對物流網點選址進行了研究，分析了目前快遞網點布局的現狀，在傳統設施選址模型的基礎上，基于改進PSO算法研究物流網點選址問題構建模型，將分散在一定區域內的客戶視為具體發生點，針對已知備選網點不確定網點選擇數目的情況下，在建立物流網點時采用改進后P-中值選址模型研究選址問題，使物流網點的布局及數量分布更加合理，同時滿足時效性及經濟成本方面的要求，以改進后P-中值模型的特點為依據，為使粒子易陷入局部收斂的問題得以有效解決，在算法的求解中，對粒子編碼方式和混沌變異算子進行了優化設計，通過CUDA并行編程模型的運用使算法的計算速度得以顯著提高，可有效滿足對物流網點選址的具體計算問題，通過物流網點在某區域的選址實例證明了該算法的具有較高的實際應用價值。接下來的研究方向將結合客戶時效性問題，通過客戶的時間滿意度函數等的應用進一步優化模型功能。