基于改進粒子群算法的物流配送車輛調度

馬冬青, 王蔚

MA Dongqing1, WANG Wei2

1.華北計算技術研究所, 北京 100083

2.太極計算機股份有限公司, 北京 100083

1.North China Institute of Computing Technology, Beijing 100083

2.TAIJI Computer Corporation Limited, Beijing 100083

1 引言

隨著市場經濟的蓬勃發展和物流水平的不斷提高，物流配送對經濟發展、商品流通和大眾消費起到越來越重要的作用。采用科學的物流管理，是提高物流效率、降低成本、提高服務質量的重要途徑。物流企業的管理涉及多個方面，其中配送是一個重要環節。配送指按照客戶的要求進行收攬、派發。配送過程包括集貨、分貨、配貨、配裝、送貨等多項活動，其中車輛配送是配送過程中的重要部分。配送車輛調度的優化目標是在滿足客戶需求及各種約束條件的同時，盡可能地節約成本。

由于配送受客戶位置、客戶要求、配送車輛能力等多種因素影響，導致車輛的調度問題十分復雜。如何利用有限的車輛資源盡可能高效地安排配送任務，降低成本，是物流車輛調度系統要解決的一項關鍵問題。概括來說，配送車輛調度問題是一個有約束的組合優化問題。

1959 年 Dantzig和 Ramser，提出物流配送車輛優化調度問題。物流配送車輛優化調度問題被歸結為車輛路徑問題（VRP）和多路旅行商問題（MTSP）。Dantzig是線性規劃之父，在運籌學建樹極高。物流配送車輛優化調度問題一經提出，就引起運籌學、組合數學、物流科學等多個領域專家的重視，開展了多方面的研究。多年以來，國內外對車輛路線問題之學術研究文獻眾多，也提出了相當多的求解策略與方法，包括：數學解析法、線性規劃法、分支法、模擬退火法、節約法、蟻群算法、禁忌搜索法、遺傳算法、人工神經網絡法等。國外在該領域研究的代表人物有 Bodin、Golden、Laporte、Desrochers、Altinkermer等[1]。

國內對物流配送車輛優化調度問題也展開了許多研究。在建模方面，對問題模型進行細分，融入多種約束，解決各種不同限制及優化目標的車輛優化調度問題。在算法方面，對經典的TSP、VRP問題解決方法提出優化和改進方法，并提出基于混合策略的多種算法等。

本文參照經典車輛路徑問題模型，建立了物流配送雙向車輛調度問題的數學模型，并提出了基于改進粒子群算法的物流配送車輛調度算法。

2 雙向車輛調度問題模型

物流配送車輛調度問題是安排有限的車輛按時間完成配送任務。每一車輛為具有一定需求的分布在不同地理位置的多個客戶配送貨物，在滿足客戶需求的約束條件下，找出配送成本最低的配送車輛調度方案。

例如，某配送中心有若干配送車輛，負責完成多個客戶的配送任務，這些客戶位于不同的地點，有的客戶需要收貨，有的客戶需要發貨。配送車輛設有單次配送里程上限和單次配送客戶數上限，以便控制配送人員的勞動強度。配送車輛調度的任務是科學規劃車輛行駛路線以及工作時間，生成優化的調度方案，在既定的約束條件下，使完成所有配送任務的總行駛里程最短。圖1是配送車輛調度的示意圖。

圖1 配送車輛調度的示意圖

2.1 范圍

配送車輛調度受配送中心數量、配送車輛狀況、配送任務特征、客戶要求等多種因素影響，使得調度問題十分復雜。配送車輛調度問題可歸類為一類有約束的組合優化問題。

本文從雙向車輛調度問題入手展開研究。雙向車輛調度問題具有如下約束：

(1) 一個配送中心、多個客戶，配送中心和客戶位置固定。

(2) 配送中心有多輛配送車，每車負責雙向配送，即收攬和派發。

(3) 每輛車的載重量一定，不允許超載。

(4) 每輛車每次配送設有單次配送里程上限，不允許超出。

(5) 每輛車每次配送設有單次配送客戶數上限，不允許超出。

(6) 車輛配送貨物時從配送中心出發，最后返回出發地。

(7) 客戶對配送時間無特殊要求。

可以看出，本文對現實中的物流配送調度問題進行了抽象和簡化。選擇雙向車輛調度問題作為重點研究對象主要是出于以下幾點考慮。

(1) 雙向車輛調度問題是一類典型的配送調度優化問題。

(2) 物流管理系統中涉及的配送大部分可歸類為雙向車輛調度。

(3) 通過抽象簡化問題，易于建模和求解。

2.2 模型描述

本文參照經典車輛路徑問題模型，建立雙向車輛調度問題的數學模型。

配送車輛調度問題是安排有限的車輛按時間完成配送任務。本文研究的配送車輛調度問題可以用如下的活動、資源、調度目標三要素來描述[2]。

活動指由配送中心為客戶配送貨物。配送中心數目是1，客戶數目是M，客戶位置固定，每個客戶的貨物重量為qi(i=1,2,…,M)。

資源指配送車輛。K輛配送車，各配送車的載重量為 Qk(k=1,2,…,K)，各配送車的單次配送里程上限為Dk(k=1,2,…,K)，各配送車的單次配送客戶數上限為 Ck(k=1,2,…,K)。

調度目標是求解優化的調度序列。該調度系列在滿足配送任務需要及車輛約束的情況下，實現配送里程最短。

依據上述目標建立的數學模型

其中，d0j(j=1,2,…,M)為配送中心到每個客戶的距離，dij(i,j=1,2,…,M)為客戶i到j的距離，nk為第k輛車配送服務的用戶數(nk=0代表不使用第 k輛車)。Rk為第k條行駛路線，其中rk0=0代表配送中心，rki表示在路線k中第i個訪問的客戶。

在上述模型中，各式的含義是：

式（2-1）為目標函數，要求配送總里程最短。

式（2-2）為配送要求，要求每個客戶的配送要求均需要滿足。

式（2-3）為里程約束，調度安排各車輛配送時，要求各車輛配送任務不超過單次配送里程上限。

式（2-4）為載重量約束，調度安排各車輛配送時，要求各車輛不超載。

式（2-5）為是客戶數約束，要求每條配送路線上的客戶數不超過單次配送客戶數上限，該限制的上限是客戶數目M。

式（2-6）是表示每條配送路線的安排。

式（2-7）是隱含約束，要求每個客戶僅由一臺車配送。

3 基于混合粒子群算法的物流配送車輛調度算法

粒子群優化算法是由美國的 Kennedy和Eberhart于1995年提出的。粒子群優化算法是一種基于群體智能理論的優化算法，通過模擬鳥群的覓食過程，借鑒鳥群中的協作與競爭關系，不斷演化來搜索最優解[3][4]。

本文參照標準粒子群優化算法構建了物流配送車輛調度算法的基本框架，并對標準粒子群優化算進行改進，在算法的多次迭代中引入爬山操作，增強了算法的局部搜索能力，實現了基于改進粒子群算法的物流配送車輛調度算法。

3.1 粒子群優化算法

在粒子群優化算法中，將每只小鳥抽象為一個粒子，用于表示問題的候選解。粒子的狀態包括兩個向量：位置向量和速度向量[5]。位置向量可以用式（3-1）表示，速度向量可以用式（3-2）表示。

其中，D是解空間的維數，i表示粒子的編號。

粒子群中的粒子運動模擬了鳥群的活動，并融入了個體認知和社會影響。粒子群中粒子的位置受三方面的影響而改變。

(1) 粒子以當前的位置和速度為基礎進行運動。

(2) 粒子運動受自身運動過程中的最好位置影響，即受個體認知的影響。粒子的優劣通過對粒子的位置進行適應度計算來確定。當前粒子的最好位置表示為pBest。

(3) 粒子運動受群體中所有粒子的最好位置影響，即受社會模式的影響。群體的最好位置表示為gBest。

粒子i在t+1時刻的狀態表示為：

其中，ω是慣性權重，表示粒子當前位置對下一位置的影響程度；c1、c2是加速系數，分別表示粒子受個體認知和社會模式影響的程度；r1、r2是0到1之間的隨機數。

粒子群優化算法的基本過程是首先隨機構造初始粒子群，然后根據自身的最好位置和群體的最好位置來動態地調整自己的位置，通過多次迭代來搜索最優解[6]。

3.2 粒子編碼

在本文的基于改進粒子群算法的物流配送車輛調度算法中，用實數編碼的位置向量來表示配送車輛的調度序列。

在現有的研究成果中，在解決車輛路徑問題時，解的表示方式多采用客戶與虛擬配送中心共同排列的整數表示方法。由于整數表示方法不適用于進行粒子位置和速度的計算，本文借鑒處理器任務分配的實數表示方法來表示車輛配送調度序列。Ayed Salmen在解決處理器任務分配問題時，提出了實數向量的編碼方式，用L維實數向量表示L個任務的配送車輛的調度序列[7]。

本文采用L維實數位置向量表示對L個客戶的配送車輛的調度序列。向量中的每一維實數的范圍是[0～M)，M表示車輛數。實數的整數部分，確定由哪一輛車為該客戶服務，整數部分為0時表示，由第1輛車配送，整數部分為1時表示由第2輛車配送，以此類推。某輛車對客戶的訪問順序，由實數小數部分從小到大的順序決定。以8客戶3輛配送車為例，粒子位置向量中的每一維均是0至3之間的實數。例如向量[2.418,2.873,2.615,0.158,0.002,2.211,1.896,2.716]中，第4、5維分別是 0.158、0.002，表示客戶4、5由車1配送，按從小到大順序，車1從配送中心出發，先為客戶5配送，再為客戶4配送，然后返回配送中心。如果用0表示配送中心，自然數表示客戶，則上述粒子位置向量表示的調度序列為：

車1:0->5->4->0

車2:0->7->0

車3:0->6->1->3->8->2->0

粒子的位置通過解碼過程轉化為實際的配送車輛調度調度方案。

3.3 粒子評價

在本文基于改進粒子群算法的物流配送車輛調度算法中，粒子位置用于表示問題的解，即表示調度序列。調度序列的優劣通過對粒子的位置進行適應度計算來確定。為了評價解的優劣，首先通過解碼得到該解所對應的調度序列，即配送路徑方案，然后判斷該配送路徑方案是否滿足問題的約束條件，同時計算該配送路徑方案的目標函數值，在滿足問題的各種約束條件的前提下，其目標函數值越優，則解的質量越高，配送方案越優。

在本文研究的物流配送車輛調度問題中，采用總里程作為調度序列的目標函數值，用于評判解的優劣?？偫锍绦〉恼{度序列優于總里程大的調度序列?？偫锍痰挠嬎愎綖椋?/p>

其中，dsum表示調度序列的總里程，K表示分配的車輛數，nk表示第 k 輛車配送的客戶數，d(i-1),i表示從前一出發點（客戶或配送中心）到客戶i的行使里程。對于不可行的解，即調度序列不滿足配送任務的需要或車輛的約束的情況，目標函數值取極壞值，并標志為不可用。

本算法中，目標函數值的計算過程是：

(1) 對備選解對應的調度序列進行解碼。

(2) 檢查備選解對應的調度序列中，是否滿足所有客戶的請求。如果有不滿足的情況，則適應度設置為極壞值，并標志為不可用。

(3) 根據調度序列，分配各配送車任務。

(4) 計算各配送車的任務歷程，檢查是否超過車輛的運送能力。如果有超出的情況，則目標函數值設置為極壞值，并標志為不可用。

(5) 在調度序列滿足配送任務的需要以及車輛的約束的情況，計算整個調度序列中各車任務的里程之和，作為解的目標函數值。

3.4 爬山操作

粒子群優化算法是一種簡單易用、高效實用的智能優化算法，算法的優點是收斂速度快，但是容易落入局部最優。本文在標準粒子群算法的基礎上，引入爬山操作，增加了粒子群的多樣性，提高了算法的局部搜索能力。爬山算法是一種采用鄰域搜索技術的、朝著有可能對解的質量產生改進的方向進行搜索的擇優方法。這種方法具有較強的局部搜索能力。

本算法對粒子群優化算法各次迭代生成的新粒子逐個進行爬山操作，利用爬山算法局部搜索力強的特點，提高粒子群的適應度。本文根據實數編碼的特點，采用單維突變的方式構造當前解的鄰域。對于當前粒子，隨機選取維數編號，對位置向量中選定維數的值進行隨機設置，即對粒子的位置向量進行單維突變，得到新的位置向量。然后進行適應度計算，如果新的位置向量優于原位置向量，則接受新的位置向量，否則拒絕新的位置向量。通過增加爬山操作，可有效地增加粒子的多樣性，增強局部搜索能力。

本文所采用的單維突變方法優于換位法、逆轉法和插入法。爬山算法是基于鄰域搜索的算法，在爬山算法中，通過鄰域選點來構造新解。確定鄰域選點方法是構成爬山算法的一個重要環節。解決組合優化問題通常采用的鄰域選點方法包括換位法、逆轉法和插入法。與換位法、逆轉法和插入法相比，通過本文所采用的單維突變方法進行鄰域選點，增加了車輛數目調整的可能性，擴大了鄰域搜索范圍。

3.5 算法流程

本文基于改進粒子群算法的物流配送車輛調度算法的基本流程是：

(1) 隨機構造初始粒子群，生成各粒子的初始位置和速度。

(2) 評價粒子群的所有粒子，并記錄各粒子的最好位置pBest和所有粒子的最好位置gBest。

(3) 按照式（3-3）和（3-4）更新各粒子的速度和位置。位置值越界時，設置為邊界值。

(4) 對更新后的粒子進行爬山操作。采用的單維突變方法，進行鄰域選點，得到新的位置向量。如果新的位置向量優于原位置向量，則接受新的位置向量，否則拒絕新的位置向量。

(5) 評價粒子群的所有粒子，更新每個粒子的最優位置和群體的最優位置。如果粒子位置的優于pBest，則更新pBest。如果粒子位置的優于gBest，則更新gBest。

(6) 若滿足結束條件，則輸出 gBest所為滿意解。否則轉到第3步繼續迭代。

3.6 算法分析

粒子群算法可歸類為群體智能算法，是一種隨機搜索的全局優化算法。搜素過程從問題的一個解集合開始，在搜索過程中，通過群體中粒子間的相互協作與競爭進行迭代搜索，得到優化結果。粒子群算法計算簡單，易于實現，控制參數少，實際應用中收斂速度較快。

粒子群算法屬于隨機算法，其收斂性目前沒有嚴格的數學證明，而在廣泛的實際應用中被證明是有效的。算法中慣性權重ω控制著前一速度對當前速度的影響，用于平衡算法的探索和開發能力，ω設為0.729的同時將c1和c2設為1.49445，有利于算法的收斂[8]。粒子群算法自身收斂速度較快，但是容易落入局部最優。本文基于改進粒子群算法的物流配送車輛調度算法，在標準粒子群算法的基礎上引入爬山操作，增加了粒子群的多樣性，提高了算法的局部搜索能力。

4 實驗驗證

為驗證本算法的調度能力，本文采用兩個固定的實驗樣本作為算法輸入進行解算，利用計算機模擬產生一定區域內的配送中心位置及客戶位置，并計算出配送中心與各客戶之間以及各客戶相互間的距離。實驗樣本1是3輛車8客戶的調度問題，實驗樣本2是50輛車120客戶的調度問題。實驗中設每輛車單次配送里程上限為 80km，載重量為8t，單次配送客戶數上限為30個客戶。表1列出計算機模擬生成的實驗樣本 1的客戶位置及貨物重量。在表2中列出的是實驗樣本1的配送中心與各客戶之間以及各客戶相互間的距離。

表1 實驗樣本1的模擬客戶位置

表2 實驗樣本1的配送中心與客戶間的距離

第一組實驗分別采用100次迭代的爬山算法、粒子群算法算法、改進粒子群算法、動態規劃法解決規模較小的實驗樣本1問題。實驗結果如表3所示。

第二組實驗分別采用1000次迭代的爬山算法、粒子群算法算法、改進粒子群算法、動態規劃法解決規模較大的實驗樣本2問題。實驗結果如表4所示。

實驗中，各算法運行 20次進行統計，將平均數據作為實驗結果。

表3 實驗樣本1實驗結果

表4 實驗樣本2實驗結果

從數據中可以看出，對于規模較小的實驗樣本1，改進粒子群算法生成的調度方案的最小總里程為66.4km，優于改進前的粒子群算法，但是計算結果不如爬山法和動態規劃法。動態規劃法是精確算法，計算產生了最優化結果，最小總里程為54.1km。

對于規模較大的實驗樣本 2，改進粒子群算法生成的調度方案的最小總里程為 397.5km，明顯優于爬山法和改進前的粒子群算法。由于改進粒子群算法由于相對復雜，耗時也相對較多，但計算時間屬于實際應用可接受的范圍內。動態規劃法經6小時的計算沒有生成最優化調度序列。實驗證明動態規劃法不適用于解決較大規模的物流配送車輛調度問題。

5 結束語

本文參照經典車輛路徑問題模型，考慮了車輛配送里程和用戶數等限制，建立了雙向車輛調度問題的數學模型。在標準粒子群算法的基礎上，引入爬山操作，增加了粒子群的多樣性，提高了算法的局部搜索能力，并設計了基于改進粒子群算法的物流配送車輛調度算法。

通過分析和實驗驗證，得出如下結論：本文的改進粒子群算法可以有效地解決了物流配送車輛的優化調度問題。算法能夠根據客戶位置、配送車輛能力，綜合協調，生成配送總里程優化的配送車輛調度方案。引入爬山操作增強粒子群算法的局部搜索能力，是算法改進的一項有效途徑。

[1]Gilbert Laporte.Fifty Years of Vehicle Routing.Transportation Science, 2009 , 43(4)

[2]Pinedo M.調度：原理、算法和系統(第2版).張智海,譯.北京：清華大學出版社，2007.

[3]張軍,詹志輝.計算智能.北京:清華大學出版社,2009.

[4]王凌,劉波.微粒群優化與調度算法.北京:清華大學出版社,2008.

[5]Kennedy J, Eberhart R.Particle swarm optimization[C].In Proceedings of IEEE International Conference on Neural Networks,1995：1942-1948.

[6]Clerc,M.Discrete Particle Swarm Optimization, illustrated by the Traveling Salesman Problem.New optimization technique in engineering[C].Springer- Verlag,2004.

[7]Salmen A, Ahmad I, Al-Madani S.Particle swarm optimization for task assignment problem[J].Microprocessors and Microsystems,2002,26：367-371.

[8]Y Shi, R C Eberhart.Empirical study of particle swarm optimization.In Proceedings of the Congress on Evolutionary Computation,1999:1945-1950.