換電模式下電動車貨運路徑優(yōu)化模型與算法

李 進，王 鳳，楊沈宇

（1.浙江工商大學管理工程與電子商務學院，杭州 310018；2.浙江工商大學現(xiàn)代商貿(mào)研究中心，杭州 310018）

（?通信作者電子郵箱jinli@mail.zjgsu.edu.cn）

0 引言

物流行業(yè)具有高能耗和高碳排放的特點，如何構建新型低碳環(huán)保的物流體系是物流業(yè)發(fā)展的必然趨勢。當前汽車碳排放約為我國總碳排放的25%，預計2030 年汽車二氧化碳排放量將達到423 億噸。推廣應用新能源車，加速燃油車替換是減少二氧化碳排放的必由之路。隨著城市限行和國家推動貨運用車電動化，我國明確提出提高電動車城市配送推廣應用力度，2020年全國電動物流車產(chǎn)量達到10萬輛。電動車在物流貨運領域的應用對于我國節(jié)能減排和提高環(huán)境和經(jīng)濟效益都具有十分重要的意義。為此，本研究將換電式電動車作為運輸工具，探究物流貨運過程中碳排放核算及其低碳路徑優(yōu)化。

經(jīng)典的車輛路徑問題（Vehicle Routing Problem，VRP）［1］往往只考慮經(jīng)濟因素，以行駛距離、時間或成本最小為優(yōu)化目標。低碳車輛路徑問題則關注車輛行駛過程中產(chǎn)生的碳排放對環(huán)境的影響，在考慮能耗和碳排放的基礎上建立車輛路徑優(yōu)化模型，越來越多的學者開始重視這方面的研究。早在1985 年，Cermak 等［2］就開始研究考慮城市氣體污染防控的物流配送問題。Bekta?等［3］提出了污染路徑問題，建立了考慮溫室氣體的排放、油耗和旅行時間等因素的基于混合整數(shù)規(guī)劃的數(shù)學模型，提出了將非線性問題轉化為線性規(guī)劃問題的解決方案。Behnke等［4］研究了城市配送中考慮多車型和復雜交通網(wǎng)絡的最小化排放的車輛路徑問題，提出了一種列生成的有效求解算法。Turkensteen［5］在可變速度下對車輛路徑優(yōu)化中的傳統(tǒng)油耗和碳排放計算模型進行了驗證，發(fā)現(xiàn)速度波動相較于固定速度的計算方法油耗可能增加高達80%。李進等［6］建立了碳交易機制下的物流配送路徑優(yōu)化模型，分析了碳交易、碳價格和碳配額對配送路徑策略、碳排放量和總成本的影響。周鮮成等［7］研究了時間依賴型綠色車輛路徑問題，構建了考慮車輛油耗、碳排放、旅行時間以及固定起用成本等為目標的模型，并對蟻群算法進行改善設計。

目前在車輛路徑問題研究中，很少有學者將電動車作為運輸工具。根據(jù)目前電動車充電的模式、與電動車匹配的基本設施，現(xiàn)有研究主要將其細分為三個角度來研究:充電型電動車路徑優(yōu)化、換電型電動車路徑優(yōu)化以及電動車充換電站選址優(yōu)化。在充電型電動車路徑優(yōu)化方面，Conrad 等［8］構建了充電型電動車路徑優(yōu)化模型，實現(xiàn)了電動車使用成本和貨運成本的最小化。Hiermann 等［9］考慮了電動車的不同類型和時間窗約束，構建了最小化車輛數(shù)和行駛距離的電動車路徑優(yōu)化模型。Pelletier 等［10］提出了考慮不確定能耗的電動車貨運路徑優(yōu)化問題，在大規(guī)模鄰域搜索基礎上提出了一種兩階段啟發(fā)式算法。Bahrami 等［11］研究了插電式混合動力車輛路徑問題，以總能耗最小為目標建立了一種能源管理模型，提出了一種精確的分支定價法和一種啟發(fā)式算法。葛顯龍等［12］研究了帶軟時間窗的電動車輛路徑優(yōu)化問題，建立了最小化路徑成本、時間窗懲罰成本和車輛使用成本的數(shù)學模型，設計了融合節(jié)約里程和禁忌搜索的混合算法。

在電動車充電站選址與車輛路徑問題方面，現(xiàn)有文獻主要是將充電站的選址與電動車路徑進行集成規(guī)劃。例如:Yang 等［13］比較早地研究了基于電動車的網(wǎng)絡選址與車輛路徑聯(lián)合問題，該問題考慮了電動車的容量約束和換電站的布局，設計了相應的啟發(fā)式算法和禁忌搜索算法。楊珺等［14］將換電站選址和電動車路徑優(yōu)化進行集成研究，提出了一個混合整數(shù)規(guī)劃模型，設計了一種改進的禁忌搜索智能求解算法，通過數(shù)值仿真對電動車容量、續(xù)航能力和固定建設成本等進行了參數(shù)敏感性研究。Worley等［15］也研究了電動車充電站選址和電動車路徑優(yōu)化相結合的問題，建立了考慮電動車續(xù)航里程和容量的一個整數(shù)規(guī)劃數(shù)學模型。

將電動車作為物流運輸工具，符合我國能源結構調(diào)整和物流車輛電動化的要求，研究和分析物流配送的碳排放和能耗節(jié)約情況具有很強的實際應用背景。目前換電式電動車具有充電快、安全性高和續(xù)航長等優(yōu)點，傳統(tǒng)的研究大多關注慢充或快充等充電方式的研究，對于物流企業(yè)具有車輛數(shù)量、電池續(xù)航能力和換電站等約束下以節(jié)能減排為目標的換電式電動車路徑優(yōu)化問題，目前這方面的研究還比較缺乏。由于車輛的碳排放與能耗有關，而能耗受到車輛速度、載重和距離等多種因素的影響，因此該研究還將建立換電式電動車的碳排放度量模型。總之，將換電模式下的電動車作為物流貨運車輛，在路徑優(yōu)化中加入對能耗和碳排放的考量，該問題稱之為換電式電動車貨運路徑優(yōu)化問題（Battery-swapping Electricvehicle Freight Routing Problem，BE-FRP）。同時，針對該問題是NP-hard 難題［16-17］，提出能夠滿足計算機實時計算要求的基于爬山優(yōu)化和鄰域搜索的自適應遺傳算法。該算法的交叉和變異概率隨著種群的適應度變化而自適應調(diào)整，通過爬山優(yōu)化加強了算法的局部搜索能力，提出了電動車換電站鄰域搜索策略以滿足電動車的電池續(xù)航容量和換電站約束，從而最終求得模型的最優(yōu)解。通過數(shù)值實驗驗證了所提自適應遺傳算法能夠快速有效地求得滿意的可行解，確保經(jīng)濟成本和碳排放量的最小化。

1 BE-FRP模型的建立

1.1 問題描述

文中定義的數(shù)學符號如下:完全有向圖G=(V，E)表示貨運配送網(wǎng)絡，其中:V=C∪F為節(jié)點的集合，C={1，2，…，n}為客戶點集合，F(xiàn)={0，n+1，n+2，…，n+}為換電站的集合，節(jié)點0 表示配送中心，假設配送中心也設有換電站+1為最大可用換電站數(shù)，E={(i，j)|i≠j∈V}表示弧集；K={1，2，…，}表示電動車隊集合為最大可用電動車輛數(shù)，電動車的載重容量為Q；dij表示弧(i，j)的距離；vij表示車輛從節(jié)點i出發(fā)訪問弧(i，j)的行駛速度；pij表示電動車訪問弧(i，j)的耗電量；lij表示電動車輛在弧(i，j)的貨物載重量；sf為電動車在換電站f的換電服務時間，f∈F；qi表示客戶點i的貨物需求量，i∈C；T為電動車的電池容量；xijk表示若電動車輛k訪問弧(i，j)，則其值為1，否則其值為0；yijk表示電動車輛k訪問弧(i，j)后的剩余電量。決策變量為xijk。

不同于傳統(tǒng)的燃油車輛路徑問題，經(jīng)典的VRP 往往只允許車輛訪問一次客戶點，BE-FRP將換電式電動車作為運載車輛，加入了換電站，為了通過換電完成配送，電動車允許訪問同一換電站多次，同時還將考慮換電站和電池續(xù)航能力約束。定義電動車每小時的使用費用為α，電動車使用費用與行駛時間正相關，包括司機薪酬、過路過橋費等；電動車消耗每度電的費用為β。BE-FRP 將優(yōu)化電動車輛和路線安排使得電動車使用費用和能消耗總成本最小化。此外，還應滿足如下條件:配送貨物時，電動車從配送中心發(fā)出，配送完成后最終返回配送點；每個客戶點被訪問且僅被訪問一次；換電站可被訪問多次；每條配送路線的總需求不超過電動車的容量限制；電動車輛具有電池續(xù)航能力限制。

1.2 綜合多種因素的電動車碳排放計算

影響電動車的電能損耗的因素有很多，包括電動車行駛的速度和距離、路況以及自身重量等。其中，車速的動態(tài)變化受到空氣阻力和道路擁堵等的影響，進而影響電量的消耗；電動車的重量包括空車重量和載重，載重隨著對客戶點的配送而不斷減少。根據(jù)已有研究［3］，電動車在弧(i，j)的電能消耗計算如下:

其中:aij=a+gsinθij+gCrcosθij為與路段有關的常數(shù)，a表示加速度，g為重力常數(shù)，θij為路段角度，Cr為滾動阻力系數(shù)；w為電動車空車的重量；γ=0.5Cd Aρ為與電動車型有關的系數(shù)，Cd為牽引系數(shù)，A為車輛迎風面積，ρ為空氣密度。本文所采用的電動車耗電計算方法能夠綜合反映電動車速度、載重和行駛距離這些關鍵要素的影響，使得電動車能耗計算更加精確和符合應用實際。

電動車的碳排放量與電動車在弧(i，j)的耗電量pij和電能排放因子e有關，計算如下:

其中，電能排放因子e為單位電能的二氧化碳排放量。我國還有較多的火力發(fā)電，而火力發(fā)電將產(chǎn)生大量二氧化碳氣體，該因子與所使用的電動車型和發(fā)電類型有關，在特定的物流配送中為一常數(shù)e，將其設定為e=0.7 kg/kWh［18］。

1.3 BE-FRP數(shù)學模型

根據(jù)綜合多種因素的電動車碳排放計算方法，BE-FRP的數(shù)學模型描述如下:

其中:式（3）為目標函數(shù)，表示最小化總成本，包括電動車輛使用費用和耗電費用兩個部分；式（4）和式（5）為每個客戶點的訪問唯一性約束；式（6）為配送中心限制，表示所有電動車均在完成配送任務后重新返回出發(fā)點配送中心；式（7）保證了每個弧段的流量守恒；式（8）和式（9）為電動車輛的容量約束；式（10）表示電動車在從配送中心或換電站充電后，其電量被充滿；式（11）約束了經(jīng)過客戶點后電動車電量消耗程度；式（12）保證了電動車的剩余電量能夠確保其完成任務后返回配送中心；式（13）為決策變量的約束。

由BE-FRP 的目標函數(shù)可以看出，該問題存在兩種特殊的情況，即:1）令α=0，該模型將最小化電動車的耗電費用，根據(jù)1.2 節(jié)，由于碳排放與電動車的耗電量成正比，也等同于最小化運輸中的碳排放；2）令β=0，則模型將以最小化運輸中的旅行時間費用為目標，也就是最小化旅行時間。因此，本文模型有利于通過對旅行時間費用和低碳成本的考慮反映出對電動車配送中經(jīng)濟和環(huán)境的綜合評估。

與傳統(tǒng)的VRP 模型相比，BE-FRP 的目標函數(shù)考慮了車輛使用和耗電費用構成的總成本，而傳統(tǒng)的VRP 往往以總旅行距離最小為目標；同時，BE-FRP 還考慮了與電動車有關的換電站充電約束、電量消耗約束和電動車數(shù)量約束，還允許電動車多次訪問同一換電站，從而保證了電動車順利完成配送，也更符合物流配送的實際情況。因此，BE-FRP是對傳統(tǒng)VRP的擴展，而經(jīng)典的VRP則簡化成為BE-FRP的一個特例。

2 BE-FRP的求解算法設計

由于經(jīng)典的VRP 是公認的NP-hard 問題［1］，而BE-FRP 是VRP的擴展，為了提高求解效率，需要設計啟發(fā)式算法求解該問題，所以本文擬提出一種基于爬山優(yōu)化和鄰域搜索的自適應遺傳算法。自適應遺傳算法是一種參數(shù)能夠根據(jù)求解過程靈活調(diào)節(jié)的智能算法［19］，與一般遺傳算法相比，其特點是交叉和變異概率隨著種群的適應度變化而自適應調(diào)整。為了加強算法的局部搜索能力，保證算法快速收斂到最優(yōu)解，還將引入爬山搜索算法，該算法對當前解采用循環(huán)過程，進行優(yōu)化改進，直到達到“峰頂”時結束。另外，為了滿足電池續(xù)航能力和換電站約束，對自適應遺傳算法得到的最優(yōu)解中的每條路徑進行換電站鄰域搜索，進一步改進最優(yōu)解，最終得到最優(yōu)可行解。自適應遺傳算法的基本流程及各階段之間的關系如圖1所示。

圖1 基于爬山優(yōu)化和鄰域搜索的自適應遺傳算法Fig.1 Adaptive genetic algorithm based on mountain-climb optimization and neighborhood searching

2.1 算法編碼、初始化種群和適應度函數(shù)策略

根據(jù)BE-FRP 模型特點，選擇實數(shù)編碼策略。首先，根據(jù)物流配送中心的數(shù)量、客戶點數(shù)n和換電站數(shù)量fˉ設定個體染色體長度；然后在貨運路徑中加入個體編碼元素。自然數(shù)編碼表示如下:設配送中心為0，客戶點為(1，2，…，n)，換電站為(n+1，n+2，…，n+)。由車輛的容量和客戶點總需求量可計算出貨運中啟用的最少電動車數(shù)量。

在種群內(nèi)，個體表示貨運路徑安排，個體的適應度值一方面取決于個體目標函數(shù)值，另一方面取決于是否滿足模型規(guī)定的約束條件。自然數(shù)編碼方式在編碼時將考慮電動車的總數(shù)量、電動貨車載重量和續(xù)航里程等約束條件。另外由于適應度函數(shù)δ追求最大值，這與模型函數(shù)最小化總成本Z的目標是相反的，故采用的計算公式為:δ=1/Z。

2.2 選擇策略

擬采用的選擇策略將融合保留最優(yōu)個體和輪盤賭法。首先，依次計算出每個個體的適應度值；接著，按照適應度值由大到小對個體進行降序排列，保留適應度值最高的個體進入后續(xù)遺傳操作；最后，通過輪盤賭法確定剩余個體能否進入后續(xù)操作。輪盤賭法將計算個體適應度與群體總適應度的比值，其中Ω為種群中所有個體的集合。個體被選擇的概率與該比值成正比。

2.3 交叉策略

交叉策略即對染色體基因進行適當處理，提高解空間的搜索功能，從而產(chǎn)生更優(yōu)異個體。種群的最小適應度、最大適應度和平均適應度分別用δmin、δmax和表示。設參數(shù)μ=(0.5，1)和ν=(0，0.5)。為了說明種群的適應度分布，定義為平均適應度和最大適應度的比值，該值越趨向0.5，表明種群集中程度越高。群體適應度集中程度通過最小和最大適應度的比值來確定，當該比值趨于0 時，表明算法陷入局部最優(yōu)。另外，若表示為個體適應度集中化的群體，否則表明群體中的個體適應度較為分散。

交叉策略的設置應盡量減少保留表現(xiàn)不好的個體和近親交叉操作，防止算法過早收斂。定義pc為交叉概率，U為父代個體分量的集合，和代表父代個體的第i個分量，xmin和xmax分別表示個體內(nèi)的最小和最大分量，δ1和δ2表示父代的兩個適應度。根據(jù)上述原則，自適應交叉概率［20］可計算如下:

由于算法前期種群內(nèi)個體一般較為分散，父代個體基因具有較大差異，交叉操作的概率將與個體適應度值成正比。在算法執(zhí)行后期，種群個體表現(xiàn)得較為集中，交叉操作有兩種可能:1）父代個體間基因表現(xiàn)為差別較小，算法可能趨向最優(yōu)解，那么需要提高交叉操作的概率使得平均適應度能夠進一步接近最大值。2）父代個體間基因表現(xiàn)相差較大，容易導致局部最優(yōu)解，那么就需要使用更大的交叉概率。

通過判斷交叉概率pc與(0，1)內(nèi)產(chǎn)生的隨機實數(shù)的大小關系決定是否啟用交叉策略。只有pc大于該隨機數(shù)值時才執(zhí)行如下的交叉操作:1）任意選擇兩條染色體作為交叉操作的父代染色體。2）對給定的父代染色體中的兩條車輛路徑，隨機選擇交叉位置，執(zhí)行次序交叉操作。3）將交叉后的兩條車輛路徑的子染色體合并，刪除連續(xù)為0 的元素，從而產(chǎn)生兩條新染色體。

2.4 變異操作策略

變異操作模仿基因遺傳中的染色體突變，從而增加解空間中種群和染色體的多樣性。利用自適應的變異概率，這樣可以增強個體的多樣性，使算法盡快跳出局部最優(yōu)的搜索過程。自適應的變異概率計算如下:

算法在前期時擬采用常數(shù)的變異概率，這是由于前期個體分散程度較高，種群具有較大的多樣性。而算法到了后期，解空間的個體集中性和種群多樣性都比較低，則根據(jù)適應度來自適應調(diào)整變異概率。如果個體適應度小于其平均值，那么適應度值減少，變異概率將增加；否則，變異概率將隨著個體適應度的增加而減小。

首先通過計算自適應交叉概率pm與(0，1)內(nèi)隨機實數(shù)的大小關系判斷個體是否需要執(zhí)行變異操作。如果pm比該值小，則不執(zhí)行變異過程；否則，開展如下變異操作過程:1）將選定的染色體當成父代染色體。2）在父代染色體中，對所有車輛路徑隨機確定變異位置，并進行交換變異操作。3）刪除連續(xù)為0 的元素，合并車輛路徑的子染色體，從而形成新染色體。

2.5 爬山優(yōu)化與終止準則

爬山優(yōu)化將應用于算法過程的以下兩個部分:1）優(yōu)化產(chǎn)生的初始種群并改進種群的個體適應度。2）在算法遺傳過程執(zhí)行后，優(yōu)化最優(yōu)適應度個體，實現(xiàn)對遺傳操作最優(yōu)解進行局部尋優(yōu)，嘗試進一步改進該解。

爬山優(yōu)化將執(zhí)行如下步驟:

步驟1 對染色體表示的子車輛路徑，隨機選擇基因所在位置，并執(zhí)行互換的操作。

步驟2 對比互換操作前后每個個體適應度發(fā)生的變化，若個體適應度值減少或不變，則原染色體也不變；否則，進行原染色體更新操作。

步驟3 判斷是否到達終止條件，如果沒有到達則循環(huán)執(zhí)行步驟1和步驟2。

對于算法終止規(guī)則的設定，常見的有三類:1）達到預先給定的目標函數(shù)值，則算法終止，該方法通常需要預先知道最優(yōu)目標值，然后對其進行反證。2）算法連續(xù)執(zhí)行設定的若干次數(shù)沒有改進當前解，則算法終止，由于連續(xù)執(zhí)行的次數(shù)難以預先估計，導致算法可能無法跳出局部最優(yōu)解。3）可以根據(jù)要求的計算時間和精度，設定算法的最大迭代次數(shù)，最終保證算法收斂到最優(yōu)解，故本文研究選擇該終止規(guī)則。

2.6 鄰域搜索策略

電動車換電站點的鄰域搜索就是根據(jù)客戶點與換電站的位置，確保最優(yōu)解中的每條路徑都滿足電動車的續(xù)航能力約束和換電站約束。假設換電站的位置是給定的，電動車在按照配送順序行駛到某一客戶點時，根據(jù)其剩余電量能否到達下一客戶點決定是否進行換電操作，如果它的剩余電量不足以行駛到下一客戶點，根據(jù)這兩個客戶點之間的行駛半徑尋找最近的換電站位置，換電站鄰域搜索的主要流程如圖2所示。

圖2 電動車換電站鄰域搜索Fig.2 Battery-swapping neighborhood searching for electric vehicle

鄰域搜索具體過程如下:

步驟1 在貨運路徑中，當電動車訪問某一客戶點時，對貨運電動車的當前可用電量進行計算。

步驟2 根據(jù)可用電量估算電動車能否正常到達下一目的節(jié)點（可能是客戶點或配送中心）。如果能夠到達，則轉到步驟3；否則，轉到步驟4。

步驟3 繼續(xù)前往下一節(jié)點，直至所有節(jié)點搜索完畢終止。

步驟4 按照鄰域規(guī)則記錄下就近的換電站及其數(shù)量。

步驟5 對于每個候選的換電站，確定該電動車通過該換電站進行充電服務的行駛距離。

步驟6 對通過每個換電站的行駛距離進行比較，根據(jù)鄰域原則確定最優(yōu)方案。

步驟7 該節(jié)點的換電站鄰域搜索終止，轉到步驟3。

2.7 自適應遺傳算法具體執(zhí)行步驟

通過上述對算法關鍵內(nèi)容的詳細分析，自適應遺傳算法的具體執(zhí)行安排如下:

步驟1 初始化。初始種群規(guī)模設定為Inn，算法最大迭代次數(shù)為Gnmax，確定網(wǎng)絡圖中任意兩節(jié)點間的行駛距離。對個體進行自然數(shù)編碼，初始化滿足模型約束條件的種群。計算出每個個體的適應度值，并選擇出適應度最小的個體。

步驟2 執(zhí)行爬山優(yōu)化操作，改進適應度最小的個體，并設定初始爬山次數(shù)為t=0。

步驟3 根據(jù)總爬山次數(shù)Tmax確定是否終止爬山操作。如果達到，則替換種群當前解為最優(yōu)解；否則，轉到步驟2，并更新t=t+1。

步驟4 確定選擇概率為(0，1)的隨機數(shù)，按照適應度水平對種群中的個體排序，若個體適應度不是最高的，則根據(jù)輪盤賭法設定選擇概率，如果個體適應度達到了最高，其選擇概率可設定為1。初始化執(zhí)行次數(shù)s=0。

步驟5 交叉策略。產(chǎn)生(0，1)的隨機實數(shù)，若交叉概率小于該值，不進行交叉；否則執(zhí)行交叉操作。

步驟6 變異策略。產(chǎn)生(0，1)的隨機實數(shù)，若變異概率小于該值，則不進行變異；否則執(zhí)行變異操作。

步驟7 對新的種群，計算各個體的適應度值并給出適應度最大的個體。初始化爬山次數(shù)b=0。

步驟8 利用爬山搜索優(yōu)化適應度最高的個體，一旦適應度增加則更新最優(yōu)解。

步驟9 爬山次數(shù)是否達到最大執(zhí)行數(shù)目Bmax，一旦達到則更新最優(yōu)解；否則，令b=b+1并執(zhí)行步驟8。

步驟10 算法終止條件。執(zhí)行次數(shù)是否達到Gnmax，如果達到最大迭代次數(shù)，則對當前的最優(yōu)個體進行記錄，轉到步驟11；否則轉到步驟5，并更新迭代次數(shù)s=s+1。

步驟11 利用換電站的鄰域搜索方法對遺傳算法得到的最優(yōu)解進行后優(yōu)化，記錄下最優(yōu)可行解。

步驟12 終止整個算法，輸出最優(yōu)可行解。

3 實驗與結果分析

3.1 實驗設置

某所在地區(qū)貨運公司從其一配送中心出發(fā)為客戶執(zhí)行送貨服務，假設該中心有5 輛電動車。選取該公司29 個訂單的數(shù)據(jù)，包括:客戶點的位置、需求量和換電站（5 座）。電動車離開配送中心或在換電站充電后假設電池被充滿，換電時間為0.1 h，電動車貨運的平均速度為60 km/h。目前微面和輕卡是電動車市場的主力，考慮到市場實際和經(jīng)濟效益，貨運電動車選擇電動車中微面型的“電牛一號”，并將其參數(shù)作為仿真數(shù)據(jù)。另外，將工業(yè)用電的價格0.8 元/kWh 作為電動車換電的可變費用。

結合實際情況和電動車相關參數(shù)，實驗仿真中的模型相關參數(shù)設置如下:電動車使用成本α=120元/h；充電費用β=0.8 元/kWh；電池容 量T=35.7 kWh/L；換電服 務時間sf=0.1h；空車重量w=1325 kg；車輛最大載重Q=595 kg；加速度a=0 m/s2（假設勻速行駛）；重力常數(shù)g=9.81 m/s2；路段角度θij=0；滾動阻力系數(shù)Cr=0.01；牽引系數(shù)Cd=0.7；車輛迎風面積A=0.378 m2；空氣密度ρ=1.204 1 kg/m3。

3.2 算法參數(shù)設置與分析

參數(shù)設置直接影響算法的收斂性，主要從初始種群的大小、自適應交叉、變異概率和爬山搜索次數(shù)多個方面設置最優(yōu)的參數(shù)范圍，加快算法收斂速度。首先確定合適的種群規(guī)模，為此依次對［50，310］區(qū)間中每次增加20 的種群規(guī)模進行測試，每組種群進行10次運算，圖3給出了算法的平均收斂代數(shù)和收斂概率。由圖3 可以看出，隨著種群規(guī)模的增加，平均收斂代數(shù)總體先減少后增加，而收斂概率則正好相反，即種群規(guī)模太大或太少都會減小收斂概率。特別地，當種群規(guī)模達到210 時，具有最大的收斂概率，同時只需要最少的迭代次數(shù)就可以收斂。為此，將初始種群規(guī)模的參數(shù)選為210 時最為合適。

圖3 最佳種群規(guī)模的設置Fig.3 Setting of optimal population size

下面對自適應與常數(shù)的交叉和變異概率進行比較。使用確定的最優(yōu)種群規(guī)模210，算法在迭代到200 次時終止，常數(shù)時的交叉和變異概率分別為0.8 和0.06。圖4～5 為仿真50 次獲得相同最優(yōu)解時常數(shù)概率和自適應概率的收斂情況?？梢钥闯?，常數(shù)概率的方案在算法初期表現(xiàn)較好，但當?shù)?0 次以后，自適應概率的方法通過提升交叉概率，保證算法較快接近最優(yōu)解。當?shù)螖?shù)超過160 后，自適應方法增加了變異概率，使得算法更快達到最優(yōu)解?？傊ㄟ^交叉和變異概率參數(shù)的自適應調(diào)整，有利于算法快速全局尋優(yōu)，提高了算法的靈活性。

圖4 交叉和變異概率為常數(shù)下的收斂曲線Fig.4 Convergence curves with fixed crossover and mutation probabilities

下面通過數(shù)值實驗探討如何設置最優(yōu)的爬山搜索迭代次數(shù)。給定前文實驗得到的最佳初始種群規(guī)模和自適應的交叉、變異概率，在區(qū)間［0，210］選取爬山搜索次數(shù)，每個候選次數(shù)運行10 次求算法的平均適應度和平均收斂代數(shù)，結果如圖6 所示。可以看出，平均適應度和平均收斂代數(shù)隨著爬山次數(shù)的變化波動較大，總體上當爬山次數(shù)位于［25，40］，算法收斂快且平均適應度也比較高。故為了加快算法的收斂，將爬山次數(shù)設定在35次。

圖6 爬山次數(shù)的設定Fig.6 Setting of mountain-climb number

3.3 模型計算結果分析

選用Matlab 7 對自適應遺傳算法進行編程實現(xiàn)，求出數(shù)值案例的最優(yōu)解。限制電動車為3 輛，根據(jù)前面的初步參數(shù)實驗，擬設置參數(shù)為:算法最大迭代次數(shù)350，爬山最大次數(shù)35，初始種群規(guī)模210。運行算法20 次，記錄前5 個最佳路徑結果，如圖7 所示。由圖7 可見，最優(yōu)路徑為線路5，且如圖8所示，共三條子路線，其總費用為277.68 元，碳排放總量為93.5 kg。通過對比可得，該最優(yōu)解在所有可行解中不僅實現(xiàn)了總成本的最小化，也最大限度地降低了碳排放量。

圖7 模型求解路徑結果Fig.7 Result of model solving routes

圖8 換電式電動車配送最優(yōu)路徑Fig.8 Optimal distribution route of battery-swapping electric vehicle

3.4 算法比較分析

為了說明所提出的改進的自適應遺傳算法的求解表現(xiàn)，將其與基本的常數(shù)參數(shù)的遺傳算法進行比較。終止規(guī)則是評價各算法以何種收斂速度達到當前最優(yōu)解的適應度值。如果達到最優(yōu)適應度值，則判定為收斂；否則算法不收斂。同樣選取初始種群數(shù)量為210，基本遺傳算法（概率固定）中變異概率為0.05，交叉概率為0.8。圖9 給出了兩種算法分別運算10次的結果。從圖9 中可以看出，自適應遺傳算法迭代次數(shù)在50～100，相較于傳統(tǒng)的遺傳算法，平均減少了52.1%，這表明所提出的自適應遺傳算法具有更高的求解效率，能夠更快地收斂到最優(yōu)解。

圖9 不同算法迭代次數(shù)比較Fig.9 Comparison of iteration times of different algorithms

4 結語

綠色環(huán)保已成為世界主題，發(fā)展電動汽車是我國能源戰(zhàn)略轉型和未來汽車行業(yè)發(fā)展的方向。研究和分析基于電動車的物流運輸具有十分重要的現(xiàn)實意義，優(yōu)化電動車貨運路徑是實現(xiàn)物流配送節(jié)能減排的重要舉措。本文以經(jīng)典的VRP作為基本參考模型，引入了綜合考慮速度、載重和行駛距離等多種因素的電動車能耗與碳排放計算方法，并考慮了電動車的容量、電池續(xù)航能力和換電站多次服務等新的約束，建立了考慮電動車使用費用和耗電費用的換電式電動車貨運路徑優(yōu)化問題模型——BE-FRP。算法比較結果表明，所提出的自適應遺傳算法能夠更快地收斂到最優(yōu)解，提升了算法的效率。

本文研究將為采用電動車作為運輸工具的物流企業(yè)的實際配送操作提供優(yōu)化模型和求解算法等決策支持，同時也可為政府制定電動車物流政策提供參考。