徐婷婷，胡曉銳，胡 文，李雙慶，池 磊

(1.國(guó)網(wǎng)重慶市電力公司 營(yíng)銷(xiāo)服務(wù)中心,重慶 401123；2.重慶大學(xué) 計(jì)算機(jī)學(xué)院，重慶 400044)

物流配送對(duì)規(guī)模和時(shí)效性要求越來(lái)越高，物流車(chē)輛路徑優(yōu)化問(wèn)題顯得極其重要，合理的車(chē)輛路徑規(guī)劃方案可以為企業(yè)節(jié)省大量配送成本。另一方面，傳統(tǒng)物流車(chē)輛已造成嚴(yán)重的污染物排放問(wèn)題，而物流汽車(chē)電動(dòng)化是解決排放治理的重要手段，但電動(dòng)物流車(chē)最大的問(wèn)題在于配送里程焦慮?？紤]物流總路程、用戶(hù)時(shí)間窗口、總時(shí)間的條件下，提出一種加權(quán)AP聚類(lèi)的非支配排序遺傳算法(AP-NSGA-Ⅱ)來(lái)解決電動(dòng)物流車(chē)的路徑優(yōu)化配送問(wèn)題。

電動(dòng)物流車(chē)物流配送大部分關(guān)注的是路徑優(yōu)化。葛顯龍等[1]運(yùn)用混合模擬退火算法研究了靈活充電策略帶時(shí)間窗口的電動(dòng)物流車(chē)的配送問(wèn)題，Schneider和Stenger等[2]在VRP條件下，通過(guò)車(chē)載電池容量的增加，搭建了電動(dòng)物流車(chē)的車(chē)輛路徑優(yōu)化問(wèn)題，并建立電動(dòng)汽車(chē)數(shù)量最小和路徑最短的多目標(biāo)，尋求最優(yōu)行駛路徑。Lim和Kuby[3]基于公共設(shè)施的選址問(wèn)題，提出電動(dòng)汽車(chē)的能源補(bǔ)充設(shè)施選址模型。馮智泉等[4]應(yīng)用蟻群算法對(duì)分段路線(xiàn)進(jìn)行優(yōu)化，在全局充電方案中加入行駛路徑的約束，將兩部分結(jié)合形成全局的最優(yōu)行駛路徑。文展等[5]提出一種改進(jìn)的粒子群優(yōu)化算法解決離散域的組合優(yōu)化問(wèn)題及車(chē)輛路徑規(guī)劃。但這些方法普遍存在以下問(wèn)題：1)隨著配送點(diǎn)的增加，車(chē)輛路徑可行解呈階乘增長(zhǎng)，使用啟發(fā)式或者亞啟發(fā)式算法的求解效率低，且容易陷入局部最優(yōu)，貪婪隨機(jī)自適應(yīng)搜索算法等[6-10]；2)大多數(shù)車(chē)輛路徑問(wèn)題的優(yōu)化目標(biāo)函數(shù)較少，不切合現(xiàn)實(shí)場(chǎng)景需求，未考慮相關(guān)變量的相互關(guān)系，導(dǎo)致實(shí)際應(yīng)用的局限性[11-14]。3)電動(dòng)物流車(chē)的里程焦慮問(wèn)題，限制了每輛電動(dòng)物流車(chē)路徑規(guī)劃的最長(zhǎng)距離，導(dǎo)致電動(dòng)物流車(chē)的用車(chē)數(shù)量增加，綜合用車(chē)成本增加[15-17]。

研究提出一種改進(jìn)的非支配遺傳算法(AP-NSGA-Ⅱ)解決大規(guī)模物流電動(dòng)車(chē)的路徑規(guī)劃問(wèn)題，根據(jù)配送點(diǎn)的分布，采用先聚類(lèi)再并行優(yōu)化的方式解決多目標(biāo)問(wèn)題，聚類(lèi)采用帶權(quán)AP算法，并行多目標(biāo)優(yōu)化采用改進(jìn)的非支配排序算法得到初始配送方案。避免了初始配送方案的隨機(jī)性和盲目性，同時(shí)也降低了算法的執(zhí)行復(fù)雜度。在初始路徑規(guī)劃的基礎(chǔ)上執(zhí)行鄰近配送點(diǎn)搜索進(jìn)行局部重構(gòu)，以獲得最終配送方案。最后根據(jù)配送點(diǎn)的權(quán)值大小，優(yōu)選配送路途充電策略。

1 問(wèn)題描述

在已知區(qū)域內(nèi)有一定數(shù)量的配送點(diǎn)和充電站，從物流中心出發(fā)，若干輛電動(dòng)物流車(chē)對(duì)所有配送點(diǎn)進(jìn)行雙向貨物配送，在配送過(guò)程中，要綜合考慮配送點(diǎn)的分布和充電站的地理位置，當(dāng)電動(dòng)物流車(chē)的電池余量不足完成剩余配送，則尋求最適合的充電站進(jìn)行充電，以滿(mǎn)足配送任務(wù)，考慮總路程、時(shí)間窗口和總時(shí)間的多目標(biāo)優(yōu)化問(wèn)題。圖1展示了典型電動(dòng)物流車(chē)的配送場(chǎng)景，其中0為配送中心，N1～N7為配送點(diǎn)，C1,C2為充電站。

圖1 途中充電策略示意圖

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

2.1 假設(shè)條件

實(shí)際場(chǎng)景中大規(guī)模電動(dòng)物流車(chē)配送問(wèn)題較為復(fù)雜，比如路況擁堵，電池衰減、貨物體積容量，人力成本計(jì)算等，這些都是影響配送結(jié)果的因素。為了簡(jiǎn)化模型，做如下假設(shè)：

1)每輛電動(dòng)物流車(chē)從配送中心出發(fā)最終回到配送中心，形成環(huán)路；

2)每個(gè)配送點(diǎn)的送貨量和取貨量不能大于電動(dòng)物流車(chē)的最大載貨量；

3)僅考慮貨物的重量，不考慮貨物的體積容量；

4)每輛電動(dòng)物流車(chē)的電池容量、行駛速度、充電系數(shù)等參數(shù)配置一致；

5)電動(dòng)物流車(chē)的行駛距離、充電時(shí)長(zhǎng)與電池容量呈線(xiàn)性關(guān)系；

6)每個(gè)充電站能多次被訪(fǎng)問(wèn)，且無(wú)等待時(shí)間

7)不考慮交通擁堵、車(chē)輛故障等特殊因素，且配送過(guò)程的車(chē)速是均勻的；

8)每個(gè)配送點(diǎn)的裝卸貨時(shí)長(zhǎng)為0，僅考慮路途時(shí)間和充電時(shí)間。

AP-NSGA-Ⅱ算法的思想：以充電樁為重要潛在聚類(lèi)中心，根據(jù)各配送點(diǎn)的取送貨量為權(quán)值，執(zhí)行加權(quán)AP算法以獲得配送點(diǎn)的聚類(lèi)中心，各簇執(zhí)行NSGA-Ⅱ多目標(biāo)算法，并考慮電池笑話(huà)以獲得最終配送方案。數(shù)學(xué)符號(hào)如表1所示。

表1 數(shù)學(xué)符號(hào)及含義

2.2 加權(quán)AP聚類(lèi)算法

AP(affinity propagation)算法稱(chēng)為鄰近傳播算法或者親和度傳播算法，其基本思想是將所有數(shù)據(jù)點(diǎn)看成潛在的聚類(lèi)中心，根據(jù)點(diǎn)與點(diǎn)之間的距離自主劃分聚類(lèi)區(qū)域，算法中每一個(gè)點(diǎn)的權(quán)重等值。作為大規(guī)模的電動(dòng)物流車(chē)的配送問(wèn)題，區(qū)域劃分可以明顯降低計(jì)算復(fù)雜度。由于配送點(diǎn)和充電站的權(quán)重不等價(jià)，在考慮配送和充電方案時(shí)，區(qū)域的劃分不能簡(jiǎn)單自主聚類(lèi)，通過(guò)設(shè)置每個(gè)點(diǎn)的權(quán)重來(lái)控制AP聚類(lèi)結(jié)果。配送點(diǎn)i的權(quán)重設(shè)置為送貨量和取貨量之和，即Di+Ri，充電樁的權(quán)值設(shè)置為所有配送點(diǎn)權(quán)值的最大值max{Di+Ri},i∈N∪C。加權(quán)AP算法的初始化相似度矩陣S的各元素為

(1)

式中：s(i,k)表示第i個(gè)配送點(diǎn)到第k個(gè)配送點(diǎn)的帶權(quán)歐式距離的負(fù)值，當(dāng)i=k時(shí)，更新相似度矩陣S對(duì)角線(xiàn)的值為相似度矩陣中所有值的最小值；

初始化吸引度矩陣R為0矩陣，其中r(i,k)描述了配送點(diǎn)k作為配送點(diǎn)對(duì)象i的聚類(lèi)中心的程度，初始化歸屬度矩陣A為0矩陣，其中a(i,k)描述了配送點(diǎn)i選擇配送點(diǎn)k作為聚類(lèi)中心的合適程度。

更新吸引度矩陣R

(2)

式中：t為迭代序號(hào)；j表示除配送點(diǎn)k的任意一個(gè)配送點(diǎn)；r(i,k)表示配送點(diǎn)k成為配送點(diǎn)i的聚類(lèi)中心的證明，如果r(i,k)>0，越大表示配送點(diǎn)k成為聚類(lèi)中心的能力越強(qiáng)。

更新歸屬度矩陣A，

(3)

式中：a(i,k)分為兩種情況:當(dāng)i≠k時(shí)，取所有大于0的吸引度累加，加配送點(diǎn)k作為聚類(lèi)中心的可能性與0之間的小值;當(dāng)i=k，表示所有其他配送點(diǎn)傳遞給配送中心k的正吸引度的累加。

根據(jù)衰減系數(shù)λ對(duì)吸引度矩陣和歸屬度矩陣進(jìn)行更新，所述衰減系數(shù)λ為[0,1]之間的正數(shù)；

(4)

重復(fù)執(zhí)行式(2)～式(4)，直到吸引度矩陣R和歸屬度矩陣A穩(wěn)定并不再更新，當(dāng)r(k,k)+a(k,k)>0就認(rèn)為是配送點(diǎn)k是一個(gè)聚類(lèi)中心，再根據(jù)其他配送點(diǎn)到聚類(lèi)中心的最短歐式距離劃分各簇，最終劃分為M個(gè)簇。

2.3 電動(dòng)物流車(chē)路徑規(guī)劃

利用加權(quán)AP算法把大規(guī)模的配送點(diǎn)和充電樁進(jìn)行劃分后，在簇內(nèi)執(zhí)行考慮充電策略的改進(jìn) NSGA-Ⅱ算法。建立以簇內(nèi)電動(dòng)物流車(chē)的總路程、簇內(nèi)電動(dòng)物流車(chē)行駛總時(shí)間、簇內(nèi)時(shí)間懲罰成本為最小的多目標(biāo)優(yōu)化函數(shù)。

(5)

(6)

(7)

(8)

(9)

(10)

Li-1+(Ri-Di)L,?i∈N,

(11)

(12)

Qi+g·tfiQ,?i∈C,

(13)

(14)

yik∈{0;1},?i∈V,k∈K,

(15)

式(5)～式(7)分別為目標(biāo)函數(shù)f1電動(dòng)物流車(chē)的總路程;目標(biāo)函數(shù)f2電動(dòng)物流車(chē)配送過(guò)程花費(fèi)的時(shí)間;目標(biāo)函數(shù)f3時(shí)間懲罰成本的計(jì)算；式(8)表示每個(gè)配送點(diǎn)僅被電動(dòng)物流車(chē)k服務(wù)一次，式(9)表示電動(dòng)物流車(chē)k從配送中心出發(fā)只服務(wù)一條配送線(xiàn)路，式(10)表示電動(dòng)物流車(chē)k進(jìn)入某個(gè)節(jié)點(diǎn)后必須離開(kāi)。式(11)表示電動(dòng)物流車(chē)在進(jìn)入配送點(diǎn)i之前的裝車(chē)容量要滿(mǎn)足配送點(diǎn)j的貨送貨之差。式(12)表示配送車(chē)輛k從節(jié)點(diǎn)i出發(fā)的剩余電池容量Qi要滿(mǎn)足到達(dá)節(jié)點(diǎn)i；式(13)表示電動(dòng)物流車(chē)在充電站i充電后的電池容量不能大于電池最大容量；式(14)和(15)是決策比變量約束。

2.4 非支配排序遺傳算法

2.4.1 編碼方式

本算法采用的智能編碼方式為自然數(shù)編碼，所有節(jié)點(diǎn)的編碼方式為自然數(shù)，配送中心為0，對(duì)配送點(diǎn)和充電站依次進(jìn)行編碼：1,2,3,4,5,…,m。在某個(gè)簇的配送網(wǎng)絡(luò)中，如有10個(gè)配送點(diǎn)編號(hào)依次為1到10，2個(gè)充電站編號(hào)為11和12，若使用2輛電動(dòng)物流車(chē)進(jìn)行配送活動(dòng)，一條完整個(gè)體編碼形式為：0→8→3→12→4→0→1→10→11→5→7→9→6→2→0，其中，0→8→3→12→4→0和0→1→10→11→5→7→9→6→2→0分別表示兩條完整的配送環(huán)路，前一條環(huán)路展示了電動(dòng)物流車(chē)從配送中心0出發(fā)，依次經(jīng)過(guò)了配送點(diǎn)8和3，然后在充電站12進(jìn)行充電后，再經(jīng)配送點(diǎn)4，最后返回配送中心。

NSGA-Ⅱ的工作原理的偽代碼所示，算法如下

2.4.2 初始化種群

初始化個(gè)體編碼的基本思想為：以電動(dòng)物流車(chē)所在位置的作為參照中心，隨機(jī)選取離車(chē)輛最近的h個(gè)配送點(diǎn)的其中一個(gè)進(jìn)行配送，按照同一規(guī)則依次把配送點(diǎn)加入個(gè)體序列，再根據(jù)電動(dòng)物流車(chē)的載貨量和電池容量，分配車(chē)輛和插入充電站，具體步驟如下：

步驟4：根據(jù)電動(dòng)物流車(chē)的載貨量和電池容量約束以及充電站的位置信息，進(jìn)行車(chē)輛分配和插入充電站，生成一條符合配送要求的個(gè)體；

2.4.3 快速非支配排序

根據(jù)式(5)～式(7)的目標(biāo)函數(shù)，比較任意2個(gè)體之間的支配和非支配關(guān)系，找到種群中所有支配個(gè)體數(shù)為0的個(gè)體，并保存在當(dāng)前集合F1中，對(duì)于F1中的每一個(gè)個(gè)體i其所支配的個(gè)體集合為Si，遍歷Si中的每一個(gè)個(gè)體b，執(zhí)行遞減步驟，如果執(zhí)行完畢，將個(gè)體b保存在集合中H；在F1中得到的個(gè)體為第一個(gè)非支配層個(gè)體，并以H作為當(dāng)前集合，重復(fù)操作得到F2,F3…，直到初始種群的個(gè)體關(guān)系被全部分層，示意圖如2所示。

圖2 初始種群的個(gè)體關(guān)系

2.4.4 遺傳操作

遺傳操作包括：個(gè)體的選擇、交叉、變異，從而產(chǎn)生新種群。由于考慮充電策略和充電站的分布，遺傳操作首先是刪除充電站進(jìn)行操作，最后再根據(jù)耗電量插入序列。

a)選擇操作盡量選擇質(zhì)量較優(yōu)的父代個(gè)體，以ps的概率選擇父代，根據(jù)各層的非支配關(guān)系，選擇概率為pF1s>pF2s>pF3s，其中pF1s表示的集合F1選擇父代個(gè)體的概；

b)交叉操作：從父代中選擇差異性最大2個(gè)的父代交叉產(chǎn)生下一代個(gè)體，交叉的原則以一個(gè)父代中節(jié)點(diǎn)i和j為相鄰最近的配送點(diǎn)，另外一個(gè)父代中節(jié)點(diǎn)i和j為相鄰最遠(yuǎn)的2個(gè)配送點(diǎn)，如圖3所示，2個(gè)父代的區(qū)域進(jìn)行交換，把序列最長(zhǎng)的子代隨機(jī)刪除重復(fù)配送點(diǎn)后得到新的子代；

圖3 交叉操作

c)變異操作：父代的序列按照概率pm隨機(jī)生成2不相等的自然數(shù)，進(jìn)行變異操作，把父代中的兩個(gè)配送點(diǎn)的位置調(diào)換，得到新的子代，如圖4所示；

圖4 變異操作

如果遺傳操作后新子代的目標(biāo)函數(shù)小于之前的子代則保留，否則丟棄，依次生成N個(gè)，得到新一代種群，把父代和新一代種群合并形成2N的候選種群；

2.4.5 擁擠距離計(jì)算

擁擠距離的計(jì)算保證了種群多樣性，同時(shí)也是為了使得多目標(biāo)的解在目標(biāo)中間更加均勻。首先分別在3個(gè)目標(biāo)函數(shù)下計(jì)算個(gè)體i在同一層中與相鄰2個(gè)個(gè)體的平均距離，即以個(gè)體i+1和i-1為對(duì)角線(xiàn)形成的長(zhǎng)度。如果長(zhǎng)度越大則表示個(gè)體i與相鄰點(diǎn)的擁擠距離越大，即多樣性越好，就越應(yīng)該保留，以防止局部最優(yōu)的出現(xiàn)。通過(guò)遺傳操作生成新的子代也使得pareto前沿更均勻。

3 仿真分析與驗(yàn)證

3.1 實(shí)驗(yàn)方法及算例場(chǎng)景設(shè)計(jì)

為驗(yàn)證本算法對(duì)路徑規(guī)劃和充電策略的有效性, 在考慮實(shí)際場(chǎng)景容量和規(guī)模的情況下, 指定1個(gè)配送中心、隨機(jī)生成90個(gè)配送點(diǎn)和10個(gè)充電站，以及配送點(diǎn)對(duì)應(yīng)的裝卸貨物量、服務(wù)的起止時(shí)間進(jìn)行仿真分析。主要條件包含：電動(dòng)物流車(chē)的最大載貨量為4 t，車(chē)載電池的最大容量Q為40 kWh;每輛電動(dòng)物流車(chē)的最大行駛距離Dis=150 km,而配送車(chē)輛的電能消耗與行駛距離成正比，消耗速率ca為3.75 km/KWh;電動(dòng)物流車(chē)的行駛速度s為40 km/h。時(shí)間窗懲罰成本系數(shù)ep為10元/h;lp為20元/h，時(shí)間窗口小于0.5 h忽略懲罰，大于0.5 h記為1 h。部分節(jié)點(diǎn)如表2所示：其中0代表配送中心，序號(hào)表示配送點(diǎn)。

表2 部分節(jié)點(diǎn)的詳細(xì)信息

3.2 實(shí)驗(yàn)參數(shù)設(shè)定

為了驗(yàn)證實(shí)驗(yàn)的有效性，并定性分析與其他方法的優(yōu)勢(shì)，加權(quán)AP聚類(lèi)算法與NSGA-Ⅱ的參數(shù)設(shè)置如下：衰減系數(shù)設(shè)置為0.5，聚類(lèi)算法最大迭代次數(shù)為200次，聚類(lèi)中心無(wú)變化，迭代為15次。最近距離的配送點(diǎn)h設(shè)置為5，每個(gè)簇初始化種群數(shù)為100個(gè)，各層選擇操作的ps值為0.8，每次遞減0.1，交叉系數(shù)設(shè)置為 0.8，變異系數(shù)設(shè)置為 0.5，與NSGA-Ⅱ比較的其他優(yōu)化算法的參數(shù)設(shè)置為：MOEA/D[18]，COEA[19]，AMOSA[20]，MOEA/D的初始種群數(shù)大小為100，每一個(gè)子問(wèn)題對(duì)應(yīng)的領(lǐng)域大小為20，COEA外部檔案大小為100，AMOSA外部檔案大小也為100，初始溫度為100，冷卻系數(shù)為0.95，結(jié)束溫度為2.5×10-6。

3.3 加權(quán)AP聚類(lèi)算法分析

聚類(lèi)是為了降低多目標(biāo)優(yōu)化的計(jì)算復(fù)雜度。在不考慮充電站的情況下，分析帶聚類(lèi)算法的多目標(biāo)優(yōu)化與不帶聚類(lèi)算法的差異。驗(yàn)證聚類(lèi)方法對(duì)路徑規(guī)劃算法的優(yōu)越性。實(shí)驗(yàn)分別以配送點(diǎn)數(shù)量為200以下規(guī)模來(lái)測(cè)試帶聚類(lèi)算法的NSGA-Ⅱ與不帶聚類(lèi)算法的NSGA-Ⅱ的時(shí)間復(fù)雜度的區(qū)別。NSGA-Ⅱ分別獨(dú)立執(zhí)行50次的平均時(shí)間為基準(zhǔn)，多目標(biāo)優(yōu)化的運(yùn)行時(shí)間分別如圖5所示：可以明顯看出，不帶聚類(lèi)的NSGA-Ⅱ運(yùn)行時(shí)間與帶聚類(lèi)的算法，當(dāng)配送點(diǎn)在40個(gè)以下差異小，當(dāng)配送點(diǎn)40數(shù)量在以上時(shí)，NSGA-Ⅱ的計(jì)算復(fù)雜度為O(N2)呈指增長(zhǎng)，增長(zhǎng)速度，帶聚類(lèi)算法呈線(xiàn)性增長(zhǎng)。

圖5 聚類(lèi)與非聚類(lèi)的執(zhí)行時(shí)間比較

3.4 多目標(biāo)優(yōu)化算法比較

4個(gè)多目標(biāo)優(yōu)化算法設(shè)置為電動(dòng)物流車(chē)到達(dá)充電站后，執(zhí)行滿(mǎn)充操作。圖6給出了4種算法在f1～f2和f1～f3從三維映射到二維平面最終非支配解集前沿，在f1～f2總距離和總用時(shí)的關(guān)系圖中可以看出，帶AP聚類(lèi)的NSGA-Ⅱ算法求解路徑規(guī)劃時(shí)能在收斂性和多樣性上取得較好的效果，該算法的前沿要明顯優(yōu)于其他3種算法，在前沿的兩端，優(yōu)化集合中最短總路徑能達(dá)到1 277 km，總用時(shí)為57.2 h，當(dāng)優(yōu)先考慮總用時(shí)的情況下，總用時(shí)為48.26 h，總距離為1 938.75, km，而其他3種算法AMOSA優(yōu)化集中最短路徑為1 475.59 km，MODEA/D的前沿的最短路徑為1 648.4 km，COEA則為1 490.2 km，由此可以分析得出該算法比其他3種算法更好平衡距離和總用時(shí)的關(guān)系。同樣，圖7是f1～f3距離和總懲罰金額的非支配解集前沿，AP-NSGA-Ⅱ大部分的前沿優(yōu)于其他算法，雖然在總距離區(qū)間[1 800-2 000]的懲罰金額，AMOSA算法稍?xún)?yōu)于A(yíng)P-NSGA-Ⅱ算法，但是總體來(lái)說(shuō)，本算法在3個(gè)目標(biāo)函數(shù)上表現(xiàn)優(yōu)于其他算法。

圖6 距離與總時(shí)間的關(guān)系

圖7 距離與懲罰金額的關(guān)系

3.5 充電策略分析

電動(dòng)物流車(chē)在配送過(guò)程中，滿(mǎn)充情況下勢(shì)必增加單條路徑時(shí)間和總時(shí)間，時(shí)間的增加會(huì)帶來(lái)懲罰成本的增加?？紤]滿(mǎn)充電情況的執(zhí)行效果，根據(jù)充電站的位置和聚類(lèi)程度，把它當(dāng)成配送量為0的配送站進(jìn)行訪(fǎng)問(wèn)，不單獨(dú)考慮它為充電站，當(dāng)經(jīng)過(guò)充電站后進(jìn)行滿(mǎn)充操作以保證后續(xù)的行駛。為考察充電策略下的對(duì)目標(biāo)函數(shù)的影響，將充電站節(jié)點(diǎn)不規(guī)劃到多目標(biāo)的路徑中，以行駛距離消耗電量為條件，尋找最近的充電站，以滿(mǎn)足后續(xù)配送的方式進(jìn)行配送。

按照聚類(lèi)結(jié)果選取3條典型的配送子線(xiàn)路，按照滿(mǎn)充和部分充電來(lái)分析不同充電策略對(duì)配送的影響，結(jié)果如表3所示。

表3 滿(mǎn)充電和部分充電策略的比較

對(duì)于車(chē)輛編號(hào)1的線(xiàn)路，在滿(mǎn)充情況下，行駛距離為204.32 km，總用時(shí)為5.79 h，到達(dá)編號(hào)100的充電站后，執(zhí)行100%充電后進(jìn)行完成剩余線(xiàn)路；在部分充電情況下，編號(hào)1車(chē)輛的原始規(guī)劃路線(xiàn)為0→42→22→1→90→63→35→6→5→55→3→56→40→16→0，在到達(dá)編號(hào)56的配送點(diǎn)后，再去適配充電站，編號(hào)100的充電站加入節(jié)點(diǎn)56和40之間，電動(dòng)物流車(chē)的充電率為18.56%，行駛距離為177.83 km，用時(shí)為4.81 h。相同地，車(chē)輛編號(hào)2滿(mǎn)充和部分充電率為分別是100%和23.32%，距離分別為184.98 km和160.35 km，用時(shí)分別為5.20 h和5.09 h。車(chē)輛編號(hào)3在滿(mǎn)充設(shè)置下編號(hào)92被規(guī)劃到路徑中，在部分充電情況下，由于行駛距離小于150 km而不需要充電，他們的行駛距離分別是109.74 km和104.74 km，時(shí)間分別為3.39 h和2.62 h。

4 結(jié) 論

基于聚類(lèi)非支配排序算法(AP-NSGA-Ⅱ)來(lái)解決電動(dòng)物流車(chē)的多目標(biāo)路徑優(yōu)化問(wèn)題，建立了一種充電策略，通過(guò)設(shè)計(jì)加權(quán)AP聚類(lèi)劃分配送簇，避免了初始種群的隨機(jī)性和盲目性，同時(shí)，聚類(lèi)簇內(nèi)配送點(diǎn)的規(guī)模降低了非支配排序算法的運(yùn)行時(shí)間和復(fù)雜度，并根據(jù)充電站的分布和距離關(guān)系，電動(dòng)物流車(chē)執(zhí)行部分充電策略。最后，通過(guò)仿真實(shí)驗(yàn)證明該算法的有效性，比較了電動(dòng)物流車(chē)滿(mǎn)充和部分充電條件的差異性。