基于改進 PSO 算法的物流網(wǎng)點選址研究

邵玉華，賈玉衛(wèi)，陳帝霖

SHAO Yu-hua1，JIA Yu-wei2，CHEN Di-lin2

（1.昆明鐵路局 貨運處，云南 昆明 650000；2.西南交通大學 交通運輸與物流學院，四川 成都

610031）

(1.Freight Transport Department， Kunming Railway Administration， Kunming 650000， Yunnan， China； 2.School of Transportation and Logistics， Southwest Jiaotong University， Chengdu 610031， Sichuan， China)

基于改進 PSO 算法的物流網(wǎng)點選址研究

邵玉華1，賈玉衛(wèi)2，陳帝霖2

SHAO Yu-hua1，JIA Yu-wei2，CHEN Di-lin2

（1.昆明鐵路局 貨運處，云南 昆明 650000；2.西南交通大學 交通運輸與物流學院，四川 成都

610031）

(1.Freight Transport Department， Kunming Railway Administration， Kunming 650000， Yunnan， China； 2.School of Transportation and Logistics， Southwest Jiaotong University， Chengdu 610031， Sichuan， China)

在闡述目前設施選址模型和快遞網(wǎng)點布局研究的基礎上，針對物流網(wǎng)點整體偏少并且布局不合理的問題，以建立物流網(wǎng)點所需滿足時效性及經(jīng)濟成本最小化要求為目標構建模型，采用改進后 P-中值選址模型對物流網(wǎng)點在某區(qū)域的選址問題進行研究，在標準粒子群算法的基礎上采用 CUDA 并行編程模型求解以提高計算速度，最后通過某區(qū)域物流網(wǎng)點的選址實例驗證算法的可行性。

物流網(wǎng)點；P-中值模型；粒子群算法；CUDA 并行編程模型

物流網(wǎng)點選址問題屬于設施選址問題之一，可以通過借鑒設施選址方法來研究物流網(wǎng)點選址問題。目前，國內(nèi)外學者對設施選址模型和快遞網(wǎng)點布局進行了諸多研究，Hakimi S L[1]用 P-中值模型來研究如何使需求點的需求量與服務站的距離乘積之和最?。籆arbone R[2]對 P-中值問題進行改進，研究需求量服從多變量正態(tài)分布且?guī)C會約束的情形，建立非線性模型來解決不確定下公共設施網(wǎng)絡的選址問題；楊茂盛等[3]在用重心法得到備選地點的基礎上，引用離散模型解決配送中心的最佳地點問題。對于算法的研究，學者最初采用線性規(guī)劃、非線性規(guī)劃和網(wǎng)絡規(guī)劃等較簡單的算法，隨著模型的復雜化，算法方面也開始采用遺傳算法[4]、蟻群優(yōu)化[5]、模擬退火[6]等智能算法。上述研究大部分假設候選地點個數(shù)為已知，而實際在選址初期不可能準確確定建立個數(shù)，必須通過不斷測算驗證，推算出建立設施的個數(shù)?；谏鲜鲅芯看嬖诘膯栴}，考慮不明確規(guī)定選址個數(shù)，而僅將其作為上層目標，建立 P-中值選址模型，下層目標在上層目標的基礎上，求得總運輸費用 (包括運輸費用、網(wǎng)點建設費用和維護費用等) 最低。

1　模型構建

目前物流網(wǎng)點總體分布偏少并且客戶分布分散不利于研究，首先對客戶進行聚類分析，將一定區(qū)域內(nèi)分散的客戶抽象為 1 個具體的發(fā)生點。假設發(fā)生點已知，物流網(wǎng)點根據(jù)發(fā)生的分布建立一定數(shù)量的候選網(wǎng)點，物流網(wǎng)點選址的目的是在配送成本最小的情況下，盡可能少地選擇物流網(wǎng)點。因此，物流網(wǎng)點選址問題可以進行以下描述：給定發(fā)生點集合和候選網(wǎng)點集合，已知發(fā)生點的數(shù)目，運量及發(fā)生點與候選網(wǎng)點之間的距離，在總配送成本最小的方案下，確定合理的物流網(wǎng)點數(shù)目。

假設有 m 個發(fā)生點，n 個備選物流網(wǎng)點，需要從 n 個備選物流網(wǎng)點中選擇 P 個網(wǎng)點來滿足該區(qū)域所有發(fā)生點的需求，P 的數(shù)目不確定；物流網(wǎng)點的修建有建造費用；每個發(fā)生點只能由 1 個物流網(wǎng)點為其服務；發(fā)生點數(shù)目及每個發(fā)生點的運量固定，所有備選物流網(wǎng)點的服務能力已知；每個備選物流網(wǎng)點的最大吞吐量不超過其最大服務能力。根據(jù)分析，問題中包含 2 個求解目標，網(wǎng)點數(shù)目和網(wǎng)點的選址均為未知，并且選址結果基于網(wǎng)點數(shù)目，針對該情況建立雙層模型來分別表示 2 個求解目標，即總的網(wǎng)點數(shù)目最小和網(wǎng)點選址目標總配送成本最低，其中后者的求解建立在前者解的基礎之上。具體模型計算公式為

式中：L 為基本配送距離；wi為發(fā)生點 i 的貨運量；δj為備選網(wǎng)點的固定成本，包括租金、貨運管理人員工資；sj為備選網(wǎng)點 j 的最大服務能力；cij為發(fā)生點 i 與備選網(wǎng)點 j 間在基本里程內(nèi)的運輸費用；c'ij為超出基本費用的費率；dij為發(fā)生點 i 與備選網(wǎng)點 j 之間的距離；P 為擬建立的網(wǎng)點個數(shù)；λ，μ為參數(shù)變量；

⑶ 式表示備選網(wǎng)點的最大吞吐量不能超過該網(wǎng)點的最大服務能力；⑷ 式表示 1 個發(fā)生點只能有1 個物流網(wǎng)點提供服務；⑸ 式表示擬建立物流網(wǎng)點至少為 1 個；⑹ 式表示保證發(fā)送點必須由選中的物流網(wǎng)點提供服務。

2　試驗環(huán)境及求解算法

粒子群優(yōu)化算法是 Kennedy 和 Eberhart 受到真實世界中鳥群尋找食物飛行行為啟發(fā)，于 1995 年提出的智能優(yōu)化算法[7]。由于該算法具有收斂速度快、尋優(yōu)能力強、參數(shù)設置簡單等優(yōu)點，目前已經(jīng)成為選址問題求解的主流算法。在實際情況中，當物流網(wǎng)點較多時，粒子本身信息和粒子極值信息常占有較大優(yōu)勢，致使算法容易陷入局部最優(yōu)解。針對該問題設計新型的粒子編碼方式和混沌變異算子，以克服粒子陷入局部最優(yōu)解的問題，同時采用 CUDA 并行編程模型分離出算法的局部性和并行性，提高計算速度。

2.1粒子編碼

2.2混沌變異操作

混沌狀態(tài)在自然現(xiàn)象和社會現(xiàn)象中廣泛存在，由于其具有隨機性、遍歷性和規(guī)律性等性質(zhì)，使混沌運動能夠在一定范圍內(nèi)按照其自身“規(guī)律”不重復遍歷所有狀態(tài)，這種遍歷性特點可以作為搜索過程中避免陷入局部極值的優(yōu)化機制，因而構造混沌變異算子如下[8]。

2.3算法步驟

步驟 1：對整個算法流程進行分析，根據(jù)算法的特性采用 CUDA 并行編程模型，分離出算法的局部性和并行性。

步驟 2：設定粒子群規(guī)模 N，閥值 thre = 0.20，初始化粒子群中每個粒子的位置為第 n 個備選網(wǎng)點被選中的概率，可以通過居民調(diào)查法或?qū)＜掖蚍肢@取。

步驟 4：計算每個需求點到所有備選網(wǎng)點的距離，選擇其中最小值組成距離矩陣 Bm×n，將解向量與矩陣 Bm×n代入到 ⑵ 式中，求得的函數(shù)值即為粒子適應值。

步驟 5：如果目前的適應度值小于之前的 local-Best1，localBest2，…，localBestn 適應度值，則用目前的適應度值代替 localBest1，localBest2，…，localBestn 適應度值，并得到新的個體最優(yōu)網(wǎng)點，新的最優(yōu)網(wǎng)點進行全局交流得到新的 globalBest 適應度值，即得到目前最優(yōu)網(wǎng)點。

步驟 6：如果 globalBest[n]-globalBest[n-1]≤thre，實驗結束；反之，繼續(xù)進化候選站點。

步驟 8：對粒子進行自適應混沌操作，并且轉(zhuǎn)入步驟 5。

步驟 9：計算結束。

3　實例分析

3.1算例描述

假定某區(qū)域需要新建網(wǎng)點來滿足該區(qū)域的需求，備選網(wǎng)點集為 N1—N5，發(fā)生點為 M1—M10，該區(qū)域備選網(wǎng)點的基本作業(yè)里程為 10 km，在基本里程內(nèi)的單位運輸費率為 20 元/t，超出基本里程的運輸費率為 0.5 元/t。備選網(wǎng)點位置及服務能力、發(fā)生點的位置及發(fā)生量、備選網(wǎng)點最大服務能力及固定成本分別如表1—表3 所示。各備選網(wǎng)點及發(fā)生點位置如圖1 所示。

表1　備選網(wǎng)點位置及服務能力

表2　發(fā)生點位置及發(fā)生量

表3　備選網(wǎng)點最大服務能力及固定成本

圖1　備選網(wǎng)點及發(fā)生點位置示意圖

3.2結果分析

算法的參數(shù)設置如下。粒子群的規(guī)模為10，學習參數(shù) w，權重 r1，r2均為 1；實驗結束采用閥值設定 thre = 0.20，前后 Fitness 差值小于該閥值時實驗結束。改進 PSO 計算的選址結果如表4 所示。

表4　選址結果

由表4 可知，當發(fā)生點 M1、M5、M6、M7、M10選擇網(wǎng)點 N1，發(fā)生點 M2、M3、M4、M8、M9選擇網(wǎng)點 N5時，總運輸費用最小為 320.4 萬元。此時，發(fā)生點 M1、M5、M6、M7、M10的需求總和為18 t，在網(wǎng)點 N1的服務能力范圍內(nèi)；發(fā)生點 M2、M3、M4、M8、M9的需求總和為 17 t，在網(wǎng)點 N5的服務能力范圍內(nèi)。結果表明，該模型有效可行。

4　結束語

通過研究物流網(wǎng)點選址的問題，將一定區(qū)域內(nèi)分散的客戶抽象為具體的發(fā)生點，研究 1 種備選網(wǎng)點已知，但網(wǎng)點選擇數(shù)目不確定的 P-中值選址模型，在算法的求解中，根據(jù)改進后 P-中值模型的特點，設計新型的粒子編碼方式和混沌變異算子，解決粒子容易陷入局部收斂的問題，采用 CUDA 并行編程模型，提高計算速度，可以應用于計算物流網(wǎng)點選址的問題，該研究對目前物流網(wǎng)點的選址有一定的實際意義和參考價值。但是，還應結合客戶時效性問題進行研究，如果加入客戶的時間滿意度函數(shù)，模型將更切合實際。

[1] Hakimi S L. Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph[J]. Operations Research，1964，12(3)：450-459.

[2] Carbone R. Public Facilities Location under Stochastic Demand[J]. Infor，1974，12(3)：261-270.

[3] 楊茂盛，姜 華. 基于重心法與離散模型的配送中心選址研究[J]. 鐵道運輸與經(jīng)濟，2007，29(7)：68-70. YANG Mao-sheng，JIANG Hua. Research on Location Selection of Distribution Center based on Gravity Method and Discrete Model[J]. Railway Transport and Economy，2007，29(7)：68-70.

[4] 王春燕，張 華. 遺傳算法在配送中心選址中的應用[J]. 物流科技，2007(4)：111-113. WANG Chun-yan，ZHANG Hua. Application of Genetic Algorithm to Location of Distribution Center[J]. Logistics Sci-Tech，2007(4)：111-113.

[5] 秦 固. 基于蟻群優(yōu)化的多物流配送中心選址算法[J]. 系統(tǒng)工程理論與實踐，2006(4)：120-124. QIN Gu. Logistics Distribution Center Allocation based on Ant Colony Optimization[J]. Systems Engineering-Theory & Price，2006(4)：120-124.

[6] 姜 山. 基于模擬退火算法的應急系統(tǒng)選址優(yōu)化[J]. 物流技術，2011(9)：142-143. JIANG Shan. Location Optimization for Emergency Response System based on Simulated Annealing Algorithm[J]. Logistics Techlonogy，2011(9)：142-143.

[7] 彭莉娟，吳 鹍，余 靜. 機場跑道最大容量評估模型的研究[J]. 四川大學學報：自然科學版，2006，43(5)：1018-1022. PENG Li-juan，WU Kun，YU Jing. The Design and Research of Airport Maximal Capacity Estimation Model[J]. Journal of Sichuan University：Natural Science Edition，2006，43(5)：1018-1022.

[8] 林玉娥，顧國昌. 一種基于混沌變異的粒子群算法[C]//黑龍江省計算機學會. 黑龍江省計算機學會 2007 年學術交流年會論文集. 哈爾濱：哈爾濱工程大學，2007：332.

責任編輯：吳文娟

Study on Location of Logistic Network based on Improved PSO

Based on expounding the current study on facility location model and distribution of express delivery network, targeting with the problems existing in logistic network such as less networks on the whole and unreasonable distribution, the modeling is made by taking the minimized timeliness and economic cost which logistic network construction need satisfying as the objects, then the location of logistic network in certain zone is studied by using improved P-median location model, and CUDA parallel programming is applied to make solution based on particle swarm optimization (PSO), in the end, the feasibility of PSO is validated through actual location example of a logistic network in certain zone.

Logistic Network; P-median Model; PSO; CUDA Parallel Programming

1003-1421(2015)12-0022-04

F259.22

A

10.16668/j.cnki.issn.1003-1421.2015.12.05

2015-11-05

中國鐵路總公司科技研究開發(fā)計劃課題(2014X009-J)