PSO算法在物流配送車(chē)輛路徑優(yōu)化模型中的應(yīng)用

青海大學(xué)管理科學(xué)與工程系 孫少龍

青海大學(xué)工商管理系 吳小濤

青海大學(xué)財(cái)經(jīng)學(xué)院 張珂珂

青海大學(xué)管理科學(xué)與工程系 馮 凱 席小斌

1.引言

隨著市場(chǎng)經(jīng)濟(jì)的發(fā)展和物流技術(shù)專(zhuān)業(yè)化水平的提高，物流配送業(yè)得到了迅猛發(fā)展。物流配送是指按用戶(hù)的訂貨要求，在配送中心進(jìn)行分貨、配貨，并將配好的貨物及時(shí)送交收貨人。在物流配送業(yè)務(wù)中，存在許多優(yōu)化決策問(wèn)題，通過(guò)制定合理的配送路徑，快速而經(jīng)濟(jì)地將貨物送達(dá)用戶(hù)手中，配送路徑的選擇是否合理，對(duì)加快配送速度、提高服務(wù)質(zhì)量、降低配送成本及增加經(jīng)濟(jì)效益都有較大影響。

2.物流配送車(chē)輛路徑優(yōu)化問(wèn)題描述

物流配送路徑優(yōu)化問(wèn)題可以描述為：從配送中心(或稱(chēng)物流據(jù)點(diǎn))用多輛汽車(chē)向多個(gè)需求點(diǎn)(或稱(chēng)顧客)送貨，每個(gè)需求點(diǎn)的位置和需求量一定，每輛汽車(chē)的載重量一定，要求合理安排汽車(chē)路線，使總運(yùn)距最短，并滿(mǎn)足以下條件：

(1)每條配送路徑上各需求點(diǎn)的需求量之和不超過(guò)汽車(chē)載重量；

(2)每條配送路徑的長(zhǎng)度不超過(guò)汽車(chē)一次配送的最大行駛距離；

(3)每個(gè)需求點(diǎn)的需求必須滿(mǎn)足，且只能由一輛汽車(chē)送貨。本文建立的車(chē)輛路徑問(wèn)題的數(shù)學(xué)模型考慮了上述物流配路徑優(yōu)化問(wèn)題的約束條件和優(yōu)化目標(biāo)。

設(shè)配送中心有K輛汽車(chē)，每輛汽車(chē)的載重量為Qk(k=1，2，…，K)，其一次配送的最大行駛距離為Dk，需要向L個(gè)需求點(diǎn)送貨，每個(gè)需求點(diǎn)的需求量為qi(i=1，2，…，L)，需求點(diǎn)i到j(luò)的運(yùn)距為dij，配送中心到各需求點(diǎn)的距離為d0j(i、j=1，2，…，L)，再設(shè)nk為第k輛汽車(chē)配送的需求點(diǎn)數(shù)(nk=0表示未使用第k輛汽車(chē))，用集合Rk表示第k條路徑，其中的元素 表示需求點(diǎn) 在路徑k中的順序?yàn)閕（不包括配送中心），令rk0=0表示配送中心，則可建立如下物流配送路徑優(yōu)化問(wèn)題的數(shù)學(xué)模型：

上述模型中：(1-1)式為目標(biāo)函數(shù)，要求配送線路最短；

(1-2)式保證每條路徑上各需求點(diǎn)的需求量之和不超過(guò)汽車(chē)的載重量；

(1-3)式保證每條配送路徑的長(zhǎng)度不超過(guò)汽車(chē)一次配送的最大行駛距離；

(1-4)式表明每條路徑上的需求點(diǎn)數(shù)不超過(guò)總需求點(diǎn)數(shù)；

(1-5)式表明每個(gè)需求點(diǎn)都得到配送服務(wù)；

(1-6)式表示每條路徑的需求點(diǎn)的組成；

(1-7)式限制每個(gè)需求點(diǎn)僅能由一輛汽車(chē)送貨；

(1-8)式表示當(dāng)?shù)趉輛汽車(chē)服務(wù)的客戶(hù)數(shù)≥1時(shí)，說(shuō)明該輛汽車(chē)參加了配送，則取sign(nk)=1，當(dāng)?shù)趉輛汽車(chē)服務(wù)的客戶(hù)數(shù)＜1時(shí)，表示未使用該輛汽車(chē)，因此取sign(nk)=0。

3.粒子群算法描述

PSO算法將群體中的每個(gè)個(gè)體視為多維搜索空間中一個(gè)沒(méi)有質(zhì)量和體積的粒子(點(diǎn))，這些粒子在搜索空間中以一定的速度飛行，并根據(jù)粒子本身的飛行經(jīng)驗(yàn)以及同伴的飛行經(jīng)驗(yàn)對(duì)自己的飛行速度進(jìn)行動(dòng)態(tài)調(diào)整，PSO算法就是這樣依據(jù)每個(gè)粒子對(duì)環(huán)境的適應(yīng)度將個(gè)體逐步移到較優(yōu)的區(qū)域，并最終搜索、尋找到問(wèn)題的最優(yōu)解。在PSO算法中，用粒子的位置表示待優(yōu)化問(wèn)題的解，每個(gè)粒子性能的優(yōu)劣程度取決于待優(yōu)化問(wèn)題目標(biāo)函數(shù)確定的適應(yīng)值，每個(gè)粒子由一個(gè)速度矢量決定其飛行方向和速率大小。設(shè)在一個(gè)d維的目標(biāo)搜索空間中，有m個(gè)粒子組成一個(gè)群體，其中，在第t次迭代時(shí)粒子i的位置表示為：Xi(t)=(xi1(t)，xi2(t)，xid(t))，相應(yīng)的飛行速度表示為：Vi(t)=(vi2(t)，vi2(t)，vid(t))。開(kāi)始執(zhí)行PSO算法時(shí)，首先隨機(jī)初始化m個(gè)粒子的位置和速度，然后通過(guò)迭代尋找最優(yōu)解，在每一次迭代中，粒子通過(guò)跟蹤兩個(gè)極值來(lái)更新自己的速度和位置：一個(gè)極值是粒子本身迄今搜索到的最優(yōu)解，稱(chēng)為個(gè)體極值，表示為Pi(t)=(pi1(t)，pi2(t)，pid(t))；另一個(gè)極值是整個(gè)粒子群到目前為止找到的最優(yōu)解，稱(chēng)為全局極值，表示Pg(t)=(pg1(t)，pg2(t)，pgd(t))。在第t+1次迭代計(jì)算時(shí)，粒子i根據(jù)下列規(guī)則來(lái)更新自己的速度和位置：

表1 各需求點(diǎn)周需求量（單位：噸）

表2 需求點(diǎn)與配送中心及各需求點(diǎn)之間最短距離（單位：千米）

表3 最優(yōu)值的迭代次數(shù)及所得到的最優(yōu)解

Vib(t+l)=ωνib(t)+randl(pib(t)-xib(t))+rand2(pgk(t)-xik(t)) (2-1)

Xik(t+l)=xik(t)+νik(t+l) (2-2)

式中ω為慣性權(quán)重，ω取大值可使算法具有較強(qiáng)的全局搜索能力，ω取小值則算法傾向于局部搜索；rand1(pib(t)-xib(t))表示粒子對(duì)自身經(jīng)驗(yàn)的依賴(lài)情rand2(pgk(t)-xik(t))表示粒子對(duì)社群信息的依賴(lài)情況。rand1，rand2表示0到1間的隨機(jī)數(shù)。

4.舉例具體演算分析

例如，設(shè)VRP問(wèn)題中發(fā)貨點(diǎn)任務(wù)數(shù)為7，車(chē)輛數(shù)為3，若某粒子的位置向量X為：

發(fā)貨點(diǎn)任務(wù)號(hào)：1 2 3 4 5 6 7 8 9 X r：6 1 2 9 5 3 7 8 4 X v：6 1 2 0 5 3 7 0 4

利用Matlab求解該粒子對(duì)應(yīng)解路徑為：

車(chē)1：0→6→1→2→0

車(chē)2：0→5→3→7→0

車(chē)3：0→4→0

該表示方法的最大優(yōu)點(diǎn)是使每個(gè)發(fā)貨點(diǎn)都得到車(chē)輛的配送服務(wù)，并限制每個(gè)發(fā)貨點(diǎn)的需求僅能由某一車(chē)輛來(lái)完成，使解的可行化過(guò)程計(jì)算大大減少。雖然該表示方法的維數(shù)較高，但由于PSO算法在多維尋優(yōu)問(wèn)題有著非常好的特性，維數(shù)的增加并未增加計(jì)算的復(fù)雜性。

5.華圣果業(yè)公司配送線路的分析與優(yōu)化

5.1 華圣果業(yè)原配送線路基本數(shù)據(jù)分析

華圣果業(yè)公司主要給超市和農(nóng)產(chǎn)品批發(fā)市場(chǎng)供應(yīng)蘋(píng)果?？蛻?hù)可分為需求量穩(wěn)定的大客戶(hù)和需求量隨機(jī)的小客戶(hù)。小客戶(hù)的需求具有時(shí)間和地點(diǎn)上的不確定性，需求量小的特點(diǎn)，一般采用共同配送運(yùn)輸服務(wù)或客戶(hù)自配卡車(chē)。大客戶(hù)地點(diǎn)確定，主要位于西安市的超市或是農(nóng)產(chǎn)品批發(fā)市場(chǎng)，但是經(jīng)過(guò)實(shí)地的考察發(fā)現(xiàn)華圣果業(yè)公司現(xiàn)在主要只給西安市的各大超市供應(yīng)蘋(píng)果。大致共有20多個(gè)點(diǎn)，如人人樂(lè)、沃爾瑪、華潤(rùn)萬(wàn)家、愛(ài)樂(lè)購(gòu)超市等，公司為推廣產(chǎn)品，采用每周專(zhuān)車(chē)送貨上門(mén)服務(wù)。公司現(xiàn)擁有3輛半噸的長(zhǎng)安貨車(chē)和2輛1.5噸的東風(fēng)小貨車(chē)，若車(chē)輛使用欠缺時(shí)，可租賃車(chē)輛。

目前，華圣果業(yè)公司對(duì)大客戶(hù)配送蘋(píng)果并沒(méi)有固定的配送線路，一般配送線路由貨車(chē)司機(jī)自己來(lái)決定。更重要的問(wèn)題是公司對(duì)于每個(gè)需求點(diǎn)會(huì)專(zhuān)門(mén)派一輛車(chē)去配送，不考慮是否滿(mǎn)載率低的問(wèn)題。這樣的話就存在一些弊端：配送路線的選擇不合理，運(yùn)距過(guò)長(zhǎng)，消耗作業(yè)時(shí)間偏多，不能充分利用車(chē)輛配載容積，浪費(fèi)較多人力和物力資源，影響公司盈利。各需求點(diǎn)每星期需求蘋(píng)果的基本數(shù)據(jù)如表1所示。

各編號(hào)對(duì)應(yīng)的需求點(diǎn)名稱(chēng)如下：

1：華潤(rùn)萬(wàn)家西二環(huán)店

2：華潤(rùn)萬(wàn)家西安蓮湖店

3：華潤(rùn)萬(wàn)家星火路店

4：人人樂(lè)超市北關(guān)購(gòu)物廣場(chǎng)

5：家樂(lè)福西安北大街店

6：人人樂(lè)購(gòu)物廣場(chǎng)西關(guān)店

7：大潤(rùn)發(fā)大唐西安店

8：愛(ài)樂(lè)購(gòu)超市

9：西安沃爾瑪萬(wàn)達(dá)店

10：沃爾瑪購(gòu)物廣場(chǎng)西安金花南路分店11：人人樂(lè)東門(mén)店

12：沃爾瑪購(gòu)物廣場(chǎng)西安騾馬市分店13：人人樂(lè)解放路購(gòu)物廣場(chǎng)

14：華潤(rùn)萬(wàn)家金花路店

15：華潤(rùn)萬(wàn)家太華路店

16：百姓自選水果超市

17：家美家超市友誼路分店

5.2 基于PSO算法的物流配送路線優(yōu)化

為計(jì)算方便，需考慮以下幾個(gè)假設(shè)前提條件：

a、配送中心(華圣果業(yè)公司)不會(huì)出現(xiàn)缺貨的可能并且對(duì)顧客的基本配送資料(需求量、地理位置)為已知，配送中心的位置也已知；

b、不考慮配送時(shí)間限制，即客戶(hù)對(duì)貨物的需求沒(méi)有時(shí)間的規(guī)定；

c、不考慮每輛車(chē)為每個(gè)客戶(hù)的服務(wù)時(shí)間，即不考慮每個(gè)客戶(hù)的卸貨時(shí)間；

d、車(chē)輛由配送中心出發(fā)，服務(wù)被指定的需求點(diǎn)后，再返回配送中心，區(qū)域內(nèi)的需求點(diǎn)假設(shè)為固定數(shù)量且位置已知，不發(fā)生變動(dòng)；

e、配送中心擁有一定數(shù)量的單一車(chē)型的配送車(chē)輛，且每輛車(chē)的容量已知。

f、每條配送路徑上各客戶(hù)需求量之和不超過(guò)配送車(chē)輛的容量；

g、每個(gè)客戶(hù)只能由一輛配送車(chē)輛送貨；

h、每輛車(chē)配送總里程不超過(guò)其最大行駛距離；

i、各道路均順暢，不考慮交通堵塞擁擠等特殊情況。

在本題中，需要分別計(jì)算以下幾個(gè)內(nèi)容，計(jì)算需求點(diǎn)與配送中心及各需求點(diǎn)之間的距離，利用粒子群優(yōu)化算法，求出函數(shù)的全局最優(yōu)位置和最后得到的優(yōu)化極值。

(1)問(wèn)題重述

用0表示華圣果業(yè)有限公司(即配送中心)，設(shè)車(chē)輛容量皆為q=8.0，公司有4輛車(chē)完成西安市內(nèi)17家超市的配送任務(wù)，初始化群體個(gè)數(shù)n=30，慣性權(quán)重w=0.729，學(xué)習(xí)因子c1=2、c2=2，最大代數(shù) MaxDT= 50。

(2)需求點(diǎn)與配送中心及各需求點(diǎn)之間的最短距離如表2。

(3)粒子群算法實(shí)現(xiàn)過(guò)程。

a、編碼初始化

本文使用整數(shù)編碼求解車(chē)輛路徑問(wèn)題。對(duì)于17個(gè)蘋(píng)果需求點(diǎn)和4輛車(chē)來(lái)配送的問(wèn)題，用從1到20的整數(shù)排列來(lái)表示粒子的狀態(tài)X(x1，x2，…，xi)，隨機(jī)的生成初始種群，用1-20的整數(shù)是因?yàn)橛?輛車(chē)來(lái)配送我們插入3個(gè)數(shù)就可將17個(gè)需求點(diǎn)劃分成4組，然后由4輛車(chē)來(lái)分別給這4組需求點(diǎn)送貨。編程的重點(diǎn)是要在每個(gè)粒子中找出這三個(gè)數(shù)用配送中心“0”來(lái)表示。

b、適應(yīng)度計(jì)算

用PSO算法優(yōu)化客戶(hù)的排序，按照客戶(hù)的排列順序分配車(chē)輛，在每條線路的內(nèi)部，用最鄰近法優(yōu)化線路。根據(jù)式(1-1)計(jì)算粒子所代表的配送方案的目標(biāo)函數(shù)Z，粒子的適應(yīng)度定義為目標(biāo)函數(shù)Fitness=Z。

c、初始化局部最優(yōu)和全局最優(yōu)

d、循環(huán)內(nèi)位置速度更新

微粒速度和位置的更新公式：

其中，Pi為微粒的自身最佳位置，Pg為群體的最佳位置。

①位置與速度的加法。粒子的位置更新時(shí)，若在速度矢量中 vi=0，則不改變位置中的第i個(gè)序列號(hào)；若 vi≠0，則交換粒子位置中的序號(hào)vi和xi，以保證新位置的有效性。

②位置間的減法。兩個(gè)位置的相減結(jié)果是一個(gè)速度，記為 V= X2- X1。V按照以下方式來(lái)確定。逐一比較X1和X2的各個(gè)分量x1,i和x2,i，若兩者相同，責(zé)令 vi=x2,i，否則令 vi=x1,i。

③速度的數(shù)乘。速度的數(shù)乘記為V2= w× V1，其中w為0到1之間的一個(gè)常數(shù)。速度的數(shù)乘按照如下方式執(zhí)行：對(duì)于V1的每一維速度v1，i，隨機(jī)生成一個(gè)0到1之間均勻分布的隨機(jī)數(shù)rand，若rand≥c，責(zé)令v2,i= v1,i，否則令 v2,i=0。

e、循環(huán)內(nèi)適應(yīng)度計(jì)算

與初始適應(yīng)度計(jì)算方法相同，根據(jù)式(1-1)計(jì)算粒子所代表的配送方案的目標(biāo)函數(shù)Z。

f、循環(huán)內(nèi)局部最優(yōu)和全局最優(yōu)更新

粒子的適應(yīng)度計(jì)算完成后，每個(gè)粒子當(dāng)前的適應(yīng)度與自身己知的最優(yōu)適應(yīng)度比較，選出個(gè)體最優(yōu)狀態(tài)P；將種群中本次迭代的最優(yōu)粒子適應(yīng)度與種群已知的最優(yōu)適應(yīng)度比較，選擇出群體最優(yōu)狀態(tài)Pg。交換更新全局最優(yōu)和局部最優(yōu)。

(4)算法得到的最優(yōu)值的迭代次數(shù)及所得到的最優(yōu)解，預(yù)計(jì)迭代次數(shù)50，共進(jìn)行20次運(yùn)算，如表3。

從實(shí)驗(yàn)結(jié)果分析，15次達(dá)到已知最優(yōu)解，得到的最優(yōu)總路徑為：

0 →7 →6 →0 →1 →0 →2 →3 →4 →5 →0

對(duì)應(yīng)的行車(chē)路線為：

車(chē)輛一：0 →7 →6 →0

車(chē)輛二：0→1→0

車(chē)輛三：0 →2 →3 →4 →5 →0

行車(chē)總距離217.81千米

6.結(jié)束語(yǔ)

由于PSO優(yōu)化模型求解出來(lái)的結(jié)果是理想狀態(tài)下的，因此需要結(jié)合華圣果業(yè)有限公司的實(shí)際情況進(jìn)行有效地分析，才能更好地加以運(yùn)用到實(shí)際情況中來(lái)。

[1]李麗,牛奔.粒子群優(yōu)化算法[M].冶金工業(yè)出版社,2009.

[2]郎茂祥.配送車(chē)輛優(yōu)化調(diào)度模型與計(jì)算[M].電子工業(yè)出版社,2009.

[3]李寧,鄒彤,孫德寶.車(chē)輛路徑問(wèn)題的粒子群算法研究[J].系統(tǒng)工程學(xué)報(bào),2004,19(6):597-600.

[4]吳建生,秦發(fā)金.基于MATLAB的粒子群優(yōu)化算法程序設(shè)計(jì)[J].柳州師專(zhuān)學(xué)報(bào),2005,20(4):97-100.