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

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

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

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)

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

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

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

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

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)

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

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

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

1　模型構(gòu)建

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

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

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

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

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

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

2.1粒子編碼

2.2混沌變異操作

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

2.3算法步驟

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

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

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

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

步驟 6：如果 globalBest[n]-globalBest[n-1]≤thre，實(shí)驗(yàn)結(jié)束；反之，繼續(xù)進(jìn)化候選站點(diǎn)。

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

步驟 9：計(jì)算結(jié)束。

3　實(shí)例分析

3.1算例描述

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

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

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

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

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

3.2結(jié)果分析

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

表4　選址結(jié)果

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

4　結(jié)束語

通過研究物流網(wǎng)點(diǎn)選址的問題，將一定區(qū)域內(nèi)分散的客戶抽象為具體的發(fā)生點(diǎn)，研究 1 種備選網(wǎng)點(diǎn)已知，但網(wǎng)點(diǎn)選擇數(shù)目不確定的 P-中值選址模型，在算法的求解中，根據(jù)改進(jìn)后 P-中值模型的特點(diǎn)，設(shè)計(jì)新型的粒子編碼方式和混沌變異算子，解決粒子容易陷入局部收斂的問題，采用 CUDA 并行編程模型，提高計(jì)算速度，可以應(yīng)用于計(jì)算物流網(wǎng)點(diǎn)選址的問題，該研究對(duì)目前物流網(wǎng)點(diǎn)的選址有一定的實(shí)際意義和參考價(jià)值。但是，還應(yīng)結(jié)合客戶時(shí)效性問題進(jìn)行研究，如果加入客戶的時(shí)間滿意度函數(shù)，模型將更切合實(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]. 鐵道運(yùn)輸與經(jīng)濟(jì)，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] 王春燕，張 華. 遺傳算法在配送中心選址中的應(yīng)用[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)工程理論與實(shí)踐，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] 姜 山. 基于模擬退火算法的應(yīng)急系統(tǒng)選址優(yōu)化[J]. 物流技術(shù)，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ī)場(chǎng)跑道最大容量評(píng)估模型的研究[J]. 四川大學(xué)學(xué)報(bào)：自然科學(xué)版，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]//黑龍江省計(jì)算機(jī)學(xué)會(huì). 黑龍江省計(jì)算機(jī)學(xué)會(huì) 2007 年學(xué)術(shù)交流年會(huì)論文集. 哈爾濱：哈爾濱工程大學(xué)，2007：332.

責(zé)任編輯：吳文娟

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ā)計(jì)劃課題(2014X009-J)