基于改進NSGA Ⅱ的時變路網污染路徑問題多目標優化

郭運聰， 韓曉龍

(上海海事大學物流科學與工程研究院，上海 201306)

0 引 言

近年來，世界各國密切關注節能減排問題。在2020年第75屆聯合國大會中，國家主席習近平提到：“中國將提高國家自主貢獻力度，采取更加有力的政策和措施，二氧化碳排放力爭于2030年前達到峰值，努力爭取2060年前實現碳中和。”據統計，交通運輸行業的碳排放量占全球碳排放量的22%，其中70%以上的碳排放量來源于公路運輸。隨著我國城市化進程的加快，交通擁堵問題愈發嚴重且具有很強的規律性。在擁堵時車輛行駛速度較低，頻繁的加速或減速造成油耗和二氧化碳排放量急劇增加，因此降低公路運輸能耗、減少碳排放量的關鍵在于合理規劃運輸車輛出發時間和路徑，在完成配送任務的同時減少碳排放量。

近年來，以節能減排為目標的污染路徑問題引起了學術界的關注，該問題是帶時間窗車輛路徑問題(vehicle routing problem with time windows，VRPTW)的延伸，主要研究考慮碳排放量的車輛路徑問題。BEKTA等[1]在2011年首次提出該問題，研究在最小油耗和最低駕駛員成本的綜合目標函數下，每條弧(i,j)的最優行駛速度。DEMIR等[2]研究最小油耗和最短配送時間的雙目標污染路徑問題，并采用自適應大鄰域搜索算法求解。DEMIR等[3]和SUZUKI[4]研究發現車速、載重、道路坡度和交通擁堵是影響油耗最重要的因素。MADEN等[5]發現隨著擁堵程度的增加，車輛的油耗和碳排放量將顯著增加。秦進等[6]提出基于節點時間窗變換以及速度和出發時間優化的兩階段算法，解決考慮擁堵情形的污染路徑問題。葛顯龍等[7]建立以最低成本和最短配送時間為目標的時間窗指派污染路徑問題優化模型，并設計混合遺傳禁忌搜索算法求解模型。

由于城市存在早晚交通高峰、路段限速、交通管制和意外事故等原因，城市交通路網具有時變特性，部分學者提出時變路網污染路徑問題，也稱時間依賴型污染路徑問題(time-dependent pollution routing problem，TDPRP)，該問題中大部分變量都隨道路交通信息的變化而改變，例如交通流狀況的改變會影響2個節點間的行駛速度和運輸車輛狀態。KUO[8]研究表明在時變路網情況下道路擁堵導致車輛緩慢行駛，對車輛的油耗和碳排放量產生重要影響。FRANCESCHETTI等[9]建立TDPRP的整數線性規劃模型，在固定行駛路線后再優化車輛出發時刻和行駛速度。趙志學等[10]將時間劃分為不同時段，用平均速度作為較短路段內的行駛速度，進而計算行駛時間。劉長石等[11]依據“先進先出”準則設計時間計算方法，引入交通擁堵指數，設計改進蟻群算法,有效避免交通擁堵。

綜上所述，國內外關于污染路徑問題已經產生一定的研究成果，為研究考慮交通擁堵的TDPRP提供了良好的基礎，但也存在一定的局限性，主要體現在以下4個方面：(1)已有的關于污染路徑問題的研究大多假設車輛行駛速度恒定，考慮交通擁堵的研究文獻較少；(2)已有的關于污染路徑問題的研究大多假設所有配送車輛在同一時刻從物流中心出發，關于車輛可以根據顧客需求和交通流量差異等情況在不同時刻出發的研究文獻較少；(3)已有的污染路徑問題研究普遍為車輛不?？?，采用車輛在配送過程中熄火停車等待作為擁堵規避策略的研究文獻較少；(4)傳統污染路徑問題的初始種群選擇通常隨機生成，在面對較大的種群規模時，種群質量極其不穩定，采用算法優化初始種群的研究文獻較少。

為克服上述局限性，本文考慮交通擁堵和不同時刻的交通流量狀況，車輛在配送過程中可熄火停車等待，以規避交通擁堵；同時以最低碳排放量和最短配送時間為雙目標，結合多目標優化理論，建立TDPRP多目標優化模型，并改進帶精英策略的非支配排序遺傳算法(elitist non-dominated sorting genetic algorithm，NSGA Ⅱ)進行求解；最后采用Solomon數據庫算例驗證模型和算法的有效性。

1 問題描述和假設

一個配送中心為城市不同區域的顧客配送貨物，其中顧客位置、需求量和時間窗均已知，不同時段城市道路交通擁堵狀況可從交通部門獲得。交通路網流量具有實時變化的特征，配送車輛的行駛速度根據道路交通狀況變化而改變。配送車輛可以根據顧客時間窗在不同時刻從配送中心出發，完成任務后返回配送中心。

為便于分析和研究，假設：(1)顧客位置、需求量和時間窗均已知，且不超過配送中心服務范圍和車輛的最大負載能力；(2)任意2個顧客點之間的最短路線均已知，且配送路線在配送過程中不能改變；(3)當配送車輛在行駛過程中遇到嚴重交通擁堵時，可在配送途中熄火停車等待，以規避交通擁堵；(4)車輛在行駛過程中產生碳排放量，在?？繒r間內發動機關閉，不產生碳排放量；(5)城市道路平整，不考慮道路坡度。

2 數學模型

2.1 擁堵規避策略

已有的污染路徑問題研究普遍為車輛不?？?，即車輛在從節點i行駛到節點j的過程中沒有等待或空閑，無論遇到什么情況，車輛都處于行駛狀態。當目標函數是最低碳排放量時，在交通擁堵時車輛低速行駛會對目標函數產生消極影響，故引入擁堵規避策略，規避交通擁堵，以降低車輛行駛過程中的碳排放量。圖1為車輛在3個相鄰時段的行駛速度分布，其中：時段1為中速時段，此時車輛行駛速度略低；時段2為低速時段，此時道路發生擁堵，車輛行駛速度最低；時段3為高速時段，此時車輛行駛速度只受道路最高速度限制。為達到最低碳排放量，設置高速時段的速度為最佳經濟速度。

圖1 時變路網車輛速度

車輛從節點i行駛到節點j的過程中,假設從時段1中的時刻t開始，假設車輛k無法在時段1剩下的時間內完成整段路程dij，并且必須在接下來幾個時段完成整段路程。圖2為車輛不采用擁堵規避策略時(A方案)的行駛距離與時間關系圖，在時刻t″到達節點j。圖3為車輛采用擁堵規避策略(B方案)，即在時段2停車等待，然后在時段3行駛，最終在時刻t′到達節點j。顯然，A方案中的車輛配送時間比B方案的短，即t″

圖2 不采用擁堵規避策略的行駛距離與時間關系圖

圖3 采用擁堵規避策略的行駛距離與時間關系圖

2.2 計算碳排放量

根據由DEMIR等[3]和FRANCESCHETTI等[9]提出的車輛油耗函數計算車輛在不同速度和負載下的碳排放量。車輛油耗函數為

F(v,f)=αv-1+βv2+γ+φf

(1)

式中：系數α、β、γ和φ與車輛參數有關；v表示車輛行駛速度；f表示車輛的負載；αv-1+βv2+γ表示車輛在空載行駛過程中產生的油耗；φf表示車輛負載行駛額外產生的油耗。以BARTH等[12]提出的柴油卡車為例，車輛的最大負載為10 t，為接近現實生活，車輛受到150 kg燃油容量的限制。圖4表示車輛在空載行駛時不同速度下的碳排放率。F(v,f)具體形式為

(2)

圖4 車輛在空載行駛時不同速度下的碳排放率

2.3 符號和變量

模型參數：{0}∪N為節點集合,0為配送中心N={1,2,…,n}為顧客集合；K為車輛集合，k∈K；H為時段集合，h∈H；fi為節點i的需求，i∈N；fijk為車輛k從節點i到節點j時的負載；fmax為車輛最大負載限制；dij為從節點i到節點j的距離；vijh為時段h車輛從節點i到節點j的速度；tijk為車輛k從節點i到節點j的配送時間；tijk,1為車輛k從節點i到節點j的行駛時間；tijk,2為車輛k從節點i到節點j的等待時間；c為燃油到CO2的轉化率；[TS,i,TE,i]為節點i的服務時間窗；[Tb,h,Te,h]為時段h的開始和結束時間；ts,i為節點i的服務時間；Ta,i為到達節點i的時刻；Tl,i為離開節點i的時刻。

決策變量：xijk為0-1變量，當車輛k從節點i到節點j時其值為1，否則為0；xijkh為0-1變量，當在時段h車輛k從節點i到節點j時其值為1，否則為0；yik為0-1變量，當節點i由車輛k服務時其值為1，否則為0。

2.4 TDPRP模型建立

以最低碳排放量和最短配送時間為目標構建TDPRP數學模型如下：

式(3)表示所有車輛的最低碳排放量；式(4)表示最短配送時間；式(5)表示每位顧客只能被服務1次；式(6)表示每輛車只能使用1次；式(7)表示車輛到達和離開的是同一顧客點；式(8)表示車輛必須從配送中心出發并返回配送中心；式(9)表示車輛不能超過其最大負載限制；式(10)表示在時段h車輛k從節點i到節點j的行駛時間；式(11)表示車輛k從節點i到節點j的配送時間；式(12)表示車輛到達節點i并服務之后才離開；式(13)表示配送車輛必須在顧客要求的時間窗內到達并服務顧客。

3 改進的NSGA Ⅱ

求解單目標問題時，可以求出唯一最優解，但求解多個目標函數時，由于目標矛盾，大多情況下并不存在唯一的最優解。DEB等[13]在2002年提出NSGA Ⅱ，克服NSGA的許多缺陷，例如：提出快速非支配排序(non-dominated sorting，NS)法，降低運算的復雜度；引入擁擠度計算，讓解的分布更加均勻；引入精英保留策略，提高種群多樣性。與傳統的多目標算法相比，NSGA Ⅱ在算法精度和計算效率方面均有所提高。經過十多年的實踐和應用，NSGA Ⅱ已成為人工智能領域的經典算法。

3.1 種群初始化

傳統污染路徑問題通常隨機產生初始種群，而當種群規模較大時，遺傳迭代的解的質量極其不穩定。XIAO等[14]研究表明初始種群的質量不僅影響算法迭代收斂速度，還會影響迭代最終解。種群個體聚集程度也會影響最終的優化結果，因此采用節約算法來生成初始種群。

采用自然數編碼方式為配送中心0和n位顧客進行編碼，顧客點用1，2，3，…，n表示，采用節約算法生成初始種群的步驟如下：

(1)為每位顧客分配1輛配送車輛。

(2)依次計算融合每2位顧客的距離節約值并降序排序，按照距離節約值排序依次判斷融合的2條路徑是否滿足時間窗約束和車輛負載約束。

(3)將滿足約束條件的距離節約值最大的2條路徑融合，重復上述操作生成初始種群。

3.2 NS

NS首先需要確定個體的Pareto等級和個體之間的支配關系。2個目標函數分別為f1(x)和f2(x)，首先計算所有個體的Pareto支配關系。Pareto支配關系是對于2個目標函數fi(x),i=1,2,任意給定2個個體xa和xb，如果同時滿足①對于?i∈{1,2}都有fi(xa)≤fi(xb)，②?i∈{1,2}使得fi(xa)

(1)在初始種群中找出非支配解，并將其Pareto等級定義為1。

(2)將Pareto等級定義為1的解從種群中刪除，剩下的種群中非支配解的Pareto等級定義為2。

(3)重復上述步驟可以得到該種群中所有個體的Pareto等級。

3.3 擁擠度計算

擁擠度是NSGA Ⅱ中非常重要的概念，用于計算某一特定個體周圍的種群密度，根據擁擠度可以有效調整種群多樣性。數值可以看作某特定個體i兩側相鄰個體作為對角線兩頂點形成的長方形的周長，表示為

(14)

由上式可知：個體i與相鄰個體越分散，該個體與相鄰個體的差異性越大，擁擠度越大；個體i與相鄰個體越密集，該個體與相鄰個體的相似性越高，擁擠度越小。對于Pareto等級相同、位于邊緣的個體，擁擠度定義為正無窮。位于內部的個體，擁擠度越大，表示該個體與相鄰個體的目標函數值的差異越大，即個體的多樣性越好。因此,NSGA Ⅱ在合并種群后的篩選過程中在Pareto等級相同的情況下，優先選擇擁擠度更大的個體有利于保護種群多樣性，防止出現局部最優解。

3.4 精英保留策略

將精英保留策略引入NSGA，擴大種群規模，組合父代種群和子代種群，共同競爭產生下一代父代種群，有利于保留父代中的優良個體，并在迭代中擴大種群規模。精英保留策略的步驟如下：

(1)將父代種群Pi和子代種群Qi合成種群Ri。

(2)將合成后的種群Ri進行非支配排序，按照Pareto等級從低到高的順序將種群放入新的父代種群Pi+1，直到某一等級的個體不能全部放入新的父代種群Pi+1。

(3)將該等級的個體根據擁擠度從大到小的順序排列，依次放入新的父代種群Pi+1，直到新的父代種群Pi+1被填滿。

該精英保留策略的優點在于最佳個體不會丟失，可以迅速提高種群水平并且在演化過程有更多的候選解，使得種群具有更佳的多樣性。

3.5 自適應交叉算子

在NSGA Ⅱ中，種群中個體的主要差異在于其所屬的Pareto等級。自適應交叉變異機制用來增加優秀個體的進化機會，提高算法的搜索能力。自適應交叉概率為

(15)

式中：pc,i表示個體i的自適應交叉概率；pc表示預設交叉概率；n表示種群數量；ri表示交叉個體的Pareto等級。

計算交叉概率使得Pareto等級越低的個體發生交叉的概率越高，使得種群有更高的進化概率。為避免交叉過程中產生超出車輛負載限制或者與顧客時間窗有沖突的子代，提高算法的收斂效果并保留優良基因，本文采用的交叉方法步驟(見圖5)如下：(1)選出參與交叉的父代1和父代2，從父代1中隨機選出不包含配送中心的路段作為交叉段；(2)找出父代2中對應父代1交叉片段的編號順序，作為父代2的交叉段；(3)將父代1的交叉段和父代2的交叉段進行互換，生成子代1和子代2。

圖5 交叉操作示意

3.6 自適應變異算子

個體i的自適應變異概率為

(16)

式中：pm表示預設交叉概率；n表示種群數量。

自然數編碼下基因代表顧客點，變異操作指該顧客點被替換成其他顧客點。采用交換變異，即在染色體上任意選擇2個不為0的基因位置，然后進行互換操作，互換后產生新的個體。具體變異方式見圖6。

圖6 變異操作示意

4 實驗設置和結果分析

4.1 實驗設置

由于目前沒有TDPRP的標準測試數據庫，案例數據采用國外著名學者Solomon的VRPTW數據庫中的算例。該算例分為3種類型：C類型(集中分布)、R類型(隨機分布)和RC類型(混合分布)。本文使用3種類型算例中顧客的坐標、需求量、時間窗和服務時間等數據作為測試數據。每個算例都有100位顧客和1個配送中心，每位顧客的服務時間為10 min。為符合測試要求，補充如下數據：

(1)設定配送中心的總工作時間為960 min，將工作時間分為16個時段，每個時段為60 min。最早工作時間為06:00，最晚工作時間為22:00。

(2)根據上海市交通出行網(http://www.jtcx.sh.cn/)歷史數據分析可得,工作日上海市市區內交通擁堵時刻普遍集中于08:00—10:00和18:00—20:00，將此時段規定為低速時段。將車輛速度按照早晚高峰時段劃分為高速、中速、低速等3個等級，高速設置為(50，75]km/h，中速設置為(25，50]km/h，低速設置為[10，25]km/h，具體的行駛速度在區間內隨機產生。

算法采用MATLAB R2018b編程，在CPU為AMD Ryzen 5 3600 3.6 GHz、內存為16 GB的計算機上運行，程序參數參考文獻[15]中所給出的最佳參數設置(種群規模為250、迭代次數為100、交叉概率為0.8、變異概率為0.1)。

4.2 實驗結果分析

4.2.1 算法有效性檢驗

為驗證算法的有效性，將改進的NSGA Ⅱ(記為INSGA Ⅱ)與NSGA進行比較。NSGA不采用精英保留策略和不進行擁擠度計算，初始種群隨機生成，交叉變異概率與NSGA Ⅱ的相同但在遺傳迭代中不進行自適應變化，并且所有車輛出發時刻均為0。選取算例RC208進行實驗，Pareto解集和每代種群最優的碳排放量和配送時間見圖7、圖8和表1。

圖7 Pareto解集前沿分布情況

圖8 每代種群最優的碳排放量和配送時間

表1 算法有效性檢驗

(1)與NSGA隨機生成初始種群相比,INSGA Ⅱ運用節約算法生成初始種群，其平均碳排放量降低40.51%，配送時間減少24.29%,說明在顧客規模較大的情況下，采用節約算法生成的初始種群更貼合實際，有利于提高遺傳算法迭代尋優的效率，加快算法收斂。

(2)由圖7可知，INSGA Ⅱ生成11個分布較為分散的Pareto解，NSGA生成6個分布較為集中的Pareto解,這說明算法中加入擁擠度計算有利于保護種群多樣性，防止出現局部最優解。

(3)INSGA Ⅱ較NSGA碳排放量降低25.40%，配送時間減少8.26%。由圖8可知INSGA Ⅱ在迭代到40次左右就已經收斂，說明精英保留策略和自適應選擇策略可以增強算法的局部搜索能力和全局尋優能力。

(4)INSGA Ⅱ運行1次的平均時間為42.29 s，說明INSGA Ⅱ可以為物流企業在較短時間內給出決策者滿意解。

4.2.2 擁堵規避策略結果分析

為驗證擁堵規避策略的有效性，采用的算例具有3種不同的分布類型和4種不同規模的顧客數量。計算結果見表2,其中:碳排放量指Pareto解集中所有解的碳排放量平均值;配送時間包含等待時間和行駛時間;優化比例是采用擁堵規避策略相對于不采用擁堵規避策略的結果。分析表2可知：

(1)不采用擁堵規避策略的車輛配送時間略低于采用擁堵規避策略的車輛配送時間，但是采用擁堵規避策略的碳排放量的優化效果更為明顯,碳排放量最多降低29.79%，最少降低18.90%，平均降低24.19%，由此可知本文提出的擁堵規避策略可以有效降低物流企業車輛的碳排放量。

(2)顧客數量越多，采用擁堵規避策略的優化效果越明顯。針對3種類型算例，擁堵規避策略都可以有效降低車輛碳排放量。隨著顧客數量的增加，平均配送時間增長率逐漸降低，3種分布模式下25位顧客平均配送時間增加10.80%，100位顧客平均配送時間增加4.94%，即顧客數量越多，擁堵規避策略對車輛平均配送時間的影響越小。因此，提出的擁堵規避策略更適合服務顧客數量較多的大型物流企業的物流配送。

4.2.3 車輛路徑算例分析

為驗證INSGA Ⅱ的穩定性，選取算例RC208進行驗證，運行10次，平均運行時間為42 s，說明算法能夠在較短的時間內得到車輛路徑規劃方案。隨機取Pareto解集中的1個解，進行車輛路徑分析，數據見表3。

分析表3可知：

(1)共使用7輛配送車輛，各車輛的配送任務有所差異，車輛2要服務18位顧客，配送任務最少的車輛3要服務10位顧客，其他車輛要服務15位顧客左右，這是因為車輛路徑規劃需要考慮顧客的需求、地理分布和時間窗要求以及車輛負載限制、時變路網、服務時間等。

表2 有無采用擁堵規避策略的結果比較

表3 RC208車輛路徑分析

(2)由表3出發時段可知，車輛2和車輛5在時段6出發，其他車輛都在時段1第0時刻從配送中心出發。如果所有車輛都在同一時刻從配送中心出發，則必然增加部分車輛等待時間，延長車輛的使用時間。因此,本文算法可以根據顧客需求合理規劃車輛出發時間，有效減少車輛等待時間和車輛使用時間，降低成本。

(3)物流企業應根據時變路網狀況和顧客時間窗要求等實際情況合理安排車輛出發時間，以降低車輛碳排放量和配送成本。

5 結 論

本文研究時變路網交通擁堵條件下的污染路徑問題，考慮實際物流過程中出現交通擁堵等情況，首先提出擁堵規避策略，然后引入基于時段劃分的路段行駛時間計算方法和車輛油耗函數。在此基礎上建立最低碳排放量和最短配送時間的雙目標污染路徑問題模型，并使用改進的NSGA Ⅱ進行求解，最后結合算例分析,得出以下結論：(1)擁堵規避策略可以有效降低車輛碳排放量并縮短車輛的行駛時間，但是會在較小程度上增加車輛使用時間。(2)改進的NSGA Ⅱ和本文提出的擁堵規避策略更適合顧客數量較多的大型物流企業的車輛路徑優化。(3)在調度配送車輛的過程中，物流企業應充分考慮時變路網信息、顧客時間窗、交通流量等實際情況，合理安排出發時間規避擁堵時段和規劃路線，從而降低碳排放量和配送成本。(4)物流企業在節能減排的同時會增加一定的配送成本，為促進綠色物流、保護環境，政府相關部門應該制定相應的綠色物流引導政策。

本文研究考慮的是規律性的交通擁堵情況，在未來會繼續研究偶發性的交通擁堵情況下的車輛實時調度問題及模糊需求和模糊時間窗對時變路網污染路徑問題的影響。