□ 李董潔，梁革英

(廣西大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，廣西 南寧 530004)

1 引言

為解決銷售給客戶的汽車?yán)锍瘫頌榱愎锏囊?，就要求汽車生產(chǎn)企業(yè)將汽車直接運輸?shù)街付ǖ匿N售地點。由于汽車企業(yè)運輸?shù)能囕v變多、地點變多，手工分派不能滿足企業(yè)運輸?shù)男枨螅枰褂糜嬎銠C智能選擇整車運輸路徑。整車的運輸方案影響著企業(yè)的利益和顧客對企業(yè)的滿意度，如何選擇合適的運輸路徑是整車運輸?shù)暮诵膯栴}，合理的路徑安排不僅可以降低運輸成本，還可以提高顧客對企業(yè)的滿意度。因此，本文在平衡運輸成本與運輸時間的情況下建立運輸模型。

目前在整車調(diào)度運輸以及物流配送方面已有不少文獻，大多數(shù)研究中采用遺傳算法、蟻群算法、遺傳算法以及Dijkstra算法來進行求解路徑優(yōu)化問題。這些經(jīng)典算法本身存在一定的缺陷，如遺傳算法存在易出現(xiàn)局部收斂且當(dāng)問題較為復(fù)雜時需要進行大量計算；蟻群算法存在收斂速度慢及易出現(xiàn)局部最優(yōu)的問題；而粒子群法相比遺傳算法具有算法簡單，收斂速度快的優(yōu)點，但也存在著陷入局部最優(yōu)解的可能。因而，不少人在研究時都對傳統(tǒng)的算法做了改進。

如陳磊提出使用混合遺傳算法來解決物流配送問題，建立滿足客戶需求的同時使得運輸費用最少模型[1]；劉娜翠等通過使用改進的遺傳算法求解以費用最小為目的的帶時間窗的整車物流配送問題[2]；袁彬等提出了一種基于改進Dijkstra的物流網(wǎng)絡(luò)路徑優(yōu)化模型[3]；徐鵬等提出Dijkstra算法在GIS中的優(yōu)化與應(yīng)用[17]；劉臣宇等使用Dijkstra算法通過對目的點標(biāo)號的形式解決直送式配送問題[4]；姜辰凱等提出通過改進Dijkstra算法解決無碰撞路徑規(guī)劃問題[5]。1995年,美國學(xué)者Kennedy J與Eberhart R共同提出了粒子群算法[6]。有不少學(xué)者應(yīng)用粒子群算法解決路徑選擇問題，并對傳統(tǒng)算法改進：如Shi Y等在論文中基于粒子群算法引入慣性權(quán)重的概念，并且指出慣性權(quán)重取0.9-1.2是合適的[7]；Shi Y等還提出了線性遞減慣性權(quán)重LDIW(Linear Decreasing Inertia Weight)[8];毛開富等考慮調(diào)節(jié)非對稱學(xué)習(xí)因子對粒子群算法的影響，確定使用c1=2.5-0.5,c2=1.0-2.25的非對稱調(diào)節(jié)因子對粒子群算法有明顯的改進[9]。李寧等提出使用粒子群算法來解決車輛路徑問題，并且驗證粒子群算法(PSO)在應(yīng)用于VRP(vehicle routing problem,VRP)問題時有著運算速度快、魯棒性好等優(yōu)點[10]；李寧等還提出了帶時間窗車輛路徑問題的粒子群算法[11]。張丹露、黃向紅提出通過改進蟻群算法來解決VRP問題[12]。劉娜等通過改進慣性權(quán)重來改進粒子群算法從而求解質(zhì)押物配送路徑問題[13]。為提高企業(yè)的競爭力，在求解路徑規(guī)劃問題時結(jié)合實際，既要盡可能地滿足客戶的需求，又要考慮降低運輸費用減少企業(yè)開支。如，蔡鑒明、吳松城提出對整車物流運輸網(wǎng)絡(luò)進行研究時還需要考慮碳稅政策對運輸路徑選擇的影響[14]；楊樹國、李春霞通過使轎車運能最大化求出相應(yīng)的配載模式，與實際相結(jié)合，解決整車物流配送優(yōu)化問題[15]；張慶瑩在考慮了各方主體利益、貨源緊急程度以及運力資源的利用率三個因素建立了考慮貨源時間窗的整車運力資源選擇模型[16]。

2 研究思路

為解決汽車制造企業(yè)整車運輸?shù)膯栴}，根據(jù)整車運輸?shù)奶攸c將整車運輸過程分成兩段：一段是跨省的長距離運輸，即從生產(chǎn)廠家運輸?shù)戒N售商所在省的中轉(zhuǎn)倉庫；另一段是省內(nèi)的短距離配送運輸，即從中轉(zhuǎn)庫運輸?shù)戒N售商的銷售點。一般物流的運輸方式有四種：水路運輸、鐵路運輸、公路運輸以及航空運輸。因為航空運輸?shù)某杀据^高且運輸能力有限，故一般整車調(diào)度運輸不采用航空運輸。對于跨省的長距離運輸，運輸方式主要有三種方式：水路運輸、鐵路運輸和公路運輸[13]。而對于省內(nèi)城市之間的運輸，由于目前在全國各地省內(nèi)的高速路網(wǎng)已完善，時間與效率能滿足客戶對整車運輸?shù)囊螅杀驹诳煽氐姆秶鷥?nèi)，所以省內(nèi)運輸一般通過公路運輸?shù)街付ǖ匿N售網(wǎng)點。

對于長距離的跨省運輸部分：建立可以根據(jù)訂單的緊急程度來考慮運輸費用還是運輸時間作為影響路徑的絕對因素的路徑選擇模型，由于Dijkstra算法可以針對有向圖求解最短路徑且可以根據(jù)訂單緊急程度改變路徑權(quán)值，算法成熟且具有簡單、運算快和更易于找到滿意解的優(yōu)點，因此本文針對長距離的跨省運輸部分采用Dijkstra算法求解最優(yōu)路徑方案。

對于短距離的省內(nèi)運輸部分：在考慮汽車企業(yè)本身利益的情況下，為提高顧客對汽車企業(yè)的滿意度，求解的路徑結(jié)果應(yīng)滿足顧客對整車運達時間的期望，因此本文將VRP問題轉(zhuǎn)化為VRPTW(VRP with Time Windows)問題，即建立以總運輸費用最少且?guī)r間窗的整車運輸路徑模型。由于粒子群算法相比于遺傳算法更易于收斂于最優(yōu)解且粒子群算法相較于遺傳算法和蟻群算法更為簡單，故本文粒子群算法來求解該模型并通過對粒子群算法改進從而克服其易陷入局部最優(yōu)解的問題。

為實現(xiàn)上述目標(biāo)，根據(jù)運輸?shù)奶卣鹘啥温窂侥Ｐ停旱谝欢危蓚}庫運輸?shù)礁魇》菹鄳?yīng)的中轉(zhuǎn)庫(也可以稱為配送中心)；第二段，由中轉(zhuǎn)庫運送到經(jīng)銷商。如圖1整車調(diào)度運輸網(wǎng)絡(luò)所示。

圖1 整車調(diào)度運輸網(wǎng)絡(luò)

3 模型建立

3.1 全局假設(shè)

在公路運輸過程中沒有運輸意外發(fā)生，如車禍、堵車等，且在運輸中為了保證運輸時間，在派送前將選擇路況良好(通行車輛少)的時間段。

3.2 第一段模型

每條路徑根據(jù)實際情況選擇水路、公路或者鐵路。

迪杰斯特拉算法(Dijkstra)是一種用于求解帶權(quán)有向圖中的最短路徑問題的經(jīng)典算法。最短路徑是指從源點到達終點一條路徑上所有經(jīng)過邊的權(quán)值之和最小的路徑[18]。根據(jù)任務(wù)的緊急程度或費用優(yōu)先相應(yīng)地將權(quán)值定為經(jīng)過這條邊所需的時間或所花費的費用，利用Dijkstra算法求出花費時間成本最小、費用最少的最短路徑。因此根據(jù)實際應(yīng)用寫出對應(yīng)的鄰接矩陣是關(guān)鍵。

第一段的運輸路徑選擇可以按以下方式進行：

①根據(jù)訂單的緊急程度進行規(guī)則選擇，若為緊急訂單，使用以時間作為路徑權(quán)重的運輸規(guī)則；若為非緊急訂單，使用以費用作為路徑權(quán)重的運輸規(guī)則。

②確定運輸規(guī)則后，依據(jù)運輸成本(運輸時間)為權(quán)值建立相應(yīng)的運輸成本(運輸時間)的鄰接矩陣。設(shè)S為出發(fā)點也可以將S稱為源點(S中包含{s})，源點到源點的最短路徑為0。設(shè)N為終點，除源點以外的點都設(shè)為目的地包含在t(t中包含{j=1,2,…}以及終點N)中，若兩點之間存在路徑，兩點間的距離設(shè)為相應(yīng)的權(quán)值(注意方向)，若兩點間無法到達則將鄰邊距離設(shè)為∞。

③使用Dijkstra算法計算出所需費用(運輸時間)最少的路徑。

a.從t中找到與出發(fā)點s距離(此距離指代相應(yīng)路徑權(quán)值)最小的目的地t，把t加入到S中。

b.將加入S的t考慮為新的出發(fā)點，修改t中各頂點j的最短距離值(即權(quán)值)。

c.重復(fù)上述步驟二和步驟三，直至得出最終結(jié)果。

④如果是計算路徑，利用公式成本=每公里變動運輸費用×路徑長度+固定運輸費用，得到第一段的成本。

具體實現(xiàn)流程圖如圖 2所示。

圖2 具體步驟流程圖

3.3 第二段模型

3.3.1 第二段模型的假設(shè)

①運輸路徑上各經(jīng)銷商的整車需求的總重不超過運輸車輛的額定載重量。

②運輸車輛最后會回到中轉(zhuǎn)庫。

③每一個經(jīng)銷商只能由一輛運輸車進行配送。

④每一輛運輸車的行駛總里程小于其單次運輸車輛的最大里程。

⑤每次運輸?shù)能囕v為同一款車系。

3.3.2 符號說明

構(gòu)建第二段模型所需要用到的符號如表1符號說明所示。

表1 符號說明

3.3.3 第二段路徑計算

構(gòu)建第二段模型是為了解決整車從配送中心到達省內(nèi)各地經(jīng)銷商的問題，除了要考慮整車的運輸費用外，還需考慮經(jīng)銷商對接收整車的時間區(qū)間的期望。因此建立以總整車配送費用最小為目標(biāo)建立含有時間窗的運輸總成本按以下方式計算[2]：

(1)

公式(1)有以下約束條件：

(2)

(3)

(4)

(5)

Etj≤Sj≤Ltj

(6)

xijn∈{0,1}i,j=0,1,…,M;n=1,2,…,N

(7)

yin∈{0,1}i=0,1,…,M;n=1,2,…,N

(8)

根據(jù)實際運輸情況，做如下定義：

式(1)為目標(biāo)函數(shù)；式(2)表示運輸車輛上裝載的貨物量不超過運輸車的額定載貨量；式(3)表示經(jīng)銷商由特定車輛進行配送；式(4)與(5)表示運輸車輛的運輸方向是唯一的；式(6)表示通過對決策變量取整來對模型進行約束。

3.3.4 改進后的粒子群算法實現(xiàn)路徑選擇

對于第二段模型，本文選用粒子群算法(PSO)[6]進行求解。粒子群算法的基本原理是通過鳥群覓食的方法對模型進行求解，鳥的位置是隨機的，每只鳥每次只會在離食物最近的鳥的附近尋找食物，若發(fā)現(xiàn)有更加接近食物的鳥，則鳥對其所在位置進行更新，下一步將在更接近食物的鳥的周圍進行尋找食物，依次迭代最終找到食物。其核心思想可以概括為，利用個體在群體中共享的信息的特點，使整個種群在動態(tài)的問題求解空間中產(chǎn)生從無序到有序的轉(zhuǎn)變。

粒子群算法的具體公式為：

(9)

(10)

由于基本的粒子群算法存在局部收斂過快的缺點，因此需要對粒子群算法進行相應(yīng)的改進，平衡算法的全局搜索以及局部搜索能力。一個較大的慣性權(quán)值有利于全局搜索，而一個較小的權(quán)值更有利于局部搜索，因此可以考慮對慣性權(quán)重進行改進。

粒子群算法有多種改進方式，本文通過對慣性權(quán)重進行線性遞減慣性權(quán)重以及改進非對稱學(xué)習(xí)因子對模型進行改進。采用ShiY等[8]提出的線性遞減慣性權(quán)重，改進方式如下：

將權(quán)重ω改寫為：

(11)

改進非對稱學(xué)習(xí)因子[9]，則c1與c2可以寫成：

(12)

4 模型檢驗

4.1 第一段的檢驗

對實際路徑及運輸節(jié)點進行相應(yīng)簡化[18]，抽象得到如圖 3所示的運輸路徑圖。由圖 3得知，從整車生產(chǎn)基地出發(fā)由水路、鐵路和公路可以將整車運輸?shù)街修D(zhuǎn)庫，而針對水路和鐵路的運輸還需要進行公路運輸才能把整車運送到中轉(zhuǎn)庫；再由中轉(zhuǎn)庫或水路倉庫、鐵路倉庫經(jīng)公路或鐵路運輸?shù)较鄳?yīng)的倉庫(倉庫之間可以進行運輸)；最后經(jīng)公路將整車運送到配送中心。

圖3 運輸路徑情況圖

將圖 3進行簡化，將生產(chǎn)基地、倉庫、中轉(zhuǎn)庫等節(jié)點用編號指代，隱去公路、鐵路以及水路的標(biāo)識，給路徑給予相應(yīng)的權(quán)值如圖4運輸路徑簡化圖所示。

圖4 運輸路徑簡化圖

假設(shè)本次權(quán)重設(shè)置為時間成本，如圖 4 運輸路徑簡化圖所示，假設(shè)出發(fā)點(生產(chǎn)基地)編號為0，目的地編號為6，編號為1，2，3，4，5分別代表水路倉庫1、中轉(zhuǎn)庫、鐵路倉庫1、倉庫2、倉庫3，又依據(jù)水路、公路及鐵路的特性，公路運輸時間短，鐵路運輸時間較長，而水路運輸時間最長的特性來設(shè)置路徑權(quán)重，例如，0→2權(quán)重為4，0→3權(quán)重為5，0→1權(quán)重為7；又根據(jù)路徑長短不同設(shè)置不同的權(quán)重，例如1→2與2→5皆為公路運輸，但是由于1→2距離較短則權(quán)重設(shè)為1，而2→3權(quán)重設(shè)為3；若無路徑到達某一目的地，則該相應(yīng)路徑權(quán)重設(shè)為∞。每次經(jīng)過中轉(zhuǎn)站可以選擇不同的路徑行走，每條路徑只對應(yīng)某一種運輸方式(公路、鐵路或水路)。則由此假設(shè)此時的路徑權(quán)值代表的是運輸時間，此時的鄰接矩陣可以寫成以下形式：

為找出所需運輸時間最少的運輸路徑，使用C++程序進行計算，計算結(jié)果如表2由Dijkstra算法計算出運輸時間最少的路徑所示。

表2 由Dijkstra算法計算出運輸時間最少的路徑

由表2可知，從生產(chǎn)基地到達目的地(配送倉庫)所耗費時間最短的路徑是：0→2→5→6。由于此次假設(shè)考慮的是緊急訂單的情況，因此選用運輸時間最少的運輸路徑，為能計算運輸成本，需要計算每一小節(jié)運輸距離以相應(yīng)運輸方式單位變動運輸費用最后加上相應(yīng)運輸方式固定運輸費用。由上訴結(jié)果可知，運輸時間最少的運輸路徑為0→2→5→6，該運輸路徑中的運輸方式均為公路，假設(shè)該路徑距離一共為1000km，又由劉娜翠等[2]提出的數(shù)據(jù)假設(shè)，固定運輸費用為100元，單位變動運輸費用為4元/km，則

路徑總費用=4×1000+100=40100元

該模型可以依據(jù)考慮情況的不同而設(shè)置不同的權(quán)重，從而得到符合要求的最優(yōu)結(jié)果。

4.2 第二段模型的檢驗

本文使用Solomon算例中的標(biāo)準(zhǔn)測試集r104的前25個數(shù)據(jù)進行模型檢驗，根據(jù)數(shù)據(jù)集所給數(shù)據(jù)運輸車輛最大載貨量為200個貨物，假設(shè)配送中心一共有10輛運輸車可用，數(shù)據(jù)集如表3所示。

表3 算例r104前25個數(shù)據(jù)

基于毛開富等[9]將學(xué)習(xí)因子寫為c11=2.5,c12=0.5,c21=1,c22=2.25，由Shi,Y[8]的文章中指出，ω1取0.9，ω2取0.4，本文將粒子群的初始規(guī)模設(shè)定為50，單位固定運輸費用設(shè)定為100元，單位變動運輸費用設(shè)定為4元/km位變動(單位固定費用、單位變動運輸費用以及車輛行駛速度的設(shè)置參照劉娜翠等在基于遺傳算法的汽車整車銷售物流配送路徑優(yōu)化文章中所使用的數(shù)據(jù)[2])，超出時間窗的懲罰系數(shù)定為200，而超出車輛額定載重的懲罰系數(shù)定為20000(為形成約束，懲罰系數(shù)應(yīng)設(shè)置得盡量大)[2]，基于多次實驗發(fā)現(xiàn)，迭代次數(shù)設(shè)置為100次已經(jīng)能夠得出較優(yōu)結(jié)果，因此在本文中算法的迭代次數(shù)設(shè)為100次。

基本的粒子群算法的迭代結(jié)果如圖 5(a)所示與改進后的粒子群迭代結(jié)果如圖 5(b)所示。

圖5 算法結(jié)果對比圖

由圖5算法結(jié)果對比圖所示，使用基本的粒子群算法圖5(a)以及改進后的粒子群算法圖5(b)在迭代100次后得到兩個不同的方案，使用基本粒子群算法得出的方案為：配送路線1：0→7→19→11→8→17→5→18→0，配送路線2：0→21→22→23→4→24→12→0，配送路線3：0→2→15→14→16→6→13→0，配送路線4：0→3→9→20→10→1→0；而使用改進后的粒子群算法得出的方案為：配送路線1：0→2→15→14→16→17→5→6→0，配送路線2：0→21→22→23→4→0，配送路線3：0→12→24→3→9→20→10→1→0，配送路線4：0→7→19→11→8→18→13→0。

將100次迭代所得結(jié)果可視化迭代結(jié)果對比圖如圖6所示：

圖6 迭代結(jié)果對比圖

由圖 6(a)基本粒子群算法的迭代次數(shù)與圖 6(b)改進后的粒子群算法可知，使用改進后的粒子群算法可以更快收斂找到滿意解。

最后依據(jù)兩種算法得出的結(jié)果分別初始化粒子群后，再次進行迭代，此時將迭代次數(shù)設(shè)置為1000。即，第一次使用粒子群算法是對所有結(jié)果進行全局搜索從而找到最優(yōu)方案；第二次使用粒子群算法是依據(jù)第一次所得結(jié)果，重新確定粒子群的初始位置后再次進行局部搜索，從而得出最終結(jié)果。通過實驗計算出使用兩種方案初始化粒子群在經(jīng)過1000次迭代之后將得到最優(yōu)配送方案，其結(jié)果與改進后的粒子群算法的計算結(jié)果相似，配送方案為配送路線1：0→2→15→14→16→17→5→0，配送路線2：0→21→22→23→4→0，配送路線3：0→12→24→3→9→20→10→1→0，配送路線4：0→7→19→11→8→18→6→13→0?；谌炙阉骱筮M行局部搜索得出得最佳方案圖如圖7所示。

圖7 基于全局搜索后進行局部搜索得出得最佳方案

將所得數(shù)據(jù)整理成表，最終實驗結(jié)果如表 4 計算結(jié)果所示。

表4 計算結(jié)果

由表4計算結(jié)果以及圖6迭代結(jié)果對比圖可知在算法僅進行100次迭代時，使用改進后的粒子群算法與使用基本的粒子群算法相比所找到的派送方案更優(yōu)，且所得結(jié)果更接近最終結(jié)果。因此，改進后的粒子群算法在面對規(guī)模較大的組合問題時更具優(yōu)勢，所需得迭代此次更少且方案更優(yōu)。從實驗結(jié)果可知，使用改進后的粒子群算法，在有限的迭代次數(shù)中，可以生成更優(yōu)的配送方案，通過改變路徑方案，可以減少相應(yīng)的運輸費用與運輸距離，而且還能滿足顧客對接收貨物的時間窗的需要。該模型從公司運營角度出發(fā)在考慮運輸成本最少的同時還考慮了影響顧客滿意度的時間窗的因素，極大地平衡了企業(yè)對運輸降低費用的需求與顧客對期望時間收到貨物的需求。

5 結(jié)論

本文通過建立兩段模型來規(guī)劃整車物流運輸路徑，由實證的計算結(jié)果可知，本文用到的改進粒子群算法可以找出費用(時間)所需更少的運輸路徑。在進行整車調(diào)度運輸路徑的規(guī)劃時，考慮了時效和費用對路徑分配的影響，可以通過需求(訂單是否緊急)靈活的選擇車輛的運輸路徑，再根據(jù)每段采用的運輸方式計算運輸成本。在今后的研究中，在考慮車企對運輸成本的需求以及客戶的需求之外，面對國家正大力倡導(dǎo)的節(jié)能減排，車企在進行整車運輸時也應(yīng)考慮碳稅政策以及承運商的生存問題，因此更加靈活多變的運輸路徑規(guī)劃是值得研究的一個課題，本文建立的整車調(diào)度運輸模型為整車調(diào)度運輸路徑規(guī)劃提供了一種思路。