帶時間窗車輛調(diào)度問題的改進(jìn)粒子群算法

王飛

甘肅政法學(xué)院計算機(jī)科學(xué)學(xué)院，蘭州 730070

帶時間窗車輛調(diào)度問題的改進(jìn)粒子群算法

王飛

甘肅政法學(xué)院計算機(jī)科學(xué)學(xué)院，蘭州 730070

帶時間窗車輛調(diào)度問題是一類典型的NP難解問題。為了克服標(biāo)準(zhǔn)粒子群算法存在早熟收斂和易陷入局部解等問題，提出了一種改進(jìn)的粒子群優(yōu)化算法。該算法在慣性權(quán)重遞減的基礎(chǔ)上通過群體極值進(jìn)行t分布變異，使算法跳出局部收斂，將該算法應(yīng)用于帶時間窗的車輛調(diào)度問題優(yōu)化。算例證明了改進(jìn)粒子群算法應(yīng)用于求解帶時間窗的車輛調(diào)度問題的可行性和有效性。

帶時間窗車輛調(diào)度問題；NP問題；粒子群優(yōu)化算法；t分布

1 引言

隨著市場競爭的日益加劇，科學(xué)技術(shù)的飛速發(fā)展和物流技術(shù)專業(yè)化水平的提高，許多企業(yè)已將先進(jìn)的物流理論技術(shù)引入到企業(yè)生產(chǎn)和經(jīng)營管理中，并且把物流作為提高市場競爭力和提升核心競爭能力的一個重要手段。作為實現(xiàn)物流組織的關(guān)鍵環(huán)節(jié)，合理的車輛調(diào)度對企業(yè)降低物流成本、提高服務(wù)質(zhì)量、提升運作效率以及增加經(jīng)濟(jì)收益都有著重要的意義。

車輛調(diào)度問題（Vehicle Scheduling Problem，VSP）已經(jīng)被證明是NP難題[1]，帶時間窗車輛調(diào)度問題（Vehicle Scheduling Problem with Time Windows，VSPTW）由于增加了時間約束這個限制條件，使原本具有NP復(fù)雜性的車輛調(diào)度問題的求解更增加了難度，該類問題，尤其規(guī)模較大時，很難求得精確解。近年來，最短路徑、散射搜索、節(jié)約法、禁忌、模擬退火、遺傳等算法在解決該類問題已得到了應(yīng)用[2-7]，但在收斂速度和收斂精度等方面還有待于提高。

粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）是一種模仿鳥群尋找食物飛行的新的智能仿生算法[8]，有著收斂速度快、參數(shù)設(shè)置少、易于實現(xiàn)等優(yōu)點，在車輛調(diào)度問題中已得到初步應(yīng)用[9-10]，取得了不錯的效果，但由于PSO存在容易停滯、容易陷入局部最優(yōu)等問題，故本文在采用慣性權(quán)重遞減的基礎(chǔ)上通過群體極值進(jìn)行t分布變異，使算法跳出局部收斂，將該算法應(yīng)用于帶時間窗的車輛調(diào)度問題優(yōu)化。通過實驗證明，本算法在減少計算時間和避免算法早熟現(xiàn)象方面均取得了不錯的效果。

2 帶時間窗車輛調(diào)度問題的數(shù)學(xué)模型

2.1 問題描述

帶時間窗車輛調(diào)度問題一般可描述為：有一個配送中心，負(fù)責(zé)向N個客戶完成配送任務(wù)，配送中心的車型為統(tǒng)一車型，擁有的車輛數(shù)為M輛，每輛車的最大裝載量為Q，已知客戶i到客戶j的運輸距離為dij及客戶i的需求量gi＜Q，最早允許車輛到達(dá)客戶i的時間為ai，最遲允許車輛到達(dá)客戶i的時間為bi，車輛的行駛速度為v，現(xiàn)要求設(shè)計一套合理的調(diào)度方案，使所有客戶的物資需求必須在規(guī)定的時間內(nèi)得到滿足，并確定每輛車的運輸線路，使得總運輸距離最低且滿足以下約束條件。

（1）每個客戶必須由一輛車來完成調(diào)度任務(wù)，且每個客戶的物資需求量不大于單輛車的最大裝載量。

（2）每輛車任務(wù)完成后必須返回到配送中心。

（3）每條線路的總運輸量不能超過車輛的最大裝載量。

2.2 數(shù)學(xué)模型

將配送中心和客戶以點i(i=0，1，…，N)來表示，i=0表示為配送中心。定義如下變量：

模型中，式（3）為目標(biāo)函數(shù)，為車輛最低的運輸距離；式（4）限定車輛由配送中心發(fā)出車輛總數(shù)不超過該配送中心擁有的車輛數(shù)；式（5）表示每輛車的最大運輸量不能超過它的承載量；式（6）表示客戶i的任務(wù)只能由一輛車來配送；式（7）表示某客戶點必定有某一輛車來自另一點完成運輸任務(wù)，并且只有一輛車完成該任務(wù)；式（8）表示某客戶點必定有某一輛車去向另一點完成運輸任務(wù)，并且只有一輛車完成該任務(wù)；式（9）～式（11）為車輛行駛的時間約束條件。

3 粒子群優(yōu)化算法

3.1 標(biāo)準(zhǔn)PSO

粒子群優(yōu)化算法是人們受到真實世界中鳥群尋找食物啟發(fā)，由Kennedy和Eberhart在1995年提出的一種群體智能優(yōu)化算法[8]。其基本原理是通過群體之間的信息共享和個體經(jīng)驗來修正個體行為，最終求取問題的最優(yōu)解。由m個粒子構(gòu)成的粒子群在D維空間以一定速度飛行搜索，第i個粒子的位置表示為：Xi= (xi1，xi2，…，xiD)，對應(yīng)的速度表示為Vi=(vi1，vi2，…，viD)，pi=(pi1，pi2，…，piD)為該粒子目前為止搜索到的最優(yōu)位置，pg=(pg1，pg2，…，pgD)為粒子群目前為止搜索到的最優(yōu)位置。粒子i在第k+1次迭代時第d維速度和位置的更新公式如式（12）和式（13）所示。

式中，c1、c2為加速系數(shù)；ω是慣性權(quán)重；r1，r2為0～1之間的隨機(jī)數(shù)。

3.2 改進(jìn)的粒子群算法

慣性權(quán)重w是粒子保持原來速度的系數(shù)，當(dāng)w較大時，算法具有較強(qiáng)的全局搜索能力，有利于搜索一個新的區(qū)域；當(dāng)w較小時，算法傾向于局部搜索，有利于粒子在當(dāng)前區(qū)域仔細(xì)搜索。本文慣性權(quán)重w采用遞減策略，以達(dá)到優(yōu)化的目的，其變化公式如式（14）所示：

式中，Nmax為算法的最大迭代次數(shù)，Ni為算法的當(dāng)前迭代次數(shù)，wmax為初始慣性權(quán)重，wmin為進(jìn)化到最大迭代次數(shù)時的慣性權(quán)重，通常取wmax為0.9，wmin為0.4。

針對PSO陷入局部最優(yōu)，變異操作是用來跳出局部收斂的常用方法。柯西變異和高斯變異是進(jìn)化規(guī)劃中常用的變異算子，柯西變異的全局搜索能力較強(qiáng)，能夠有效維持群體的多樣性，而高斯變異的局部開發(fā)能力較好，可以保證進(jìn)化后期的收斂速度。本文采用基于t分布的擾動算子。

t分布又稱學(xué)生分布，是英國統(tǒng)計學(xué)家哥賽特（Gosset）以“Student”的筆名在1908年發(fā)表[11]，含有自由度n的t分布的概率密度函數(shù)如式（15）所示：

當(dāng)n=1時，t分布變?yōu)闃?biāo)準(zhǔn)柯西分布，即t(n=1)= C(0，1)；當(dāng)n趨近于∞時，t分布就是標(biāo)準(zhǔn)高斯分布，即t(n→∞)=N(0，1)，一般n≥30時二者偏差可以忽略。不難看出，標(biāo)準(zhǔn)柯西分布和高斯分布是t分布的兩個邊界特例[12]。因此，t分布算子可以銜接柯西分布算子和高斯分布算子，選擇合適的自由度n，可以充分發(fā)揮柯西變異和高斯變異的優(yōu)勢，從而提高算法的靈活性和求解效果。

本文采用文獻(xiàn)[13]中提出的群體適應(yīng)度方差作為算法是否陷入早熟收斂的標(biāo)志：

式中，N為種群粒子數(shù)目，fi為第i個粒子的適應(yīng)度，fave為粒子當(dāng)前的平均適應(yīng)度，可按公式（17）計算；f限制σ2的大小，它的取值隨算法迭代的變化而變化，可按式（18）計算。式中，

粒子的群體適應(yīng)度方差σ2反應(yīng)粒子收斂的程度，當(dāng)σ2越小，粒子群越趨于收斂，當(dāng)σ2小于某一規(guī)定時，就認(rèn)為算法陷入早熟收斂現(xiàn)象。然后按照式（19）選擇自由度n，采用基于t分布的變異算子進(jìn)行變異。

對粒子位置按式（20）進(jìn)行重新分布。

4 改進(jìn)的粒子群算法在帶時間窗車輛調(diào)度問題中的應(yīng)用

4.1 粒子的編碼

本文采用文獻(xiàn)[13]的編碼，構(gòu)造2n維的空間對應(yīng)n個客戶的車輛調(diào)度問題，粒子i對應(yīng)的2n維向量Z分成兩個n維向量Zix和Ziy，分別表示服務(wù)客戶的車輛信息和車輛在客戶之間的路徑行駛次序。

4.2 粒子的解碼

（1）對于服務(wù)客戶的車輛，對粒子i的向量Zix取整，能夠得到配送中心分配給客戶i的車輛j。

（2）對于車輛j的路徑行駛次序，可用向量Ziy元素的大小順序來確定，即先尋找車輛j服務(wù)的客戶i，然后按照i對應(yīng)的Ziy值的大小，從小到大進(jìn)行編號排序，從而確定車輛j的路徑行駛次序。

例如，一個含有7個客戶點，3輛車的車輛調(diào)度問題，第i個粒子的位置向量Z，如表1所示。

表1 解碼前的粒子i的向量

根據(jù)粒子的解碼方式對Zix取整，可得到車輛在各個客戶的路徑行駛次序，如表2所示。

表2 解碼后的粒子i的向量

則粒子對應(yīng)的各車輛行駛路徑次序為（0表示配送中心）：

車輛1，0→2→6→0；車輛2，0→1→4→3→0；車輛3，0→7→5→0。

4.3 算法過程描述

步驟1算法初始化。輸入車輛調(diào)度問題的相關(guān)數(shù)據(jù)；輸入粒子群數(shù)目N、慣性權(quán)重因子wmax和wmin、學(xué)習(xí)因子c1和c2、最小群體方差σ2min、最大迭代次數(shù)Nmax和粒子的維數(shù)D。

步驟2適應(yīng)度計算。對粒子進(jìn)行解碼生成車輛調(diào)度方案，并根據(jù)各客戶的位置按式（3）來計算每個粒子的適應(yīng)度函數(shù)值，并且檢查是否滿足式（4）～式（11）的約束條件，若不滿足，令f=fmax，fmax是一個很大的數(shù)。

步驟3將每個粒子的個體極值Pi設(shè)置成當(dāng)前位置，全局極值Pg設(shè)置為群體中最佳粒子的當(dāng)前位置。

步驟4對群體中的每個粒子，根據(jù)式（12）～式（14）計算粒子的適應(yīng)度值，如果當(dāng)前位置優(yōu)于Pi和Pg，則用當(dāng)前位置更新Pi和Pg。

步驟5根據(jù)式（16）～式（18）計算群體適應(yīng)度方差σ2，并判斷是否滿足變異條件，若滿足，根據(jù)式（19）和式（20）進(jìn)行變異，轉(zhuǎn)入步驟4，否則轉(zhuǎn)入步驟6。

步驟6判斷當(dāng)前的迭代次數(shù)是否達(dá)到Nmax，若是，輸出最優(yōu)解，算法結(jié)束；否則轉(zhuǎn)向步驟4。

5 算例分析

為了驗證算法的可行性，對在100×100（單位：km）區(qū)域內(nèi)計算機(jī)隨機(jī)生成的1個配送中心和20個客戶的車輛路徑進(jìn)行調(diào)度，車輛行駛的速度是65 km/h，客戶位置（單位：km），需求量（單位：t）以及客戶允許到達(dá)的時間窗（單位：min）見表3，配送中心可使用的車輛數(shù)為5輛，每輛車的最大載重量為25 t。

分別采用粒子群算法和改進(jìn)的粒子群算法對該算例在同一臺計算機(jī)上進(jìn)行多次計算。求得該問題的最優(yōu)調(diào)度方案是其中3輛車參與配送，每輛車的行駛路徑、行駛距離（單位：km）及行駛時間（單位：min）如表4所示，最優(yōu)函數(shù)值（運輸總距離）隨函數(shù)的迭代次數(shù)變化的曲線如圖1所示。

從圖1不難看出，采用本文所提出的算法能夠快速準(zhǔn)確地求出帶時間窗車輛調(diào)度問題的最優(yōu)解，而且搜索到最優(yōu)值的時間和效率優(yōu)于標(biāo)準(zhǔn)粒子群算法，為求解該類問題提供了一種新的方法。

表3 客戶信息

表4 車輛的行駛路徑、行駛距離及行駛時間

圖1 算例的IPSO和PSO性能比較

6 結(jié)束語

本文提出了求解車輛調(diào)度問題的一種新的改進(jìn)方法。實驗證明了改進(jìn)粒子群優(yōu)化算法針對該問題具有良好的性能。本文求解的車輛調(diào)度問題是車輛在勻速行駛的過程中，但由于在實際行駛過程中，面臨著車輛行駛變速以及車輛調(diào)度等許多不確定因素，如何針對實際情況建立不同情況的實際模型，進(jìn)而尋找高效的算法，是后續(xù)研究的內(nèi)容。

[1]羅勇，陳治亞.基于改進(jìn)遺傳算法的物流配送路徑優(yōu)化[J].系統(tǒng)工程，2012，30（8）：118-122.

[2]Azi N，Gendreau M，Potvin J Y.An exact algorithm for a single-vehicle routing problem with time windows and multiple routes[J].European Journal of Operational Research，2007，178：755-766.

[3]Russell R A，Chiang W C.Scatter search for the VRP with time window[J].European Journal of Operational Research，2006，169：606-622.

[4]王雷.用節(jié)約法解帶有時間窗的車輛調(diào)度問題[J].黑龍江工程學(xué)院學(xué)報：自然科學(xué)版，2011，25（3）：18-20.

[5]鐘石泉，賀國光.多車場有時間窗的多車型車輛調(diào)度及其禁忌算法[J].運籌學(xué)學(xué)報，2005，9（4）：67-73.

[6]楊善林，馬華偉，顧鐵軍.時變條件下帶時間窗車輛調(diào)度問題的模擬退火算法[J].運籌學(xué)學(xué)報，2010，14（3）：83-90.

[7]魏國利，陳勁，張玉春.改進(jìn)遺傳算法求解VRPSTW問題[J].內(nèi)蒙古民族大學(xué)學(xué)報，2011，26（4）：395-397.

[8]Kennedy J，Eberhart R.Particle Swarm Optimization[C]// Proceedings of IEEE International Conference on Neural Networks，1995：1942-1948.

[9]劉志雄.基于粒子群算法的物流車輛優(yōu)化調(diào)度研究[J].武漢科技大學(xué)學(xué)報，2009，32（6）：615-618.

[10]豐偉，李雪芹.基于粒子群算法的多目標(biāo)車輛調(diào)度模型求解[J].系統(tǒng)工程，2007，25（4）：15-19.

[11]崔智超，王青建.數(shù)理統(tǒng)計學(xué)源流及應(yīng)用[J].大連教育學(xué)院學(xué)報，2005，2（2）：53-55.

[12]Rathie P N.Stable and generalized-t distributions and applications[J].Communications in Nonlinear Science and Numerical Simulation，2012，17（12）：5088-5096.

[13]鄔月春.基于自適應(yīng)變異粒子群算法的物流配送路徑優(yōu)化[J].蘭州交通大學(xué)學(xué)報，2012，31（1）：114-117.

WANG Fei

School of Computer Science,Gansu Institute of Political Science and Law,Lanzhou 730070,China

Vehicle Scheduling Problem with Time Windows（VSPTW）is a typical Non-deterministic Polynomial hard（NP-hard）optimization problem.To overcome the shortcomings such as premature convergence and fall into local optimal, an Improved Particle Swarm Optimization（IPSO）algorithm is put forward.In the algorithm,the adaptive mutation based on t distribution on the basis of the inertia weight decreasing is used to make the algorithm jump out of local convergence. The algorithm is applied to VSPTW.The mathematical model is established and the detailed implementation process of the algorithm is introduced.The simulation results show that the algorithm is valid and feasible to solve VSPTW.

Vehicle Scheduling Problem with Time Windows（VSPTW）;NP problem;Particle Swarm Optimization（PSO）; tdistribution

A

TP301.6

10.3778/j.issn.1002-8331.1309-0319

WANG Fei.Study on Vehicle Scheduling Problem with Time Windows based on Improved Particle Swarm Optimization.Computer Engineering and Applications,2014,50（6）：226-229.

甘肅省科技支撐計劃項目（No.1304FKCA097）；甘肅政法學(xué)院青年科研資助項目（No.GZF2012XQNLW12）。

王飛（1978—），男，講師，研究方向：CSCW，智能算法。E-mail：wangfei6128@126.com

2013-09-23

2013-11-10

1002-8331（2014）06-0226-04