基于多態(tài)蟻群算法的多目標郵政物流車輛路徑問題研究

摘 要：針對在現有郵路運輸的基礎上加載一體化物流項目后的郵政物流車輛調度與路徑選擇優(yōu)化問題，建立了基于硬時間窗、車輛混合搭載、往返歸集的多目標郵政物流車輛路徑問題數學模型，以四川郵政雅芳一體化混合物流2008年5月的數據為例，利用自適應的多態(tài)蟻群算法對帶時間約束多目標混合郵政物流VRP進行了求解。結果表明多態(tài)蟻群算法可以求解多目標郵政物流VRP，能提高收斂速度和尋優(yōu)性能。

關鍵詞：車輛路徑問題；多態(tài)蟻群算法；多目標；郵政物流

中圖分類號：TP301.6文獻標志碼：A

文章編號：1001-3695(2009)06-2070-04

doi:10.3969/j.issn.1001-3695.2009.06.021

Research of post logistic VRP with multi-objective based on PACA

LV Xiong-wei，ZHAO Da，LI Jun

(School of Economic Management， Southwest Jiaotong University， Chengdu 610031， China)Abstract:According to the post logistic vehicle scheduling and routing optimization problem on basis of the post transportation as well as the integration post logistical project，established the model of multi-objective post logistics VRP on basis of the hard time windows， mixed loading， and round-trip collection.Used the adaptive polymorphic ant colony algorithm to solve the multi-objective post logistic VRPTW， by which took YaFang integrated post with logistics services in May 2008 by Sichuan post as an example.The results demonstrate that PACA can solve the multi-objective post logistics VRP，and also improve the astringency velocity and the optimizing property.

Key words:VRP（vehicle routing problems）；PACA（polymorphic ant colony algorithm）；multi-objective；post logistic

0 引言

車輛路徑問題（VRP）是指對于一系列客戶點，車隊按照一定的行車路線有序地經過它們，如何安排車輛、路線等相關因素，使得目標成本最優(yōu)。VRP最早是Danzig和Ramser于1959年提出的，涉及經濟學、博弈論、運籌學、應用數學、組合優(yōu)化、計算機軟件、計算機應用、運輸管理、工業(yè)工程與物流科學等眾多學科，是典型的NP難題，是運籌學和組合優(yōu)化等領域的前沿與熱點研究問題。郵政內部生產車輛的管理主要由中國郵政集團公司網絡運行部統(tǒng)一調度指揮，各級郵區(qū)中心局負責所轄郵路車輛的調度管理，中郵物流負責全國集散網和物流車輛的調度管理。其中物流集散網運輸中除了部分郵路或大客戶開行了物流專線外，大部分小件物流商品和一體化物流項目均搭載在中心局郵路車輛上混合運行。郵政物流在區(qū)域集散中心之間通過與郵航、行郵專列和一級干線郵路混合裝載及單獨開設集散郵路的模式實現實物傳遞，省及省以下的郵路除部分業(yè)務量大的局單獨開設集散郵路以外，大部分支線郵路還是與郵件混合裝載運輸。因此，郵政的車輛路徑問題包括傳統(tǒng)郵件郵路車輛的調度與管理、物流混合郵路的車輛調度與管理兩類，集散網專線本質上可以視為一類傳統(tǒng)郵件郵路車輛增開問題。相比傳統(tǒng)VRP特征而言，郵政物流車輛路徑問題主要是在多級郵件運輸集散體系下，針對一系列郵件和物流商品等，在滿足合理搭載、車輛安排、路徑選擇和時間限制等約束條件下，研究車輛運輸與路徑安排策略，使總體運輸費用、實際利用車輛數和服務質量等目標函數最優(yōu)化，這是一個更為復雜的帶時間窗、混合裝載、往返歸集的多約束多目標VRP。蟻群算法是由Colorni等人^[1]首先提出的一種仿生算法，是受螞蟻覓食行為的啟發(fā)而發(fā)展起來的一種新型元啟發(fā)式優(yōu)化算法，在解決優(yōu)化和分布式控制問題方面有獨到的優(yōu)勢。它可以針對難解的離散優(yōu)化問題，利用一群人工螞蟻的協(xié)作來尋找更優(yōu)的解。蟻群算法既可以解決靜態(tài)的組合優(yōu)化問題，又可以解決動態(tài)的組合優(yōu)化問題，最早被成功用于TSP。目前逐漸發(fā)展出許多新的改進算法，如蟻群系統(tǒng)^[2]、最大最小螞蟻系統(tǒng)、基于排序的螞蟻系統(tǒng)、多態(tài)蟻群算法、具有變異特征的蟻群算法、自適應調節(jié)信息素的蟻群算法、具有隨機擾動特征的蟻群算法等。

1 問題分析與模型建立

1.1 問題描述

多目標郵政物流VRP可以描述為由一個中心（郵區(qū)中心局和區(qū)域/非區(qū)域物流集散中心）、一個車輛集合和一個由N個客戶組成的客戶集合（下級郵區(qū)中心局/縣區(qū)級郵件處理中心和物流集散點）構成的兩級郵件/物流送配系統(tǒng)。每個客戶都同時有送貨需求（進口郵件和物流商品）和取貨需求（出口郵件和物流商品），在滿足所有客戶的送/取貨需求、車輛負載容量、時間窗、郵件歸集和物流組合配載優(yōu)化等條件下，使系統(tǒng)車輛運輸費用最小、物流服務質量最佳和車輛數最少。

基本假設如下：

a）假設對同一城市物流集散中心與中心局作業(yè)場所不同址的，都不考慮其間的距離問題，將其視為同一中心，其裝卸作業(yè)時間和之間路途時間均在中心裝卸作業(yè)時間中統(tǒng)一考慮。所有郵車都從中心出發(fā)，并最后返回中心；對各下級中心自有郵車往返中心之間的，將返回時間逆向視為從中心的出發(fā)時間。

b)所有物流商品和郵件都嚴格按照作業(yè)時間限制運輸，不存在積壓問題，不考慮物流商品和郵件的庫存費用。

c)物流商品和郵件運輸車輛型號相同且運載能力有限，運輸費用由固定派車費和與行駛距離線性相關的變動費用兩部分組成；根據客戶需求制訂車輛的裝載計劃，使同一車輛回路可以服務數量不等的客戶；每個客戶同一計劃期內至少接受一輛車的服務，一個子回路可能對應多輛車。

d)所有客戶進、出口郵件和物流商品的需求獨立并已知，客戶i的進口郵件需求di與進口物流商品需求ri之和（di＋ri）、出口郵件需求為pi的最大值均小于單臺車輛的最大裝載容量q，即每輛車至少可以服務一個客戶。超過容量的可以單獨派車專遞運輸。

e)郵運車輛必須在指定的時間范圍[ta，tb]內到達客戶處，即不早于ta和不晚于tb；物流商品只需要在計劃期內到達即可；時間窗約束為必須滿足的條件，否則視為該次配送任務失敗，即為硬時間窗要求。

f)各點物流商品和郵件裝卸作業(yè)時間固定，不考慮信息傳輸延遲和每天物流商品及郵件變化產生的作業(yè)處理時間差異，不考慮每天路況、車況等因素對車輛在途運輸配送時間的影響。g)服務質量由車輛運輸費用、配送時限、配載方式等條件按不同的權重方式構成，物流商品必須優(yōu)先實行整體配載。

1.2 數學模型

1)目標函數

決策變量是中心安排車輛的行車路線、郵運車次和發(fā)車時間。目標函數是運輸路徑最短、物流商品的服務質量最佳、總體派車數最少。

數學模型表示如下：

f1=min(Tt=1(

Kk=1

Ni=0

Ni≠j，j=0xijklijqijkPi+Ni=0

Ni≠j，j=0xijkRi)（1）

f2=min(Ni=1QoSi)=min(Ni=1fri/ρ1+Δt/ρ2)（2）

f3=min(Kk=1Ni=1Nj=1xijk)（3）

1/f=1/f1+1/f2+1/f3（4）

其中：f為多目標權重優(yōu)化函數；f1為最少運輸費用目標函數；Pi為中心到客戶i的單位重量運輸費用；qijk為車輛k從客戶i到j的在途運輸量；Ri為中心到客戶i處的固定派車費用；f2為最大服務質量目標函數，與運輸費用和實際到達時間線性相關；f3為最少車輛數；lij為郵運網絡中客戶i與j之間的最短距離，包括客戶點之間和各客戶點與中心之間的距離；fri為物流貨物的配送費用；ρ1為配送費用對服務質量的影響權重因子；Δt為實際到達時間與最早到達時間之差的絕對值；ρ2為時間差對服務質量的影響權重因子。

2)約束條件

QoSi=fri/ρ1+Δt/ρ2

fri=l0i c

Δt=tbik-ti（5）

Nj=1xijk=Nj=1xjik≤1;i=0;k=1，…，K（6）

Kk=1 Nj=0，j≠ixijk=1；i=1，…，N（7）

Ni=1Nj=1xijk≤|S|-1；k=1，…，K（8）

Kk=1Ni=0，i≠jxijk(eij+ti+ei)=tj；j=1，…，N（9）

taik≤(tik+ei)≤tbik（10）

Nj=0q0jk=Ni=0Nj=0xijk(dj+rj)；k=1，…，K（11）

Kk=1Ni=0

qijk-(dj+rj)=Kk=1Ni=0

qjik-pj；j=0，…，N（12)

Ni=0qi0k=Ni=0Nj=0xijkpj；k=1，…，K（13)

0≤qijk≤q；i， j=0，…，N；k=1，…，K（14）

其中：c為單位物流貨物運輸費用；tik為車輛k到達客戶i的時間，不得早于taik，不得晚于tbik；eij為車輛從客戶i到客戶j的在途運輸時間；ei為客戶i的裝卸作業(yè)時間；Xijk為0-1決策變量。

xijk=1 車輛k從點i到點j

0 否則

式(4)定義了客戶點的服務質量。式（5）保證每輛車都從中心出發(fā)并最后返回中心。式（6）和（7）保證了每個客戶點只能被同一輛車訪問一次。式（8）為支路消去約束，S為用戶集合的所有子集構成的集合。式（9）和（10）定義了時間窗約束。式（11）保證車輛從中心出發(fā)時的載貨量等于所服務客戶的進口郵件量和配送物流量之和。式（12）表示車輛在經過客戶j時的前后載貨量變化。式（13）表示車輛回到中心的載貨量為已運輸郵路客戶的出口郵件量之和。式（14）表示車輛在任何時候的負載量都不超過車輛容量限制。

2 基于蟻群算法的VRPMC問題求解

擬采用多態(tài)蟻群算法^[3]對多目標郵政物流VRP問題求解，在傳統(tǒng)蟻群算法的基礎上，考慮自適應的轉移和信息素更新策略^[4]，對算法的選擇、更新和協(xié)調機制作進一步改進。考慮到蟻群社會的分工多樣性，將時間窗、車輛裝載容量等約束條件的任務賦予偵察螞蟻，在此基礎上滿足郵件運輸成本最低、物流商品的服務質量最高、總體派車數最少的可行解的搜索任務由搜索螞蟻來完成。通過不同種類螞蟻的分工協(xié)作，最后將信息素自適應策略與多態(tài)蟻群算法相融合，克服傳統(tǒng)蟻群算法計算時間長、易出現早熟停滯等缺陷^[5]。

首先利用多態(tài)蟻群算法，將蟻群算法中的螞蟻分為偵察蟻和搜索蟻兩類^[6]。偵察蟻群負責局部偵察，搜索蟻群負責全局搜索。先將偵察蟻賦予多約束條件的任務，以每個客戶點為中心進行局域偵察，并以偵察素來標記偵察結果，為下一步搜索蟻到達該點后選擇下一個客戶點提供輔助信息。將N只偵察蟻分別放置在N個客戶點上，每只偵察蟻以所在點為中心，偵察其他N-1個點的可行性，可行性越大則該路徑上的偵察素就越高。偵察素主要由裝載容量約束偵察素和時間窗匹配偵察素兩部分組成，權重系數分別為ω1、ω2：

ω1＋ω2＝l；0<ω1，ω2<1（15）

容量約束滿足，則該項對偵察素貢獻記為ω1C1；不滿足則對偵察素貢獻為0。時間窗約束的偵察素貢獻為ω2εjiC2。其中εji為匹配因子，計算如下： 

εji=L([aji，bji]，[ai，bi])/(bi-ai)

aji=aj+tj+eji（16 ）

其中：L([aji，bji]，[ai，bi])為兩個時間窗重疊部分的長度，由路徑起始點時間窗表示兩個時間窗重疊部分的長度。在[aji，bji]一定的情況下，重疊部分越大，εji的值越大，表明點j為i的前趨從時間窗的角度上講越合理。

綜合以上偵察蟻的總偵察素為

Sij=ω1C1+ω2εjiC2 εji≠0;點j在i的前置

0否則（17）

考慮到初始時刻路徑上需要一定信息素，故置初始時刻各條路徑上的信息素為

τij(0)=CSij Sij≠0

0Sij=0（18）

其中：C為初始時刻各條路徑上信息素濃度，是一個常數。通過偵察蟻標記的偵察素蹤跡，搜索蟻就可以在這些信息素的輔助下進行有方向的搜索，既提高效率又能找到優(yōu)化解。

搜索蟻群的任務是作全局搜索，每到一個客戶點，根據偵察素和各邊的信息素等信息來選擇下一個客戶，直至找到并標記最佳路線。對搜索蟻群，螞蟻l（l＝1，2，…，N）在運動過程中的t時刻，從i轉移到j的概率為

P1ij=ω1ταijηβij/（Nj=1ταijηβij）+ω2[θj/(|svj-aj|+|svj-bj|)]/[Nj=1θj/(|svj-aj|+|svj-bj|)]； j=1，2，…，N;Sij≠0

0 其他（19）

其中：P1ij為螞蟻l從i轉移到j的狀態(tài)轉移概率；τij為邊（i，j）上的信息素軌跡強度；ηij=1/f(dij)為邊（i，j）的能見度，j是尚未訪問的客戶點；A表示螞蟻下一步允許選擇的客戶點集合；α和β為兩個參數，分別反映了螞蟻在運動過程中積累的信息素和啟發(fā)信息在螞蟻選擇路徑中的相對重要性；ω1和ω2為權重系數，其條件滿足式（19）。

搜索蟻每到達一個客戶點，利用偵察素，只在較小范圍內搜索，大大縮小了搜索規(guī)模。當所有螞蟻完成一次巡游，各路徑上信息素蹤跡要根據下式作調整：

τnewij=(1-ρ)τoldij+ρΔτij Sij≠0

(1-ρ)τoldij其他（20）

Δτij=Kk=1τkij（21）

Δτkij=

Q(1-xk/Xk)[ξ1c1+ξ2εjic2]/f(Lk) 螞蟻k經過i， j；Sij≠0

0否則（22）

為了保持蟻群算法的全局搜索能力，又能提高算法的搜索速度，采用自適應改變ρ值的策略^[5]：

ρ（t）=0.95ρ(t-1) 0.95ρ(t-1)≥ρmin

ρmin0.95ρ(t-1)≤ρmin（23）

其中：Δτij為本次循環(huán)所有螞蟻在路徑i、j上釋放的信息素濃度之和；τkij為第k只螞蟻在本次循環(huán)中留在路徑i、j上的信息素濃度，第k只螞蟻到達i之前已有Xk只螞蟻經過i點，其中有xk只螞蟻選擇了有向弧段（i，j）；Q為螞蟻每次釋放的信息量。由此可以看出，路徑上信息素增量Δτij會隨著螞蟻吸引力的增大而有所減小，與螞蟻的不斷集聚達到一種動態(tài)自適應的平衡，從而使求解過程更加有效。每只搜索蟻根據偵察蟻留下的偵察素，只在可能是最優(yōu)解組成部分的路徑上留下合適的信息素；根據轉移概率，每只搜索蟻只在可能是最優(yōu)解組成部分的路徑上增加信息素的濃度。ρmin為ρ的最小值，ρ(t0)=1，可以防止ρ過小而降低算法的全局搜索能力。

多態(tài)蟻群算法步驟如下：

a)初始化Q、C和最大進化代數NC，max。

b)將n只偵察蟻分別放在n個客戶中，每個偵察蟻以所在客戶i為中心，偵察其他n-1個客戶，按式（17）計算總偵察素，并將結果賦予Sij。

c)按式（18）置初始時刻各條路徑上的信息量。

d)置進化代數NC初值為0。

e)隨機選擇每只搜索蟻的初始位置，并將該位置放入每個搜索蟻對應的搜索表中。

f)按式（19）計算每只搜索蟻l將要轉移的位置，假設為j，上一個位置假設為i，并將j放入搜索蟻l對應的搜索表中，直至每只搜索蟻完成一個循環(huán)，得到一個解。

g)計算各搜索蟻的目標函數值f(Ll）(l =1，2，…，N），并記錄當前最好解。

h)進行2-opt局部優(yōu)化，若新解優(yōu)于原解，則替換之；反之則保留原解。

i)若達到最大進化代數NC，max，轉l)，若未達最大進化代數但所求得的解在最近若干代中無明顯改進，按式（23）調整揮發(fā)系數ρ，轉k）；否則轉j)。

j）按式（20）修改各路徑上的信息素濃度，置Δτij=0，置搜索表為空。

k)NC←NC+1，轉e)。

l)輸出最優(yōu)解。

上述算法中，引入了多種類型的蟻群和信息素，縮小了搜索子空間的規(guī)模，并用調整揮發(fā)系數ρ的方法進行進一步尋優(yōu)，與基本蟻群算法相比，該算法的效率、尋優(yōu)質量有較大提高。

3 一類多目標混合郵政物流VRP問題實例分析

以四川省郵政公司11個主要地市的進出口郵件和雅芳一體化配送項目組成的多目標混合郵政物流VRP問題為例，提取了2008年5月的數據。根據上述要求建立數學模型，并運用蟻群算法進行求解。

3.1 實驗參數設計

各點距離參數和地市編碼如表1所示。

3.2 各點時間約束

根據各點郵件要求配送時限和交通狀況，列出成都到各點之間的車輛在途運輸時間、郵件平均裝卸作業(yè)時間和到達時間上下限，有關參數如表2所示。

以2008年5月各點雅芳一體化配送項目數據為例，分析各市局進、出口郵件和物流數據對比如圖1~3所示。其中橫坐標為日期；縱坐標為郵件重量，單位為kg。

計算中的常量參數ρ(t0)為1，α為1，β為2，ω1為0.4 ，ω2為0.6，C為3，max(Pc)為10，迭代次數100，ρ1為2，ρ2為3。車輛最大裝載量Q為8 000 kg，所有客戶點的單位kg#8226;km的運輸成本Pi為0.001元/kg#8226;km，所有車輛的固定派車費用Ri為800元/車，中心與各點間的距離見表1，各點之間時間約束見表2。由于物流業(yè)務發(fā)展的原因，暫無出口一體化物流項目在運作，同時在考慮車輛裝載量限制后暫不考慮運輸車輛的容積限制。

3.3 計算結果分析

一般情況下α取值為1~2，β取值為1~3，蟻群算法的解比較理想，（α，β）＝｛（1，1），（1，2），（1，3），（2，1），（2，2），（2，3）｝。在上述參數組合下計算結果如表3所示。

從計算結果可知，在滿足時間窗約束和車輛裝載容量限制的前提下，如果按車輛派車數最少的目標，則有組合1和4兩種不同的車輛調度方式。如果按照總體運行費用最少的原則，則只有組合2這一個最優(yōu)解，但是月度派車數卻不是最少的。如果按一體化混合郵政物流服務質量最佳的原則，則組合2是最優(yōu)解。組合2的多目標優(yōu)化值最優(yōu)，因此組合2為雅芳一體化混合郵政物流車輛路徑問題的最優(yōu)解。

其對應的郵路安排如下：

車輛1：成都—德陽；車輛2：成都—綿陽；車輛3：成都—廣元；車輛4：成都—樂山；車輛5：成都—眉山—雅安—成都；車輛6：成都—自貢；車輛7：成都—資陽—內江—成都；車輛8：成都—瀘州；車輛9：成都—宜賓。

總費用節(jié)省3.62萬元，降低費用5.89%。其中計算結果優(yōu)化主要的對應郵路如下：

a）成都—眉山—雅安—成都

優(yōu)化前該郵路周期內車輛運行費用為7.43萬元

優(yōu)化后該郵路周期內車輛運行費用為5.84萬元

實際降低費用21.49%

b)成都—資陽—內江—成都

優(yōu)化前該郵路周期內車輛運行費用為9.03萬元

優(yōu)化后該郵路周期內車輛運行費用為7.15萬元

實際降低費用21.20%

計算結果表明，車輛的優(yōu)化調度在具體郵路上的效益更顯著。

有關郵路路線和時間安排如表4所示。

4 結束語

本文針對在多級郵件運輸集散體系下郵政物流多品種、多約束、多目標的特性，分析了在現有郵路運輸的基礎上加載一體化郵政物流項目需求后的車輛調度與路徑選擇優(yōu)化問題，建立了基于硬時間窗、車輛混合搭載、往返歸集的多目標郵政物流車輛路徑問題數學模型，利用自適應的多態(tài)蟻群算法對帶時間約束多目標混合郵政物流VRP進行了求解。該算法引入了群體間的交互作用，能更好地交換信息，并在搜索過程中保持多樣性。在使用相同策略的情況下，比傳統(tǒng)算法顯示了更好的性能。在啟發(fā)式因子的設計中加入了車輛剩余負載能力，使總信息同時考慮了時間窗和車輛負載容量兩個因素，將車輛配送載貨量的初始化設計為一個與剩余客戶的送取貨需求相關且可在一定范圍內變化的隨機值。以四川郵政雅芳一體化混合物流2008年5月的數據為例進行了仿真實驗，通過與原郵運車輛總行程和總費用的對比結果表明，PACA不僅可以提高車輛的裝載利用率，而且可以有效地求解多目標郵政物流VRP問題，能夠以較快的收斂速度得到滿意解，改善了尋優(yōu)性能。

參考文獻：

［1］COLORNI A，DORIGO M，MANIEZZO V.Distributed optimization by ant colonies[C]//Proc of the 1st European Conference on Artificial Life.Paris:Elsevier Publishing，1991:134-142.

[2]DORIGO M，STTZLE T.Ant colony optimization[M].[S.l.]:MIT Press，2004:161-167.

[3]馬良，朱剛，寧愛兵.蟻群優(yōu)化算法[M].北京：科學出版社， 2008.

[4]劉志碩，申金升，柴躍廷.基于自適應蟻群算法的車輛路徑問題研究[J].控制與決策，2005，20(5):562-566.

[5]王穎，謝劍英. 一種自適應蟻群算法及其仿真研究[J].系統(tǒng)仿真學報，2002，14(l):31-33.

[6]陳幼林，王勁愷.帶時間窗車輛路徑問題的改進蟻群算法研究[J].計算機工程與應用，2006，42(29):218-219.