基于改進粒子群算法的物流配送車輛調(diào)度

馬冬青, 王蔚

MA Dongqing1, WANG Wei2

1.華北計算技術(shù)研究所, 北京 100083

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

1.North China Institute of Computing Technology, Beijing 100083

2.TAIJI Computer Corporation Limited, Beijing 100083

1 引言

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

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

1959 年 Dantzig和 Ramser，提出物流配送車輛優(yōu)化調(diào)度問題。物流配送車輛優(yōu)化調(diào)度問題被歸結(jié)為車輛路徑問題（VRP）和多路旅行商問題（MTSP）。Dantzig是線性規(guī)劃之父，在運籌學(xué)建樹極高。物流配送車輛優(yōu)化調(diào)度問題一經(jīng)提出，就引起運籌學(xué)、組合數(shù)學(xué)、物流科學(xué)等多個領(lǐng)域?qū)＜业闹匾?，開展了多方面的研究。多年以來，國內(nèi)外對車輛路線問題之學(xué)術(shù)研究文獻眾多，也提出了相當(dāng)多的求解策略與方法，包括：數(shù)學(xué)解析法、線性規(guī)劃法、分支法、模擬退火法、節(jié)約法、蟻群算法、禁忌搜索法、遺傳算法、人工神經(jīng)網(wǎng)絡(luò)法等。國外在該領(lǐng)域研究的代表人物有 Bodin、Golden、Laporte、Desrochers、Altinkermer等[1]。

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

本文參照經(jīng)典車輛路徑問題模型，建立了物流配送雙向車輛調(diào)度問題的數(shù)學(xué)模型，并提出了基于改進粒子群算法的物流配送車輛調(diào)度算法。

2 雙向車輛調(diào)度問題模型

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

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

圖1 配送車輛調(diào)度的示意圖

2.1 范圍

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

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

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

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

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

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

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

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

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

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

(1) 雙向車輛調(diào)度問題是一類典型的配送調(diào)度優(yōu)化問題。

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

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

2.2 模型描述

本文參照經(jīng)典車輛路徑問題模型，建立雙向車輛調(diào)度問題的數(shù)學(xué)模型。

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

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

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

調(diào)度目標(biāo)是求解優(yōu)化的調(diào)度序列。該調(diào)度系列在滿足配送任務(wù)需要及車輛約束的情況下，實現(xiàn)配送里程最短。

依據(jù)上述目標(biāo)建立的數(shù)學(xué)模型

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

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

式（2-1）為目標(biāo)函數(shù)，要求配送總里程最短。

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

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

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

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

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

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

3 基于混合粒子群算法的物流配送車輛調(diào)度算法

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

本文參照標(biāo)準(zhǔn)粒子群優(yōu)化算法構(gòu)建了物流配送車輛調(diào)度算法的基本框架，并對標(biāo)準(zhǔn)粒子群優(yōu)化算進行改進，在算法的多次迭代中引入爬山操作，增強了算法的局部搜索能力，實現(xiàn)了基于改進粒子群算法的物流配送車輛調(diào)度算法。

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

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

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

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

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

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

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

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

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

粒子群優(yōu)化算法的基本過程是首先隨機構(gòu)造初始粒子群，然后根據(jù)自身的最好位置和群體的最好位置來動態(tài)地調(diào)整自己的位置，通過多次迭代來搜索最優(yōu)解[6]。

3.2 粒子編碼

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

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

本文采用L維實數(shù)位置向量表示對L個客戶的配送車輛的調(diào)度序列。向量中的每一維實數(shù)的范圍是[0～M)，M表示車輛數(shù)。實數(shù)的整數(shù)部分，確定由哪一輛車為該客戶服務(wù)，整數(shù)部分為0時表示，由第1輛車配送，整數(shù)部分為1時表示由第2輛車配送，以此類推。某輛車對客戶的訪問順序，由實數(shù)小數(shù)部分從小到大的順序決定。以8客戶3輛配送車為例，粒子位置向量中的每一維均是0至3之間的實數(shù)。例如向量[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從配送中心出發(fā)，先為客戶5配送，再為客戶4配送，然后返回配送中心。如果用0表示配送中心，自然數(shù)表示客戶，則上述粒子位置向量表示的調(diào)度序列為：

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

車2:0->7->0

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

粒子的位置通過解碼過程轉(zhuǎn)化為實際的配送車輛調(diào)度調(diào)度方案。

3.3 粒子評價

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

在本文研究的物流配送車輛調(diào)度問題中，采用總里程作為調(diào)度序列的目標(biāo)函數(shù)值，用于評判解的優(yōu)劣?？偫锍绦〉恼{(diào)度序列優(yōu)于總里程大的調(diào)度序列。總里程的計算公式為：

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

本算法中，目標(biāo)函數(shù)值的計算過程是：

(1) 對備選解對應(yīng)的調(diào)度序列進行解碼。

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

(3) 根據(jù)調(diào)度序列，分配各配送車任務(wù)。

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

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

3.4 爬山操作

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

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

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

3.5 算法流程

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

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

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

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

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

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

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

3.6 算法分析

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

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

4 實驗驗證

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

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

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

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

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

實驗中，各算法運行 20次進行統(tǒng)計，將平均數(shù)據(jù)作為實驗結(jié)果。

表3 實驗樣本1實驗結(jié)果

表4 實驗樣本2實驗結(jié)果

從數(shù)據(jù)中可以看出，對于規(guī)模較小的實驗樣本1，改進粒子群算法生成的調(diào)度方案的最小總里程為66.4km，優(yōu)于改進前的粒子群算法，但是計算結(jié)果不如爬山法和動態(tài)規(guī)劃法。動態(tài)規(guī)劃法是精確算法，計算產(chǎn)生了最優(yōu)化結(jié)果，最小總里程為54.1km。

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

5 結(jié)束語

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

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

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

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

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

[4]王凌,劉波.微粒群優(yōu)化與調(diào)度算法.北京:清華大學(xué)出版社,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.