帶時間窗車輛調度問題的改進粒子群算法

王飛

甘肅政法學院計算機科學學院，蘭州 730070

帶時間窗車輛調度問題的改進粒子群算法

王飛

甘肅政法學院計算機科學學院，蘭州 730070

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

帶時間窗車輛調度問題；NP問題；粒子群優化算法；t分布

1 引言

隨著市場競爭的日益加劇，科學技術的飛速發展和物流技術專業化水平的提高，許多企業已將先進的物流理論技術引入到企業生產和經營管理中，并且把物流作為提高市場競爭力和提升核心競爭能力的一個重要手段。作為實現物流組織的關鍵環節，合理的車輛調度對企業降低物流成本、提高服務質量、提升運作效率以及增加經濟收益都有著重要的意義。

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

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

2 帶時間窗車輛調度問題的數學模型

2.1 問題描述

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

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

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

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

2.2 數學模型

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

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

3 粒子群優化算法

3.1 標準PSO

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

式中，c1、c2為加速系數；ω是慣性權重；r1，r2為0～1之間的隨機數。

3.2 改進的粒子群算法

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

式中，Nmax為算法的最大迭代次數，Ni為算法的當前迭代次數，wmax為初始慣性權重，wmin為進化到最大迭代次數時的慣性權重，通常取wmax為0.9，wmin為0.4。

針對PSO陷入局部最優，變異操作是用來跳出局部收斂的常用方法?？挛髯儺惡透咚棺儺愂沁M化規劃中常用的變異算子，柯西變異的全局搜索能力較強，能夠有效維持群體的多樣性，而高斯變異的局部開發能力較好，可以保證進化后期的收斂速度。本文采用基于t分布的擾動算子。

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

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

本文采用文獻[13]中提出的群體適應度方差作為算法是否陷入早熟收斂的標志：

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

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

對粒子位置按式（20）進行重新分布。

4 改進的粒子群算法在帶時間窗車輛調度問題中的應用

4.1 粒子的編碼

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

4.2 粒子的解碼

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

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

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

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

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

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

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

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

4.3 算法過程描述

步驟1算法初始化。輸入車輛調度問題的相關數據；輸入粒子群數目N、慣性權重因子wmax和wmin、學習因子c1和c2、最小群體方差σ2min、最大迭代次數Nmax和粒子的維數D。

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

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

步驟4對群體中的每個粒子，根據式（12）～式（14）計算粒子的適應度值，如果當前位置優于Pi和Pg，則用當前位置更新Pi和Pg。

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

步驟6判斷當前的迭代次數是否達到Nmax，若是，輸出最優解，算法結束；否則轉向步驟4。

5 算例分析

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

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

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

表3 客戶信息

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

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

6 結束語

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

[1]羅勇，陳治亞.基于改進遺傳算法的物流配送路徑優化[J].系統工程，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]王雷.用節約法解帶有時間窗的車輛調度問題[J].黑龍江工程學院學報：自然科學版，2011，25（3）：18-20.

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

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

[7]魏國利，陳勁，張玉春.改進遺傳算法求解VRPSTW問題[J].內蒙古民族大學學報，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]劉志雄.基于粒子群算法的物流車輛優化調度研究[J].武漢科技大學學報，2009，32（6）：615-618.

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

[11]崔智超，王青建.數理統計學源流及應用[J].大連教育學院學報，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]鄔月春.基于自適應變異粒子群算法的物流配送路徑優化[J].蘭州交通大學學報，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）；甘肅政法學院青年科研資助項目（No.GZF2012XQNLW12）。

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

2013-09-23

2013-11-10

1002-8331（2014）06-0226-04