青海大學管理科學與工程系 孫少龍

青海大學工商管理系 吳小濤

青海大學財經(jīng)學院 張珂珂

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

1.引言

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

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

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

(1)每條配送路徑上各需求點的需求量之和不超過汽車載重量；

(2)每條配送路徑的長度不超過汽車一次配送的最大行駛距離；

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

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

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

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

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

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

(1-5)式表明每個需求點都得到配送服務；

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

(1-7)式限制每個需求點僅能由一輛汽車送貨；

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

3.粒子群算法描述

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

表1 各需求點周需求量（單位：噸）

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

表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)重，ω取大值可使算法具有較強的全局搜索能力，ω取小值則算法傾向于局部搜索；rand1(pib(t)-xib(t))表示粒子對自身經(jīng)驗的依賴情rand2(pgk(t)-xik(t))表示粒子對社群信息的依賴情況。rand1，rand2表示0到1間的隨機數(shù)。

4.舉例具體演算分析

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

發(fā)貨點任務號：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求解該粒子對應解路徑為：

車1：0→6→1→2→0

車2：0→5→3→7→0

車3：0→4→0

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

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

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

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

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

各編號對應的需求點名稱如下：

1：華潤萬家西二環(huán)店

2：華潤萬家西安蓮湖店

3：華潤萬家星火路店

4：人人樂超市北關(guān)購物廣場

5：家樂福西安北大街店

6：人人樂購物廣場西關(guān)店

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

8：愛樂購超市

9：西安沃爾瑪萬達店

10：沃爾瑪購物廣場西安金花南路分店11：人人樂東門店

12：沃爾瑪購物廣場西安騾馬市分店13：人人樂解放路購物廣場

14：華潤萬家金花路店

15：華潤萬家太華路店

16：百姓自選水果超市

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

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

為計算方便，需考慮以下幾個假設前提條件：

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

b、不考慮配送時間限制，即客戶對貨物的需求沒有時間的規(guī)定；

c、不考慮每輛車為每個客戶的服務時間，即不考慮每個客戶的卸貨時間；

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

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

f、每條配送路徑上各客戶需求量之和不超過配送車輛的容量；

g、每個客戶只能由一輛配送車輛送貨；

h、每輛車配送總里程不超過其最大行駛距離；

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

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

(1)問題重述

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

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

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

a、編碼初始化

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

b、適應度計算

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

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

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

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

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

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

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

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

e、循環(huán)內(nèi)適應度計算

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

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

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

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

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

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

對應的行車路線為：

車輛一：0 →7 →6 →0

車輛二：0→1→0

車輛三：0 →2 →3 →4 →5 →0

行車總距離217.81千米

6.結(jié)束語

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

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

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

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

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