整車智能調度運輸研究*

□ 李董潔，梁革英

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

1 引言

為解決銷售給客戶的汽車里程表為零公里的要求，就要求汽車生產企業將汽車直接運輸到指定的銷售地點。由于汽車企業運輸的車輛變多、地點變多，手工分派不能滿足企業運輸的需求，需要使用計算機智能選擇整車運輸路徑。整車的運輸方案影響著企業的利益和顧客對企業的滿意度，如何選擇合適的運輸路徑是整車運輸的核心問題，合理的路徑安排不僅可以降低運輸成本，還可以提高顧客對企業的滿意度。因此，本文在平衡運輸成本與運輸時間的情況下建立運輸模型。

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

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

2 研究思路

為解決汽車制造企業整車運輸的問題，根據整車運輸的特點將整車運輸過程分成兩段：一段是跨省的長距離運輸，即從生產廠家運輸到銷售商所在省的中轉倉庫；另一段是省內的短距離配送運輸，即從中轉庫運輸到銷售商的銷售點。一般物流的運輸方式有四種：水路運輸、鐵路運輸、公路運輸以及航空運輸。因為航空運輸的成本較高且運輸能力有限，故一般整車調度運輸不采用航空運輸。對于跨省的長距離運輸，運輸方式主要有三種方式：水路運輸、鐵路運輸和公路運輸[13]。而對于省內城市之間的運輸，由于目前在全國各地省內的高速路網已完善，時間與效率能滿足客戶對整車運輸的要求，成本在可控的范圍內，所以省內運輸一般通過公路運輸到指定的銷售網點。

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

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

為實現上述目標，根據運輸的特征建立兩段路徑模型：第一段，由倉庫運輸到各省份相應的中轉庫(也可以稱為配送中心)；第二段，由中轉庫運送到經銷商。如圖1整車調度運輸網絡所示。

圖1 整車調度運輸網絡

3 模型建立

3.1 全局假設

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

3.2 第一段模型

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

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

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

①根據訂單的緊急程度進行規則選擇，若為緊急訂單，使用以時間作為路徑權重的運輸規則；若為非緊急訂單，使用以費用作為路徑權重的運輸規則。

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

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

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

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

c.重復上述步驟二和步驟三，直至得出最終結果。

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

具體實現流程圖如圖 2所示。

圖2 具體步驟流程圖

3.3 第二段模型

3.3.1 第二段模型的假設

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

②運輸車輛最后會回到中轉庫。

③每一個經銷商只能由一輛運輸車進行配送。

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

⑤每次運輸的車輛為同一款車系。

3.3.2 符號說明

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

表1 符號說明

3.3.3 第二段路徑計算

構建第二段模型是為了解決整車從配送中心到達省內各地經銷商的問題，除了要考慮整車的運輸費用外，還需考慮經銷商對接收整車的時間區間的期望。因此建立以總整車配送費用最小為目標建立含有時間窗的運輸總成本按以下方式計算[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)

根據實際運輸情況，做如下定義：

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

3.3.4 改進后的粒子群算法實現路徑選擇

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

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

(9)

(10)

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

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

將權重ω改寫為：

(11)

改進非對稱學習因子[9]，則c1與c2可以寫成：

(12)

4 模型檢驗

4.1 第一段的檢驗

對實際路徑及運輸節點進行相應簡化[18]，抽象得到如圖 3所示的運輸路徑圖。由圖 3得知，從整車生產基地出發由水路、鐵路和公路可以將整車運輸到中轉庫，而針對水路和鐵路的運輸還需要進行公路運輸才能把整車運送到中轉庫；再由中轉庫或水路倉庫、鐵路倉庫經公路或鐵路運輸到相應的倉庫(倉庫之間可以進行運輸)；最后經公路將整車運送到配送中心。

圖3 運輸路徑情況圖

將圖 3進行簡化，將生產基地、倉庫、中轉庫等節點用編號指代，隱去公路、鐵路以及水路的標識，給路徑給予相應的權值如圖4運輸路徑簡化圖所示。

圖4 運輸路徑簡化圖

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

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

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

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

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

該模型可以依據考慮情況的不同而設置不同的權重，從而得到符合要求的最優結果。

4.2 第二段模型的檢驗

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

表3 算例r104前25個數據

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

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

圖5 算法結果對比圖

由圖5算法結果對比圖所示，使用基本的粒子群算法圖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次迭代所得結果可視化迭代結果對比圖如圖6所示：

圖6 迭代結果對比圖

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

最后依據兩種算法得出的結果分別初始化粒子群后，再次進行迭代，此時將迭代次數設置為1000。即，第一次使用粒子群算法是對所有結果進行全局搜索從而找到最優方案；第二次使用粒子群算法是依據第一次所得結果，重新確定粒子群的初始位置后再次進行局部搜索，從而得出最終結果。通過實驗計算出使用兩種方案初始化粒子群在經過1000次迭代之后將得到最優配送方案，其結果與改進后的粒子群算法的計算結果相似，配送方案為配送路線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。基于全局搜索后進行局部搜索得出得最佳方案圖如圖7所示。

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

將所得數據整理成表，最終實驗結果如表 4 計算結果所示。

表4 計算結果

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

5 結論

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