帶軟時(shí)間窗的冷鏈電動(dòng)汽車路徑問題研究

劉志碩，李秋雨，董子琦，陳 哲

（北京交通大學(xué)交通運(yùn)輸學(xué)院，北京 100044）

在食品生鮮配送領(lǐng)域，傳統(tǒng)的冷鏈配送通常采用燃油汽車，但是燃油燃燒產(chǎn)生的二氧化碳和不完全燃燒產(chǎn)生的有害氣體會加重環(huán)境的負(fù)擔(dān)，生鮮產(chǎn)品的制冷運(yùn)輸也會消耗更多能源.與燃油車相比，電動(dòng)車以電能為動(dòng)力源，使用過程零排放，對環(huán)境和社會資源更加友好.有關(guān)研究表明，相比燃油車，采用電動(dòng)車進(jìn)行物流配送能夠有效降低能源消耗和運(yùn)營成本［1-2］.因此，將電動(dòng)車應(yīng)用于冷鏈物流配送領(lǐng)域是未來的發(fā)展趨勢.目前我國已有一些物流企業(yè)開始嘗試將電動(dòng)冷藏車投入到冷鏈配送環(huán)節(jié)，但電動(dòng)冷藏車的應(yīng)用仍然存在一些問題.電動(dòng)冷藏車一般采用磷酸鐵鋰動(dòng)力電池，雖然其比三元電池成本更低且更加安全，但存在能量密度低、續(xù)駛里程短、充電時(shí)間長等問題［3］.冷鏈物流配送過程中電動(dòng)車需要制冷，因此需要消耗更多電能，而大部分城市仍存在社會充電樁密度小、覆蓋不全面等問題.因此，如何利用現(xiàn)有資源合理規(guī)劃路徑，在提高配送效率的同時(shí)降低配送成本顯得尤為重要.

針對冷鏈物流配送優(yōu)化問題，國內(nèi)外學(xué)者從冷鏈物流中多目標(biāo)、動(dòng)態(tài)需求、多溫共配等角度研究了車輛路徑問題［4-7］.Osvald 等［5］考慮到新鮮蔬菜易變質(zhì)的特點(diǎn)，研究了在時(shí)間窗和行程時(shí)間約束下的冷鏈物流車輛路徑問題.Chen 等［6］考慮了冷鏈產(chǎn)品配送中客戶需求的不確定性，提出了帶有生產(chǎn)調(diào)度的車輛路徑問題.Tsang 等［7］提出了一種基于多溫區(qū)共同配送的路徑規(guī)劃系統(tǒng)，該方案可降低食品變質(zhì)率，縮短交付時(shí)間，同時(shí)提高客戶滿意度.

針對電動(dòng)汽車路徑優(yōu)化問題，國內(nèi)外學(xué)者主要研究了里程約束、充電方式、充電策略等問題，并開發(fā)了相關(guān)的高效智能算法［8-11］.Goeke 等［9］提出了傳統(tǒng)汽車和電動(dòng)汽車的混合車隊(duì)下帶時(shí)間窗的路徑優(yōu)化問題.Keskin 等［10］在研究電動(dòng)汽車路徑優(yōu)化問題時(shí)放寬了完全充電的限制，提出了部分充電的策略.Verma 等［11］通過結(jié)合充電站充電和交換站更換電池兩種方式來提高客戶交付的準(zhǔn)時(shí)率.

然而，目前鮮有針對電動(dòng)車進(jìn)行冷鏈物流配送路徑問題的優(yōu)化研究.主要原因可能是電動(dòng)車在物流領(lǐng)域的應(yīng)用尚處于起步階段，社會充電樁等基礎(chǔ)設(shè)施的建設(shè)還有待完善.但是隨著電動(dòng)汽車不斷發(fā)展和其應(yīng)用范圍的不斷擴(kuò)大，電動(dòng)車?yán)滏溛锪髋渌吐窂絻?yōu)化將是一個(gè)非常值得研究的問題.因此，本文提出一種帶軟時(shí)間窗的冷鏈電動(dòng)汽車路徑問題（Cold-Chain Electric Vehicle Routing Problem with Soft Time Windows，CEVRPTW），構(gòu)建以配送總成本最低為優(yōu)化目標(biāo)的數(shù)學(xué)模型，設(shè)計(jì)自適應(yīng)大鄰域搜索算法并進(jìn)行求解.

1 模型建立

1.1 問題描述及基本假設(shè)

一個(gè)生鮮配送中心派出同質(zhì)的電動(dòng)車，向多個(gè)客戶配送同一溫區(qū)的生鮮商品，配送中心只在固定時(shí)間段內(nèi)運(yùn)營，車輛只能在該時(shí)段內(nèi)出發(fā)或者返回.客戶有軟時(shí)間窗要求，即給客戶配送商品，允許車輛早到或晚到，但會產(chǎn)生相應(yīng)的等待成本或延誤成本.車輛容量固定，續(xù)駛里程有限，中途可能需要在社會公共充電站充電，充電方式為快充.要求制定最優(yōu)的配送方案，使配送總成本最低.

基本假設(shè)如下：

1）一個(gè)配送中心，運(yùn)營時(shí)段固定，所有車輛出發(fā)前在配送中心充滿電，中途可多次充電，且每次充滿；

2）每輛車只允許配送一次且訪問同一個(gè)充電站最多一次；

3）各客戶有軟時(shí)間窗，需求量已知，且不超過車輛最大容量；

4）每個(gè)客戶只允許由一輛車配送一次；

5）溫區(qū)、車型單一，充電速度恒定；

6）為提供車輛動(dòng)力所消耗的電能與里程成正比；

7）制冷所消耗的電能與制冷的時(shí)間成正比.

1.2 模型變量

為解決CEVRPTW 問題，建立了一系列模型參數(shù)與決策變量，其設(shè)置及具體含義分別見表1 與表2.

表2 模型決策變量Tab.2 Decision variables of model

1.3 目標(biāo)函數(shù)

CEVRPTW 問題以配送總成本最小為目標(biāo)，它由固定成本和可變成本構(gòu)成，其中可變成本包含運(yùn)輸成本、制冷成本、等待成本和延誤成本.

1）固定成本包括車輛購置、支付員工工資等，被分配到每輛配送車輛上，計(jì)算式為

2）運(yùn)輸成本為車輛行駛過程中為提供車輛動(dòng)力所消耗的電能成本，計(jì)算式為

3）制冷成本包括電動(dòng)車通過制冷裝備在行駛途中(不包括車輛完成配送任務(wù)回到配送中心的這段路程)、卸貨期間和充電期間消耗的電能，計(jì)算式為

4）等待成本是車輛在客戶最早接受服務(wù)時(shí)間之前到達(dá)目的地所產(chǎn)生的，它通過該時(shí)間段的制冷成本來衡量，計(jì)算式為

5）車輛在客戶要求的最晚配貨時(shí)間之后到達(dá)，則產(chǎn)生延誤成本，計(jì)算式為

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

目標(biāo)函數(shù)：

約束條件：

式（7）表示車輛給客戶配送后必須離開；式（8）表示車輛從配送中心出發(fā)，最后再返回配送中心；式（9）表示每個(gè)客戶只允許訪問一次；式（10）表示車輛容量約束；式（11）表示每輛車在配送過程中允許多次充電；式（12）表示車輛的行駛時(shí)間；式（13）表示給客戶的服務(wù)時(shí)間，即卸貨時(shí)間；式（14）表示車輛在充電站的充電量；式（15）表示車輛在充電站的充電時(shí)間；式（16）表示車輛在節(jié)點(diǎn)的等待時(shí)間；式（17）表示車輛在節(jié)點(diǎn)的延誤時(shí)間；式（18）表示車輛在節(jié)點(diǎn)開始接受服務(wù)的時(shí)刻；式（19）表示車輛到達(dá)任意節(jié)點(diǎn)的時(shí)刻；式（20）表示車輛到達(dá)任意節(jié)點(diǎn)的裝載量為非負(fù)值；式（21）表示車輛在開始配送任務(wù)之前的裝載量不超過車輛的最大容量；式（22）表示客戶i與其他節(jié)點(diǎn)j的時(shí)間關(guān)系；式（23）表示充電站i與其他節(jié)點(diǎn)j的時(shí)間關(guān)系；式（24）表示客戶或充電站與配送中心的時(shí)間關(guān)系；式（25）表示客戶及配送中心滿足的時(shí)間窗要求；式（26）～式（28）表示車輛從某個(gè)節(jié)點(diǎn)出發(fā)并訪問客戶后有足夠電量到達(dá)其他節(jié)點(diǎn)；式（29）表示車輛在充電站充完電后有足夠電量回到配送中心；式（30）表示兩個(gè)變量之間的關(guān)系；式（31）表示決策變量取值范圍.

2 求解算法

上述模型是一個(gè)0-1 整數(shù)規(guī)劃模型，屬于車輛路徑問題（Vehicle Routing Problem，VRP）的范疇.VRP 問題是一個(gè)典型的NP-Hard 難題，當(dāng)節(jié)點(diǎn)規(guī)模很小時(shí)，可以采用數(shù)學(xué)規(guī)劃方法求得精確解.但隨著節(jié)點(diǎn)規(guī)模增加，解空間呈指數(shù)級增長，采用數(shù)學(xué)規(guī)劃方法無法求解，因此，一般采用啟發(fā)式方法或元啟發(fā) 式 方 法 求 解.Elshaer 等［12］對 求解VRP 問 題 的 元啟發(fā)式算法進(jìn)行了統(tǒng)計(jì)分析，結(jié)果顯示，最受學(xué)者青睞的算法有禁忌搜索算法、自適應(yīng)大規(guī)模鄰域搜索算法（Adaptive Large Neighborhood Search，ALNS）和蟻群算法等.因此，本文中針對CEVRPTW 問題特點(diǎn)設(shè)計(jì)了ALNS 算法求解.

2.1 ALNS 算法

ALNS 算法是大鄰域搜索算法的延伸［13］，可用于解決各種車輛路徑問題.它使用多種破壞和修復(fù)算子，每次迭代時(shí)采用隨機(jī)方式來選擇要執(zhí)行的算子，而選擇概率由該算子之前的表現(xiàn)來決定，歷史表現(xiàn)越好，被選中的概率越高.

本 文 在Shaw 等人［13-15］對ALNS 算法研 究的基礎(chǔ)上，增加了針對CEVRPTW 問題的相關(guān)移除算子和插入算子.算法總體思路是首先構(gòu)造初始解，然后嘗試采用不同鄰域算子對其進(jìn)行改進(jìn)，不斷迭代，直到滿足算法終止條件.在每次迭代中，先隨機(jī)選擇某個(gè)移除算子從線路中移除一些節(jié)點(diǎn)（客戶、充電站），以破壞當(dāng)前解，然后選擇插入算子來修復(fù)該解.插入算子嘗試性地將移除的客戶或充電站節(jié)點(diǎn)再插回到線路中，以獲得比之前更好的解.

2.2 構(gòu)造初始解

采用貪婪插入法構(gòu)造初始解，步驟如下：

1）初始化一條新線路，不含任何客戶節(jié)點(diǎn)和充電站節(jié)點(diǎn).

2）從當(dāng)前所有未插入到線路的客戶節(jié)點(diǎn)中選取地理位置上離配送中心最遠(yuǎn)的客戶節(jié)點(diǎn)，作為第一個(gè)節(jié)點(diǎn)插入到新線路中.

3）判斷當(dāng)前是否還有未插入的客戶節(jié)點(diǎn)，如果仍有未插入到線路中的客戶節(jié)點(diǎn)，轉(zhuǎn)4）；否則算法終止.

4）判斷當(dāng)前所有未插入到線路的客戶節(jié)點(diǎn)中，是否存在滿足插入到當(dāng)前線路條件的客戶節(jié)點(diǎn).若存在，則從這些客戶節(jié)點(diǎn)中選擇一個(gè)使線路成本增加最少的節(jié)點(diǎn)插入到當(dāng)前線路，并跳轉(zhuǎn)到3）；否則轉(zhuǎn)1）.

關(guān)于判斷節(jié)點(diǎn)是否滿足插入條件，具體指的是要滿足車輛容量約束以及配送中心的硬時(shí)間窗約束.如果客戶節(jié)點(diǎn)滿足以上兩個(gè)條件，卻因電池電量低無法插入，則可以同時(shí)插入客戶節(jié)點(diǎn)和一個(gè)充電站節(jié)點(diǎn).節(jié)點(diǎn)插入到線路的成本，指的是分別計(jì)算該節(jié)點(diǎn)插入到當(dāng)前線路所有各個(gè)位置時(shí)的成本，以最小成本所在的位置作為該節(jié)點(diǎn)的插入位置.

2.3 移除算子

2.3.1 客戶節(jié)點(diǎn)移除

本文中采用Shaw、Avci 和Masson 等設(shè)計(jì)的隨機(jī)移除、相關(guān)移除、最差成本移除、最差時(shí)間移除、區(qū)域 移 除 和 隨 機(jī) 回 路 移 除 算 子［13-15］. 此 外，針 對CEVRPTW 問題中的軟時(shí)間窗約束設(shè)計(jì)了最長延誤客戶節(jié)點(diǎn)移除算子.

1）隨機(jī)移除（CRR）：從當(dāng)前解中隨機(jī)移除若干客戶節(jié)點(diǎn).

2）相關(guān)移除（CSRR）：根據(jù)客戶節(jié)點(diǎn)之間的相似度進(jìn)行移除，客戶節(jié)點(diǎn)i和j的相似度R(i，j)根據(jù)時(shí)間窗要求、距離和需求量計(jì)算，權(quán)重分別用α、β、γ來表示，計(jì)算式為

式中：di0和dj0分別表示客戶節(jié)點(diǎn)i和j距離配送中心的距離；ei和ej分別表示客戶節(jié)點(diǎn)i和j的最早服務(wù)時(shí)間；li和lj分別表示客戶節(jié)點(diǎn)i和j的最晚服務(wù)時(shí)間；qi和qj分別表示客戶節(jié)點(diǎn)i和j的需求量.R(i，j)越小，客戶節(jié)點(diǎn)i和j的相似度越高.

3）最差成本移除（CWCR）：移除使當(dāng)前解增加成本最多的若干客戶節(jié)點(diǎn)，即若移除這些節(jié)點(diǎn)，能夠使當(dāng)前解的成本降低幅度最大.

4）最差時(shí)間移除（CWTR）：本文中考慮了客戶節(jié)點(diǎn)的軟時(shí)間窗要求，時(shí)間代價(jià)是指車輛服務(wù)該客戶節(jié)點(diǎn)的等待或延誤所造成的成本.因此移除等待或延誤時(shí)間最長的客戶節(jié)點(diǎn).

5）區(qū)域移除（CZR）：節(jié)點(diǎn)所在的笛卡爾坐標(biāo)系被劃分為許多較小區(qū)域.隨機(jī)選擇一個(gè)區(qū)域，將該區(qū)域中所有客戶節(jié)點(diǎn)從當(dāng)前解中移除.

6）隨機(jī)回路移除（CRRR）：隨機(jī)選擇若干條回路并刪除回路中所有客戶節(jié)點(diǎn).回路數(shù)量的取值范圍為當(dāng)前解回路總數(shù)的10%～12%之間.

7）最大延誤客戶節(jié)點(diǎn)移除（CBLR）：客戶節(jié)點(diǎn)有軟時(shí)間窗要求，晚到會產(chǎn)生相應(yīng)的延誤成本，且這部分成本較高，因此將延誤時(shí)間最長的客戶節(jié)點(diǎn)移除.

由于CEVRPTW 問題針對的是電動(dòng)車，行駛過程中必須考慮電動(dòng)車電量，所以在移除客戶節(jié)點(diǎn)后，一些充電可能不再需要.因此在客戶節(jié)點(diǎn)移除過程中，存在客戶和充電站節(jié)點(diǎn)關(guān)聯(lián)移除.即如果某個(gè)客戶節(jié)點(diǎn)被移除，恰好訪問該客戶節(jié)點(diǎn)的電動(dòng)車是從充電站節(jié)點(diǎn)再過來的，則同時(shí)移除該客戶節(jié)點(diǎn)和充電站節(jié)點(diǎn)，另一種情況是恰好訪問完某個(gè)客戶節(jié)點(diǎn)后需要去下一個(gè)充電站節(jié)點(diǎn)充電，如果該客戶節(jié)點(diǎn)被移除，那么接下來要訪問的充電站節(jié)點(diǎn)也被移除.

2.3.2 充電站節(jié)點(diǎn)移除

充電站節(jié)點(diǎn)是EVRP 問題的獨(dú)特之處，既要滿足電動(dòng)車行駛過程中的電量要求，又要避免多余的充電時(shí)間.因此考慮充電站節(jié)點(diǎn)的移除也可以在一定程度上優(yōu)化初始解.

1）隨機(jī)充電站節(jié)點(diǎn)移除（SRR）：與客戶節(jié)點(diǎn)隨機(jī)移除機(jī)制類似.

2）最差充電站節(jié)點(diǎn)使用移除（SWR）：移除線路中電動(dòng)車充電量最少的充電站節(jié)點(diǎn).該算子的目的是在需要充電之前盡可能多地利用電動(dòng)車電池，提高充電站效率.

2.4 插入算子

2.4.1 客戶節(jié)點(diǎn)插入

客戶節(jié)點(diǎn)插入算子包括隨機(jī)插入、貪婪插入、后悔插入算子［13-15］.

1）隨機(jī)插入（CI）：在滿足初始解生成過程中插入條件的前提下隨機(jī)插入.

2）貪婪插入（CGI）：參照初始解生成的算法.

3）后悔插入（CRI）：用xik表示第k極插入成本的路徑，當(dāng)k≤k′時(shí)(k′∈K)，滿足Δzxik≤Δzxik′，用后悔值ci=Δzxi2≤Δzxi1表示把花費(fèi)成本最高客戶節(jié)點(diǎn)i插入當(dāng)前最優(yōu)路徑和次優(yōu)路徑之間的成本差值.插入最佳位置為在滿足插入條件的前提下對應(yīng)成本最小.

2.4.2 充電站節(jié)點(diǎn)插入

在移除充電站節(jié)點(diǎn)后，某些線路會因電動(dòng)車電量不足而導(dǎo)致不可行，因而需要在合適的位置插入充電站節(jié)點(diǎn)，充電站節(jié)點(diǎn)插入如下：

1）最佳充電站節(jié)點(diǎn)插入（SBI）：若車輛到達(dá)客戶節(jié)點(diǎn)的電池電量為負(fù)，則在該客戶節(jié)點(diǎn)和前一個(gè)客戶節(jié)點(diǎn)之間的弧上插入“最佳”（增加距離最?。┏潆娬竟?jié)點(diǎn)，如果此插入不可行，則以相同方式嘗試之前的弧.

2）比較插入（SCI）：由于在選擇充電站節(jié)點(diǎn)時(shí)遵循就近原則，可能會導(dǎo)致充電完成后，訪問下一個(gè)客戶節(jié)點(diǎn)時(shí)行駛更遠(yuǎn)的距離，花費(fèi)更多的成本，因此，在一條回路內(nèi)部，可以考慮讓車輛提前充電.若提前充電成本較之前有所降低且電量能夠支持訪問回路里的剩余節(jié)點(diǎn)回到配送中心，則插入新的充電站節(jié)點(diǎn).具體插入示意圖見圖1.

圖1 比較插入算子示意圖Fig.1 Schematic diagram of comparison insertion operator

ALNS 算法偽代碼如下：

3 算例分析

針對CEVRPTW 問題的特點(diǎn)，對Goeke 構(gòu)建的算例進(jìn)行改造［9］，制作出CEVRPSTW 問題的算例集，以驗(yàn)證ALNS 算法的有效性.Goeke 的算例改編自Solomon 基準(zhǔn)算例集［16］.所設(shè)計(jì)的算例集按節(jié)點(diǎn)數(shù)目分為大規(guī)模和小規(guī)模兩個(gè)子集.其中，小規(guī)模算例有15 個(gè)，包含5、10 和15 個(gè)客戶節(jié)點(diǎn)的算例各5 個(gè)；大規(guī)模算例有30 個(gè)，每個(gè)算例包含100 個(gè)客戶節(jié)點(diǎn)、20 個(gè)充電站節(jié)點(diǎn).采用Dev-C++編程實(shí)現(xiàn)本文中所設(shè)計(jì)的ALNS 算法，測試環(huán)境為CPU：3.4 GHz、內(nèi)存：16 G.

3.1 調(diào)參試驗(yàn)

本文中的模型和算法涉及很多參數(shù)，包括CEVRPTW 問題自身的參數(shù)和算法的參數(shù).對于問題自身的參數(shù)，一部分參考相關(guān)文獻(xiàn)來設(shè)置，如車輛的固定成本、單位耗電成本等；一部分由筆者根據(jù)現(xiàn)實(shí)情況酌情設(shè)置，表示為⊙.對于算法的參數(shù)，一部分參考相關(guān)文獻(xiàn)來設(shè)置，比如時(shí)間窗要求權(quán)重、距離權(quán)重和需求量權(quán)重、模擬退火的初始溫度等，其來源直接標(biāo)記為參考文獻(xiàn)；一部分通過試驗(yàn)來優(yōu)化設(shè)置，如ALNS 算法的迭代次數(shù)、因子得分增量等，其來源表示為⊕，其余由筆者自行設(shè)置，表示為⊙，具體如表3 所示.

表3 參數(shù)設(shè)置Tab.3 Parameter setting

對于上表中通過試驗(yàn)來優(yōu)化設(shè)置的參數(shù)，選取小算例進(jìn)行調(diào)參試驗(yàn)，設(shè)計(jì)如下：5、10 和15 個(gè)客戶節(jié)點(diǎn)的算例各5 個(gè).針對15 個(gè)算例分別進(jìn)行ALNS算法迭代次數(shù)的參數(shù)試驗(yàn)、因子得分增量參數(shù)試驗(yàn)，得到最佳的參數(shù)配置，以便于后續(xù)的試驗(yàn).

3.1.1 ALNS 算法迭代次數(shù)參數(shù)試驗(yàn)

本節(jié)對ALNS 算法的迭代次數(shù)進(jìn)行試驗(yàn).迭代次數(shù)分別為100 次、200 次和300 次.試驗(yàn)結(jié)果如表4所示，f表示運(yùn)行10 次程序后得到的最優(yōu)值，t表示求解的時(shí)長.

從表4 可以看出，ALNS 算法的迭代次數(shù)為200 次時(shí)最佳，僅迭代100 次無法找到最優(yōu)解，迭代300 次花費(fèi)時(shí)間太長.

表4 ALNS 算法參數(shù)試驗(yàn)結(jié)果Tab.4 Experimental results of ALNS algorithm parameter

3.1.2 因子得分增量參數(shù)試驗(yàn)

本節(jié)針對因子得分增量參數(shù)進(jìn)行試驗(yàn)，通過試驗(yàn)效果對因子得分增量(θ1，θ2，θ3)進(jìn)行調(diào)整控制.理論上來講，算子的性能越好，越有可能搜索到更好的解，越有可能出現(xiàn)“優(yōu)化后的解優(yōu)于全局最優(yōu)解”“優(yōu)化后的解優(yōu)于當(dāng)前解，劣于全局最優(yōu)解”這兩種情形，該算子的得分就應(yīng)該越高，越容易在下一次調(diào)用時(shí)被選中.也就是說，θ1＞θ2＞θ3才是最合適的參數(shù)方案.

為了驗(yàn)證這一假想，(θ1，θ2，θ3)共選擇（40，30，20）、（40，20，30）、（30，20，40）、（30，40，20）、（20，30，40）、（20，40，30）共6 種參數(shù)組合方案進(jìn)行試驗(yàn)，試驗(yàn)結(jié)果如表5 所示.

從表5 可以看出，各參數(shù)組合結(jié)果相差不大，其中（30，40，20）表現(xiàn)最好，（40，30，20）次之，（20，30，40）效果最差.

表5 因子得分增量參數(shù)試驗(yàn)結(jié)果Tab.5 Experimental results of increment factor parameter

試驗(yàn)結(jié)果并未完全支持θ1＞θ2＞θ3這一假想.比較θ2與θ3，方案（40，30，20）對于“優(yōu)化后的解優(yōu)于當(dāng)前解，劣于全局最優(yōu)解”給30 分，而對于“優(yōu)化后的解劣于當(dāng)前解，但被接受”給20 分.然而，該參數(shù)方案的平均最優(yōu)值僅為488.79，優(yōu)于方案（40，20，30）的491.89，即θ2＞θ3的 方案要優(yōu)于θ2＜θ3的方案.另外兩組對比（30，40，20）vs（30，20，40），（20，40，30）vs（20，30，40），均得出了類似結(jié)論.顯然，3 組對比均支持θ2＞θ3這一假想.

從θ1與θ2相比較來看，方案（40，30，20）對于“優(yōu)化后的解優(yōu)于全局最優(yōu)解”給40 分，而對于“優(yōu)化后的解優(yōu)于當(dāng)前解，劣于全局最優(yōu)解”給30 分.然而，該方案的平均最優(yōu)解高于方案（30，40，20），即θ1＞θ2的方案要劣于θ1＜θ2的方案.而另外兩組對比（30，20，40）vs（20，30，40），（40，20，30）vs（20，40，30），卻支持θ1＞θ2的方案.

因此，僅從試驗(yàn)結(jié)果來看，θ1＞θ2＞θ3這一假想不一定合理.由于在所有方案中，方案（30，40，20）的優(yōu)化效果最好，因此本文后續(xù)試驗(yàn)均采用（30，40，20）的參數(shù)組合.

3.2 小規(guī)模算例試驗(yàn)結(jié)果與分析

為驗(yàn)證所建數(shù)學(xué)模型的正確性和ALNS 算法的性能，使用CPLEX 和ALNS 算法對小規(guī)模算例進(jìn)行求解，其中ALNS 算法對每個(gè)算例執(zhí)行10 次，取最優(yōu)結(jié)果.試驗(yàn)結(jié)果如表6 所示，gap 表示ALNS所求得的解與CPLEX 解的偏差.

從表6 中可以看出，針對所有算例，ALNS 均能找到CPLEX 的精確解，且花費(fèi)的時(shí)間遠(yuǎn)小于CPLEX.其中15 個(gè)客戶節(jié)點(diǎn)的最優(yōu)解對應(yīng)的配送路線為1-3-13-6-19-10-9-16-5-2-1，1-4-17-11-14-1，1-8-7-18-15-12-1（節(jié) 點(diǎn)1 表 示 車 廠，節(jié) 點(diǎn)17-21表示充電站，其余為客戶節(jié)點(diǎn)），如圖2 所示.

圖2 15 個(gè)客戶節(jié)點(diǎn)的最優(yōu)解對應(yīng)的配送路線圖Fig.2 Distribution route map corresponding to the optimal solution of 15 customer nodes

表6 小規(guī)模算例實(shí)驗(yàn)結(jié)果Tab.6 Small-scale experimental results of algorithm example

3.3 大規(guī)模算例試驗(yàn)結(jié)果與分析

針對大規(guī)模算例，將節(jié)點(diǎn)的分布類型分為C 類、R 類、RC 類，C 類算例中節(jié)點(diǎn)的分布形態(tài)為集群式分布，R 類算例中節(jié)點(diǎn)的分布形態(tài)為隨機(jī)分布，RC算例中節(jié)點(diǎn)的分布形態(tài)則結(jié)合C 類分布和R 類分布的特征.每類算例又根據(jù)時(shí)間窗要求的不同劃分成兩種.其中C 類算例有10 個(gè)，R 類算例有10 個(gè)，RC類算例有10 個(gè)，每類分布形態(tài)包括寬和窄時(shí)間窗的算例各5 個(gè).針對每個(gè)算例，運(yùn)行10 次，得到初始值f1、平均值f2、最優(yōu)值f3和程序的運(yùn)行時(shí)間t，試驗(yàn)結(jié)果如表7 和圖3 所示.

從表7 可以看出，所設(shè)計(jì)的ALNS 算法解決大規(guī)模的CEVRPTW 問題是可行的，且求解效果較好，但是代碼運(yùn)行時(shí)間較長.

表7 大規(guī)模算例試驗(yàn)結(jié)果Tab.7 Large-scale experimental results of algorithm example

從圖3 可以得出以下兩個(gè)結(jié)論：一是不同節(jié)點(diǎn)分布形態(tài)的求解結(jié)果有較大差異，特別是在C 類算例的路徑方案中車輛單次配送能夠訪問更多的客戶節(jié)點(diǎn)，車輛裝載率較高，致使C 類算例的平均值少于R類和RC 類算例，且C 類算例運(yùn)行時(shí)間更短.二是每類算例中不同種算例之間的目標(biāo)值存在較大的差異，這是由于C2 系列、R2 系列、RC2 系列算例的時(shí)間窗要求比C1 系列、R1 系列、RC1 系列的更加寬松，車輛在一次配送任務(wù)中訪問的客戶節(jié)點(diǎn)較多，車輛裝載率較高，使用車輛數(shù)較少，其配送成本也隨之減少.

圖3 大規(guī)模算例試驗(yàn)結(jié)果比較圖Fig.3 Comparison chart of large-scale algorithm examples’experimental results

3.4 ALNS 算子表現(xiàn)分析

研究了所設(shè)計(jì)的ALNS 算子的性能，如圖4～圖6 所示.每個(gè)圖的橫軸表示ALNS 算法的進(jìn)度：算法從0%開始，到100%結(jié)束.圖4 展示了每個(gè)算子的累積貢獻(xiàn)率，用算子發(fā)現(xiàn)新的可接受解的次數(shù)表示，并用找到新的可接受解的總次數(shù)（百分比）來歸一化.實(shí)線表示移除算子，虛線表示插入算子.從圖中可以看出，在算法搜索的早期就發(fā)現(xiàn)了較大數(shù)量的改進(jìn)解，搜索快結(jié)束時(shí)圖形逐漸變平.其中，最差充電站節(jié)點(diǎn)使用移除算子（SWR）、客戶節(jié)點(diǎn)相關(guān)移除算子（CSRR）和充電站節(jié)點(diǎn)比較插入算子（SCI）、客戶節(jié)點(diǎn)后悔插入算子（CRI）發(fā)現(xiàn)了最大數(shù)量的改進(jìn)解，性能較好.

圖4 每個(gè)算子的完成度Fig.4 Degree of completion for each operator

圖6 插入算子的權(quán)重變化Fig.6 Weight change of insertion operator

圖5和圖6 分別展現(xiàn)了移除、插入算子在算法執(zhí)行過程中的平均權(quán)重.盡管從百分比上講，最大延誤客戶節(jié)點(diǎn)移除算子（CBLR）和客戶節(jié)點(diǎn)相關(guān)移除算子（CSRR）發(fā)現(xiàn)了數(shù)量相近的改進(jìn)解（圖4），但從圖5 可以看出隨著時(shí)間的推移，該算子的性能會下降，并被客戶節(jié)點(diǎn)相關(guān)移除算子（CSRR）所超越.從圖6 可以看出，充電站節(jié)點(diǎn)比較插入算子（SCI）和客戶節(jié)點(diǎn)后悔插入算子（CRI）的性能始終優(yōu)于其他插入算子.

圖5 移除算子的權(quán)重變化Fig.5 Weight change of remove operator

綜合圖4～圖6 可知，針對CEVRPTW 問題所設(shè)計(jì)的ALNS 鄰域算子中，移除算子表現(xiàn)較好的是客戶節(jié)點(diǎn)相關(guān)移除（CSRR），最差充電站節(jié)點(diǎn)使用移除（SWR）次之；表現(xiàn)較差的是客戶節(jié)點(diǎn)隨機(jī)移除（CRR）、客戶節(jié)點(diǎn)隨機(jī)回路移除（CRRR）和客戶節(jié)點(diǎn)區(qū)域移除（CZR）.插入算子表現(xiàn)較好的是充電站節(jié)點(diǎn)比較插入（SCI）和客戶節(jié)點(diǎn)后悔插入（CRI）；表現(xiàn)較差的是客戶節(jié)點(diǎn)隨機(jī)插入（CI）和客戶節(jié)點(diǎn)貪婪插入（CGI）.

4 結(jié)論

1）將電動(dòng)車和客戶的軟時(shí)間窗需求同時(shí)應(yīng)用于冷鏈物流配送，建立了社會充電站環(huán)境下帶軟時(shí)間窗的冷鏈電動(dòng)車輛路徑問題的模型，并設(shè)計(jì)了切實(shí)可行的自適應(yīng)大鄰域搜索算法進(jìn)行求解.

2）算例結(jié)果表明，客戶地理位置的分布和時(shí)間窗的寬度對配送成本有很大影響，驗(yàn)證了模型和算法的有效性.

3）通過分析ALNS 算子的表現(xiàn)得出，算子的性能會隨著求解進(jìn)度變化，其中客戶節(jié)點(diǎn)相關(guān)移除和充電站節(jié)點(diǎn)比較插入算子的貢獻(xiàn)率及權(quán)重均隨迭代次數(shù)增加而不斷增加，且增幅較大，性能最好，而客戶節(jié)點(diǎn)隨機(jī)移除算子和隨機(jī)插入算子的貢獻(xiàn)率及權(quán)重均隨著迭代次數(shù)的增加而不斷下降，性能較差.