求解需求可拆分車輛路徑問題的改進(jìn)的金字塔演化策略

李華峰，黃樟燦，張 薔，湛 航，談 慶

（武漢理工大學(xué)理學(xué)院，武漢 430073）

0 引言

車輛路徑問題（Vehicle Routing Problem，VRP）最早于1959 年由Dantzig 等［1］提出。該問題可描述為：在一個物流系統(tǒng)中，存在若干個配送中心、若干個客戶和若干輛運(yùn)輸車，假設(shè)客戶的需求量不超過車輛的最大載重量，要求設(shè)計(jì)合理的車輛行駛路線，在不違背車輛容量限制、不超出車輛最遠(yuǎn)運(yùn)輸距離等約束條件下，完成所有客戶的配送任務(wù)。但在實(shí)際配送過程中，客戶的需求量大于車輛載重量的情況會經(jīng)常發(fā)生，為了解決該問題，Dror 等［2］提出了需求可拆分的車輛路徑問題（Split Delivery VRP，SDVRP）。

SDVRP 自提出以來就受到廣泛的關(guān)注，很多學(xué)者也對該問題進(jìn)行了深入的研究。由于SDVRP 是NP（Nondeterministic Polynomial）-hard 問題［3-4］，精確算法［5-6］求解比較困難，所以主要采用聚類算法［7-8］和啟發(fā)式算法［9-12］相結(jié)合的兩階段思想對該問題進(jìn)行求解。劉旺盛等［7］分別采用了先分組后路徑和先路徑后分組兩種思想求解了該問題，從不同角度論述了兩種思想的優(yōu)越性；劉旺盛等［8］結(jié)合了K-means聚類與模擬退火算法的優(yōu)點(diǎn)，實(shí)驗(yàn)結(jié)果表明，算法效果優(yōu)于其他算法；閔嘉寧等［13］在傳統(tǒng)K-means 聚類中加入了“推出”“拉入”操作，平衡了各類的需求量，優(yōu)化了算法的性能；向婷等［14］通過設(shè)置拆分閾值對客戶進(jìn)行聚類，然后采用蟻群算法優(yōu)化各類的線路，從而提高了求解精度；姜婷［15］分析了SDVRP 解的特點(diǎn)，先求解旅行商問題，然后對其進(jìn)行切割拆分成單個路徑，最后通過刪除和最小代價(jià)插入操作采用人工蜂群算法求解該問題。

以上兩階段求解算法主要采用K-means 聚類算法，先對客戶進(jìn)行分組，然后運(yùn)用智能優(yōu)化算法優(yōu)化路徑。但是K-means聚類算法的分類結(jié)果過度依賴于分類中心的初始化，缺乏探索優(yōu)良個體的潛能，容易陷入局部最優(yōu)；同時(shí)傳統(tǒng)的智能優(yōu)化算法，如粒子群算法［16］、遺傳算法［17］、禁忌搜索算法［18］未能將優(yōu)化過程中種群間的競爭與協(xié)作統(tǒng)一起來，容易陷入局部最優(yōu)，求解精度較低。而金字塔演化策略（Pyramid Evolution Strategy，PES）［19］是一種新型啟發(fā)式算法，以金字塔結(jié)構(gòu)為基礎(chǔ)，有著明確的分工與晉升機(jī)制，其模型按種群個體優(yōu)劣進(jìn)行排序分層，對各層賦予不同的職責(zé)，將種群間和群內(nèi)個體間的競爭與協(xié)作有機(jī)地融合在一起，克服了傳統(tǒng)啟發(fā)式算法容易陷入局部最優(yōu)、未考慮種群間競爭與協(xié)作的缺點(diǎn)。因此，本文基于PES，提出了改進(jìn)的金字塔演化策略（Improved PES，IPES）。首先，分析了SDVRP 解的基本特性，對其編碼、解碼方式進(jìn)行了重新定義，保證除最后一輛車不確定滿載，其余車輛均滿載；其次，結(jié)合遺傳算法隨機(jī)、“適者生存”的高度并行、自適應(yīng)等特點(diǎn)，提出了一種自適應(yīng)算子來引導(dǎo)個體向最優(yōu)解靠攏，從而將個體間的競爭與協(xié)作聯(lián)系起來，使算法能夠收斂到最優(yōu)解；最后，通過設(shè)計(jì)層間協(xié)作策略，加強(qiáng)種群間的協(xié)作，將種群間的競爭與協(xié)作聯(lián)系起來，使得算法能夠跳出局部最優(yōu)，提高求解精度。

1 SDVRP的數(shù)學(xué)模型

本文研究的SDVRP 描述如下：一個配送中心有若干輛規(guī)格都相同的配送車輛，分別給n個客戶進(jìn)行貨物需求配送，其中配送中心的編號為0，客戶的編號分別為1至n，且配送中心和每個客戶的位置坐標(biāo)(xi，yi)、貨物需求量wi等信息都已知。通過安排合理的配送方案，使得在滿足以下幾個條件時(shí)完成配送任務(wù)的路程最短、配送車輛最少。

1）各輛配送車輛的最大載重量為W，車輛不允許超載；

2）每輛車可以服務(wù)多個客戶，每個客戶也可以由多輛車進(jìn)行服務(wù)；

3）任意兩個客戶點(diǎn)之間的距離對稱，即dij=dji，且任意三個客戶點(diǎn)之間的距離滿足dik+dkj≥dij；

4）所有服務(wù)車輛必須從配送中心出發(fā)，服務(wù)當(dāng)前客戶后即刻前往下一個客戶或者直接返回配送中心。

本文的優(yōu)化目標(biāo)是配送路徑最短、配送車輛最少，假定n個客戶點(diǎn)與配送中心0 構(gòu)成集合C={0，1，…，n}，R為完成所有n個客戶所需要的最小車輛數(shù)，建立SDVRP 的數(shù)學(xué)模型如下：

式（1）代表車輛總的配送路徑最短；式（2）代表配送過程中車輛數(shù)最少；式（3）表示流量守恒，即服務(wù)某客戶的車輛數(shù)與離開該客戶的車輛數(shù)相等；式（4）和式（5）確保每個客戶至少被訪問一次，且該客戶的需求均得到滿足；式（6）表示每條線路中被服務(wù)客戶之間的弧邊數(shù)等于被服務(wù)客戶點(diǎn)的個數(shù)減1；式（7）為每條線路客戶總的需求量不超過車輛運(yùn)載能力限制；式（8）表示當(dāng)且僅當(dāng)車輛路過客戶i時(shí)，該客戶才能得到服務(wù)；式（9）表示“滿載”，即所有配送車輛中，至多存在一輛車的載重量小于車輛最大載重量；式（10）表示各線路中每一個客戶需求量不超過該客戶的最大需求量；式（11）為決策變量，當(dāng)且僅當(dāng)=1時(shí)，表示在當(dāng)前線路r中，車輛為客戶i和j服務(wù)。

2 IPES求解SDVRP

2.1 PES

PES 是一種基于金字塔結(jié)構(gòu)的智能啟發(fā)式算法［19］。PES起初應(yīng)用于連續(xù)函數(shù)優(yōu)化問題，后來有學(xué)者將其用于求解整數(shù)規(guī)劃問題［20-21］和彩色圖像顏色量化問題［22］，并通過實(shí)驗(yàn)驗(yàn)證了該算法在求解這些問題時(shí)，能夠跳出局部最優(yōu)，具有全局尋優(yōu)能力。該算法所采用的金字塔結(jié)構(gòu)主要包含四層（見圖1），自下至上分別為：探索層、傳遞層2、傳遞層1、開采層，層層遞進(jìn)，層級間和層級內(nèi)個體相互競爭與協(xié)作，引導(dǎo)個體向最優(yōu)值靠近。PES的演化機(jī)理主要包含以下幾點(diǎn)：

1）金字塔結(jié)構(gòu)有清晰的分層機(jī)制，層級根據(jù)種群中所有個體的適應(yīng)度值按區(qū)間參數(shù)DIVIDE進(jìn)行分層，自下而上每一層級的個體數(shù)量、適應(yīng)度值、鄰域搜索范圍都逐漸減小，此操作明確了每一層級的職責(zé)，從而提高了算法的尋優(yōu)效率。

2）金字塔結(jié)構(gòu)有嚴(yán)格的分工機(jī)制，每一層各司其職，層層遞進(jìn)。探索層主要負(fù)責(zé)在全局范圍內(nèi)進(jìn)行搜索，充分探測優(yōu)良個體的潛在鄰域，然后將優(yōu)良個體按照一定的比例傳遞至上一層；傳遞層（傳遞層1和傳遞層2）作為探索層與開采層的紐帶，兼任探索與開采兩方面的任務(wù)，在接收下層傳遞上來的個體后，一方面繼續(xù)探索個體潛在的優(yōu)良區(qū)域，另一方面充分挖掘當(dāng)前個體的優(yōu)良潛能，最后通過一定比例將優(yōu)良個體傳遞至開采層；開采層主要負(fù)責(zé)充分挖掘當(dāng)前個體的優(yōu)良潛能，使之逐步靠近最優(yōu)解。

3）金字塔結(jié)構(gòu)存在明確的晉升機(jī)制，通過設(shè)置傳遞參數(shù)TF將下層部分優(yōu)秀個體傳遞至上層培養(yǎng)，繼續(xù)探索個體的優(yōu)秀潛能，從而使算法能夠跳出局部最優(yōu)，求得全局最優(yōu)解。

圖1 金字塔結(jié)構(gòu)模型Fig.1 Pyramid structure model

2.2 IPES及設(shè)計(jì)

標(biāo)準(zhǔn)的PES 最初用于求解連續(xù)函數(shù)的優(yōu)化問題，其層間協(xié)作策略可以有效地使算法跳出局部最優(yōu)，具有一定的全局尋優(yōu)能力。而遺傳算法［23］作為一種高效、實(shí)用、魯棒性強(qiáng)的優(yōu)化技術(shù)，發(fā)展極為迅速，并且被驗(yàn)證能夠有效地求解NP 問題以及多目標(biāo)優(yōu)化問題。遺傳算法的重點(diǎn)在于思考了生物在繁殖過程中可能發(fā)生基因交叉和變異，引起生物性狀的連續(xù)微弱改變，為外界環(huán)境的定向選擇提供了物質(zhì)條件和基礎(chǔ)，使生物進(jìn)化成為可能，但是遺傳算法在求解此類問題時(shí)容易陷入局部最優(yōu)［17］。因此，本文結(jié)合了PES和遺傳算法性能優(yōu)勢，首先根據(jù)SDVRP 解的基本特性，重新定義了其解碼方式，使得除最后一輛車外，其余車輛全部滿載，提高了車輛滿載率；其次，根據(jù)PES 每一層級分工機(jī)制的不同，結(jié)合遺傳算法高效、實(shí)用等特性，對每層采取不同的鄰域算子來引導(dǎo)個體向最優(yōu)解收斂，將個體的競爭與協(xié)作統(tǒng)一起來，充分發(fā)揮各層級探索與開采的潛能；最后，通過層間協(xié)作策略，將下層部分優(yōu)良個體傳遞至上層繼續(xù)進(jìn)行培養(yǎng)，將種群間的競爭與協(xié)作聯(lián)系起來，從而提高算法的全局尋優(yōu)能力。

2.2.1 IPES初始種群

本文主要采用整數(shù)編碼的方式生成初始種群個體，其中0代表配送中心，i(i=1，2，…，n)表示需配送的客戶。初始種群的生成過程具體如下：

步驟1 利用客戶直接全排列的方式來表示種群個體，Xi=(x1，x2，…，xn)(xi∈{1，2，…，n})表示初始種群中個體i的編碼。

步驟2 按式（12）隨機(jī)生成Xi(i=1，2，…，NP)，作為IPES的初始種群。

其中，randperm(n)表示1～n所有整數(shù)的隨機(jī)排列。

2.2.2 IPES計(jì)算適應(yīng)度值及分層

對種群中的個體進(jìn)行解碼，計(jì)算各個體的適應(yīng)度值，具體解碼方式如下：

步驟1 定義變量Weigh，且Weigh=0代表配送車輛從配送中心出發(fā)，初始載重量為0。

步驟2 判斷路徑中是否存在客戶k∈{1，2，…，n}的需求量wk滿足式（13），若滿足，則單獨(dú)安排一輛車為客戶k服務(wù)，并將該客戶的剩余需求量按式（14）進(jìn)行更新，直至所有的客戶k(k=1，2，…，n)的需求量wk都滿足式（15）；

步驟3 依次將Xi中客戶點(diǎn)添加到車輛的訪問用戶中直至碰到可拆分的客戶點(diǎn)i，轉(zhuǎn)下一步。

步驟4 若客戶i的需求量大于車輛的剩余需求量，則根據(jù)車輛的剩余需求量將該客戶的需求量分為由當(dāng)前車輛服務(wù)由另外一輛車服務(wù)，與此同時(shí)判斷后續(xù)客戶j是否滿足式（16），若滿足，則優(yōu)先服務(wù)j客戶：

步驟5 根據(jù)步驟4 得到的個體配送線路求解完成此次配送的車輛總路徑，得到相應(yīng)的適應(yīng)度值Objvi(i=1，2，…，NP)。

步驟6 將適應(yīng)度值按式（17）進(jìn)行排序，并根據(jù)分層比例DIVIDE將種群進(jìn)行分層。

以上解碼方式，既保證了個體線路中所使用的車輛均為最小車輛數(shù)R，又保證了除最后一輛不絕對滿載以外，其余車輛均滿載，將多級優(yōu)化目標(biāo)轉(zhuǎn)化為單優(yōu)化目標(biāo)，適應(yīng)度值objv最小，即為完成配送任務(wù)路徑的路徑最短、車輛數(shù)最少。

2.2.3 IPES自適應(yīng)鄰域算子

考慮到金字塔結(jié)構(gòu)有著明確的分工機(jī)制，自下而上層級的開采能力逐漸增強(qiáng)，探索能力逐漸減弱，因此，對不同層級的個體進(jìn)行更新時(shí)，結(jié)合遺傳算法的交叉、變異算子，分別采取了不同的策略，以便最大化地發(fā)揮各個層級的開采與探索的能力。此外，針對層內(nèi)個體交叉算子的交叉點(diǎn)個數(shù)設(shè)置了一個自適應(yīng)策略，如式（18），從而加快算法的收斂。每一層級個體的鄰域搜索策略具體如下：

其中：pc表示交叉點(diǎn)的個數(shù)；g表示當(dāng)前的迭代次數(shù)；G表示最大迭代次數(shù)。

不同層級的個體進(jìn)行更新所采取的不同策略如下：

1）探索層的鄰域算子包括交叉算子和變異算子，該層探索能力最強(qiáng)，為了避免算法陷入局部最優(yōu)，最大化地探索尋找優(yōu)良個體的潛在鄰域，將相鄰個體進(jìn)行交叉，其中交叉的起始點(diǎn)位置L_Start由式（19）確定，終點(diǎn)位置L_End由式（20）確定。

二者完成交叉操作后，對新個體進(jìn)行變異擾動，常見的變異算子有兩點(diǎn)（或多點(diǎn)）換位算子、插入算子和逆轉(zhuǎn)算子。本文主要采用逆轉(zhuǎn)算子進(jìn)行變異，具體如圖2所示。假設(shè)有5個客戶待服務(wù)，個體的服務(wù)順序?yàn)?-1-2-5-3，隨機(jī)選取兩個點(diǎn)P1 和P2，對這兩個點(diǎn)中間的片段進(jìn)行倒序排列，從而產(chǎn)生一個新個體，服務(wù)順序?yàn)?-2-1-4-3。

圖2 逆轉(zhuǎn)算子Fig.2 Reversal operator

2）相比探索層，傳遞層（傳遞層1和傳遞層2）的探索能力較弱，開采能力較強(qiáng)，該層交叉算子為采用當(dāng)代最優(yōu)個體p_best與全局最優(yōu)個體g_best分別引導(dǎo)傳遞層1、傳遞層2的個體趨于最優(yōu)解，如圖3所示。該層的變異算子同上。

3）開采層的探索能力最弱，開采能力最強(qiáng)，需充分挖掘個體的潛能。對于表現(xiàn)優(yōu)良的個體，直接保留；對于病態(tài)個體，對其進(jìn)行孵化，引導(dǎo)其向好的方向發(fā)展。采用的鄰域算子包括變異算子和孵化算子，變異算子同上，重點(diǎn)介紹孵化算子。孵化算子的孵化對象是病態(tài)個體，具體步驟如下：

步驟1 從當(dāng)前個體Xi中按式（21）的方式隨機(jī)選擇一個孵化點(diǎn)位置：

步驟2 將當(dāng)前個體Xi按式（22）進(jìn)行處理，更新Xi和待服務(wù)客戶集Q：

步驟3 依次從待服務(wù)客戶集Q中選擇離Xi中所有已安排個體最近的個體進(jìn)行插入，直至所有個體都被服務(wù)，即待服務(wù)客戶集Q為空。

圖3 交叉算子Fig.3 Crossover operator

2.2.4 IPES層間協(xié)作策略

各層級內(nèi)部個體遵從“適者生存”的原則，優(yōu)良個體被保留下來；而在層級之間，部分優(yōu)良個體通過層與層之間的協(xié)作策略晉升至更高層，在新的一層中與同層個體按照鄰域算子進(jìn)行培養(yǎng)，以獲得上升到更高層的機(jī)會，充分開發(fā)個體的潛能，從而將各層種群密切地聯(lián)系起來，加快算法的收斂。本文的層間協(xié)作策略采用根據(jù)適應(yīng)度值大小的方式按設(shè)定的參數(shù)TF晉升。

2.3 IPES步驟

IPES步驟如下：

步驟1 算法初始化，設(shè)置迭代次數(shù)g=1，最大迭代次數(shù)G，分層比例DIVIDE。

步驟2 根據(jù)本文的編碼方式隨機(jī)生成包含NP個體Xi(i=1，2，…，NP)，作為初始種群。

步驟3 對個體Xi(i=1，2，…，NP)進(jìn)行解碼，計(jì)算其適應(yīng)度值objvi(i=1，2，…，NP)。

步驟4 對個體適應(yīng)度值進(jìn)行排序，按初始參數(shù)DIVIDE進(jìn)行分層。

步驟5 按照2.2.3 節(jié)提出的自適應(yīng)鄰域算子對個體進(jìn)行更新，將優(yōu)良個體保留，淘汰病態(tài)個體。

步驟6 根據(jù)參數(shù)TF將下層優(yōu)良個體傳遞至上一層進(jìn)行培養(yǎng)。

步驟7 判斷算法終止條件是否滿足，若滿足，結(jié)束迭代過程，輸出最優(yōu)個體及最優(yōu)值；否則返回步驟3，繼續(xù)進(jìn)行下一次迭代。

3 仿真實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證IPES 在求解SDVRP 上的有效性，利用Matlab R2018b軟件進(jìn)行了仿真實(shí)驗(yàn)，實(shí)驗(yàn)環(huán)境為Windows 10操作系統(tǒng)，Inter Core i5-8250U 處理器，4 GB 內(nèi)存。實(shí)驗(yàn)初始化參數(shù)設(shè)置為：初始種群NP=400，分層比例DIVIDE=(0.5，0.25，0.15，0.1)，傳遞比例TF=(0.6，0.4，0.2)，其他參數(shù)與所對比算法的參數(shù)相同。實(shí)驗(yàn)中通過四個實(shí)驗(yàn)分別對文獻(xiàn)［7］的兩個案例、文獻(xiàn)［16］的一個案例和文獻(xiàn)［14］的一個案例進(jìn)行了仿真。

3.1 實(shí)驗(yàn)1及結(jié)果分析

實(shí)驗(yàn)1采用文獻(xiàn)［7］的案例進(jìn)行仿真，將本文的IPES與文獻(xiàn)［7］的分段求解算法、文獻(xiàn)［8］的聚類算法、文獻(xiàn)［14］的聚類算法、文獻(xiàn)［15］的人工蜂群算法、文獻(xiàn)［16］的粒子群算法的結(jié)果進(jìn)行了比較，具體見表1。算例可描述為：存在一個配送中心，需要為15 個客戶點(diǎn)進(jìn)行配送服務(wù)，車輛的最大載重量為500，其中客戶編號0 為配送中心。算法設(shè)置最大迭代次數(shù)G=100，隨機(jī)運(yùn)行10次，其迭代曲線如圖4所示。

表1 實(shí)驗(yàn)1計(jì)算結(jié)果比較Tab.1 Calculation result comparison of experiment 1

圖4 實(shí)驗(yàn)1迭代曲線Fig.4 Iteration curve of experiment 1

由表1可知，從最優(yōu)路徑看，IPES效果明顯優(yōu)于其他文獻(xiàn)的算法，相較于文獻(xiàn)［7］算法、文獻(xiàn)［8］算法，最優(yōu)路徑縮短了3.32%；相較于文獻(xiàn)［14］算法，最優(yōu)路徑縮短了0.92%；相較于文獻(xiàn)［15］算法，最優(yōu)路徑縮短了2.95%；相較于文獻(xiàn)［16］算法，最優(yōu)路徑縮短了0.95%。從使用車輛數(shù)看，各算法均可求得最優(yōu)車輛數(shù)。從平均運(yùn)行時(shí)間看，IPES 略優(yōu)于文獻(xiàn)［7］算法、文獻(xiàn)［8］算法，略差于文獻(xiàn)［14］算法、文獻(xiàn)［15］算法，但由圖4可知，算法的最佳迭代次數(shù)為39，可見該算法仍具有一定的優(yōu)越性。綜上可知，IPES在求解SDVRP時(shí)有較強(qiáng)的全局尋優(yōu)能力，求解精度較高。車輛的最優(yōu)路徑見表2，完成客戶的總配送任務(wù)最少需要10 輛車，除了最后一輛車未滿載，其余車輛均滿載。該方案中涉及到的拆分點(diǎn)為1、5、7、9、12、13、14、15。

為了更加直觀地反映該實(shí)驗(yàn)結(jié)果，圖5給出了實(shí)驗(yàn)1的最優(yōu)路徑，圖中圓點(diǎn)上面的數(shù)字表示客戶的序號，每條折線代表一輛車的行駛路徑。例如：0-3-11-10-14 表示車輛從配送中0出發(fā)，依次服務(wù)客戶3、11、10、14，最后返回配送中心。

3.2 實(shí)驗(yàn)2及結(jié)果分析

該實(shí)驗(yàn)采用文獻(xiàn)［7］的案例進(jìn)行仿真，將本文的IPES與文獻(xiàn)［7］的分段求解算法、文獻(xiàn)［8］的聚類算法、文獻(xiàn)［14］的聚類算法、文獻(xiàn)［16］的粒子群算法、文獻(xiàn)［18］的禁忌搜索算法的結(jié)果進(jìn)行了比較，具體見表3。案例可描述為：存在一個配送中心，需要為20 個客戶點(diǎn)進(jìn)行配送服務(wù)，車輛的最大載重量為5，其中客戶編號0 為配送中心。算法設(shè)置最大迭代次數(shù)G=100，隨機(jī)運(yùn)行10次，其迭代曲線如圖6所示。

表2 實(shí)驗(yàn)1最優(yōu)路徑及滿載率Tab.2 Optimal path and full load ratio of experiment 1

圖5 實(shí)驗(yàn)1最優(yōu)路徑Fig.5 Optimal path of experiment 1

表3 實(shí)驗(yàn)2計(jì)算結(jié)果比較Tab.3 Calculation result comparison of experiment 2

由表3可知，從最優(yōu)路徑長度看，IPES優(yōu)于其他文獻(xiàn)的算法，相較于文獻(xiàn)［7］算法，最優(yōu)路徑縮短了5.01%；相較于文獻(xiàn)［8］算法，最優(yōu)路徑縮短了4.48%；相較于文獻(xiàn)［14］算法，最優(yōu)路徑縮短了1.22%；相較于文獻(xiàn)［16］算法，最優(yōu)路徑縮短了0.35%；相較于文獻(xiàn)［18］算法，最優(yōu)路徑縮短了8.53%。從使用車輛數(shù)來看，各算法車輛數(shù)均能達(dá)到最優(yōu)。由圖6 可知，IPES 的最佳迭代步數(shù)為73，而文獻(xiàn)［7］算法的最佳迭代步數(shù)為537。綜合可知，IPES 相較于其他算法，具有一定的有效性和很強(qiáng)的收斂能力。車輛的最優(yōu)路徑見表4，客戶的總需求量為40，8輛車的總載重也為40，剛好滿載。該方案中涉及到的拆分點(diǎn)為1、18。

圖7為實(shí)驗(yàn)2的最優(yōu)路徑，圖中圓點(diǎn)上面的序號表示客戶的序號，每條折線代表一輛車的行駛路徑。例如：0-15-16-19表示車輛從配送中0出發(fā)，依次服務(wù)客戶15、16、19，最后返回配送中心。

圖6 實(shí)驗(yàn)2迭代曲線Fig.6 Iteration curve of experiment 2

表4 實(shí)驗(yàn)2最優(yōu)路徑及滿載率Tab.4 Optimal path and full load ratio of experiment 2

圖7 實(shí)驗(yàn)2最優(yōu)路徑Fig.7 Optimal path of experiment 2

3.3 實(shí)驗(yàn)3及結(jié)果分析

實(shí)驗(yàn)采用文獻(xiàn)［16］的案例進(jìn)行仿真，將本文的IPES 與文獻(xiàn)［16］的粒子群算法的結(jié)果進(jìn)行了比較。案例可描述為：存在一個配送中心，需要為35 個客戶點(diǎn)進(jìn)行配送服務(wù)，車輛的最大載重量為8。算法設(shè)置最大迭代次數(shù)G=800，隨機(jī)運(yùn)行10次，結(jié)果如表5所示。

表5 實(shí)驗(yàn)3計(jì)算結(jié)果比較Tab.5 Calculation result comparison of experiment 3

由表5可知，IPES結(jié)果明顯優(yōu)于文獻(xiàn)［16］的粒子群算法，相較于粒子群算法，IPES 的平均路徑減少了3.04%，最優(yōu)路徑減少了3.07%。由平均車輛數(shù)為7 可知，算法每次迭代都可以收斂到最優(yōu)車輛，具有一定的穩(wěn)定性。因此，IPES 在求解SDVRP 時(shí)，有一定的有效性、收斂性和穩(wěn)定性，且求解精度相較于粒子群算法較高。IPES 的最優(yōu)路徑見表6，完成客戶的總配送任務(wù)最少需要7 輛車，除了最后一輛車未滿載，其余車輛均滿載。該方案中涉及到的拆分點(diǎn)為1、5、10、18、33。

表6 實(shí)驗(yàn)3最優(yōu)路徑及滿載率Tab.6 Optimal path and full load ratio of experiment 3

圖8為實(shí)驗(yàn)3的最優(yōu)路徑，圖中圓點(diǎn)上面的序號表示客戶的序號，每條折線代表一輛車的行駛路徑。例如：0-18-28 表示車輛從配送中0 出發(fā)，依次服務(wù)客戶18、28，最后返回配送中心。

圖8 實(shí)驗(yàn)3最優(yōu)路徑Fig.8 Optimal path of experiment 3

3.4 實(shí)驗(yàn)4及結(jié)果分析

該實(shí)驗(yàn)采用文獻(xiàn)［14］的案例進(jìn)行仿真，將IPES 與文獻(xiàn)［14］算法、文獻(xiàn)［24］算法的結(jié)果進(jìn)行了比較。案例可描述為：存在一個配送中心，需要為36 個客戶點(diǎn)進(jìn)行配送服務(wù)，車輛的最大載重量為1。算法設(shè)置最大迭代次數(shù)G=800，隨機(jī)運(yùn)行10次，計(jì)算結(jié)果具體見表7。

表7 實(shí)驗(yàn)4計(jì)算結(jié)果Tab.7 Calculation results of experiment 4

由實(shí)驗(yàn)結(jié)果可見，隨機(jī)運(yùn)行10 次，IPES 的平均路徑長度為308.78，最優(yōu)路徑為305.10，最差路徑為312.25。文獻(xiàn)［14］算法的最優(yōu)路徑為336.74，文獻(xiàn)［24］算法的最優(yōu)路徑為354.70，可知，本文算法的最差路徑優(yōu)于文獻(xiàn)［14］算法、文獻(xiàn)［24］算法的最優(yōu)路徑。且相較于文獻(xiàn)［14］的聚類算法，IPES的最優(yōu)路徑縮短了9.40%；相較于文獻(xiàn)［24］的禁忌搜索算法，IPES 的最優(yōu)路徑縮短了13.98%。此外，每次所需要的車輛數(shù)都為16，均達(dá)到最優(yōu)，由此可知，IPES 解決該問題時(shí)具有一定的收斂性、穩(wěn)定性和很強(qiáng)的全局尋優(yōu)能力。IPES 的最優(yōu)路徑見表8，完成客戶的總配送任務(wù)最少需要16輛車，除最后一輛車未滿載，其余車輛均滿載。該方案中涉及到的拆分點(diǎn)為2、3、5、7、10、17、18、21、22、25、32、33、35。

圖9為實(shí)驗(yàn)4的最優(yōu)路徑，圖中圓點(diǎn)上面的序號表示客戶的序號，每條折線代表一輛車的行駛路徑。例如：0-20-29-17-3 表示車輛從配送中0 出發(fā)，依次服務(wù)客戶20、29、17、3，最后返回配送中心。

圖9 實(shí)驗(yàn)4最優(yōu)路徑Fig.9 Optimal path of experiment 4

4 結(jié)語

本文提出了一種改進(jìn)的金字塔演化策略（IPES），以配送路徑最短、配送車輛最少為優(yōu)化目標(biāo)，建立了數(shù)學(xué)模型，介紹了IPES 求解SDVRP 的編碼方式、適應(yīng)度值計(jì)算過程、每一層級的自適應(yīng)鄰域算子以及層間傳遞策略，極大提高了車輛滿載率，克服了傳統(tǒng)兩階段的求解算法容易陷入局部最優(yōu)，以及傳統(tǒng)優(yōu)化算法在求解時(shí)只有個體間競爭與協(xié)作無種群間競爭與協(xié)作的缺陷。通過仿真實(shí)驗(yàn)表明，IPES 在求解四個案例時(shí)，相較于其他對比算法的最優(yōu)精度分別至少提升了0.92%、0.35%、3.07%、9.40%，驗(yàn)證了IPES 求解SDVRP 的可行性和有效性，為研究車輛路徑等組合優(yōu)化問題提供了一種新的啟發(fā)式方法。在接下來的工作中，將對算法的鄰域更新策略、層間協(xié)作策略繼續(xù)進(jìn)行改進(jìn)，探索算法在求解大規(guī)模SDVRP 上的可行性、收斂性、穩(wěn)定性，使PES 能夠完全應(yīng)用于離散問題的求解，拓展算法的應(yīng)用領(lǐng)域。