基于混合蟻群算法的異質(zhì)車隊(duì)低碳VRP研究

張明偉，李 波，屈曉龍，郭 盈

1.天津大學(xué)仁愛(ài)學(xué)院 管理系，天津 301636

2.天津大學(xué) 管理與經(jīng)濟(jì)學(xué)部，天津 300072

1 引言

隨著我國(guó)社會(huì)經(jīng)濟(jì)的快速發(fā)展和人民生活水平的提升，機(jī)動(dòng)車保有量也逐年攀升，隨之而來(lái)的汽車尾氣污染問(wèn)題也日益突出。目前，機(jī)動(dòng)車尾氣污染成為霧霾形成的重要原因之一已形成共識(shí)[1]。社會(huì)需求促進(jìn)了物流業(yè)的快速發(fā)展，載貨汽車總噸位也在不斷增加。與小型汽車相比，由于載貨汽車噸位大、使用率高、行駛時(shí)間和距離長(zhǎng)，所以，污染物的排放量也遠(yuǎn)大于其他小型車輛。如何優(yōu)化載貨汽車的配送調(diào)度方案，在對(duì)生產(chǎn)運(yùn)輸擾動(dòng)最小的條件下，減少碳排放量，對(duì)大氣污染治理具有十分重要的意義[2-3]。

為更加符合車輛運(yùn)輸?shù)膶?shí)際情況，本文從加入碳排放約束的車輛路徑優(yōu)化、異質(zhì)車隊(duì)和多路徑選擇（柔性路徑）三個(gè)方面對(duì)減少大氣污染的車輛路徑優(yōu)化模型進(jìn)行分析研究。

首先是加入碳排放約束的車輛路徑問(wèn)題。在車輛路徑問(wèn)題（Vehicle Routing Problem，VRP）模型中加入碳排放約束，不僅符合國(guó)家節(jié)能減排政策，也可以降低車輛油耗，節(jié)約成本。Demir等[4]對(duì)減少車輛碳排放量的綠色運(yùn)輸路徑優(yōu)化研究進(jìn)行了綜述，指出貨運(yùn)車輛排放了大量污染物，考慮低碳的VRP可以顯著降低車輛的溫室氣體排放，并指出車輛速度對(duì)單位碳排放量的影響比重遠(yuǎn)大于行駛距離和旅行時(shí)間。Hooshmand和Mirhassani[5]建立了時(shí)變網(wǎng)絡(luò)下的車輛碳排放模型，并將加油決策納入路線規(guī)劃，結(jié)果表明，模型優(yōu)化方案能夠有效減少碳排放量。Wang等[6]建立了兩級(jí)協(xié)同多中心車輛路徑問(wèn)題模型，提出了一種同時(shí)降低總運(yùn)行成本和減少二氧化碳排放的三相方法。Kancharla和Ramadurai[7]建立了考慮負(fù)載、速度和加速度的燃油消耗模型。使用行駛循環(huán)速度替代平均速度，結(jié)果表明可節(jié)省8%～12%的燃油，從而減少碳排放量。Roberto等[8]建立了一個(gè)減少碳排放量的綠色VRP模型，加入了車輛速度、坡度等變量，在不產(chǎn)生額外運(yùn)營(yíng)成本的情況下實(shí)現(xiàn)了碳減排。

其次，一個(gè)載貨車隊(duì)通常由多種不同類型的車輛構(gòu)成，不同類型的車輛在運(yùn)載能力、油耗成本等方面存在較大差異，一般稱之為異質(zhì)車隊(duì)。異質(zhì)車隊(duì)的VRP也是近年來(lái)研究熱點(diǎn)，與同質(zhì)車隊(duì)相比，異質(zhì)車隊(duì)相關(guān)的VRP優(yōu)化方案能夠明顯減少旅行成本和燃油消耗量，并減少溫室氣體的排放[9-12]。Susilawati等[13]以總行程成本和運(yùn)營(yíng)成本為目標(biāo)，建立了包含服務(wù)等級(jí)的異質(zhì)車隊(duì)車輛路徑規(guī)劃模型，優(yōu)化計(jì)算結(jié)果表明異質(zhì)車隊(duì)能夠有效減少燃料成本，減少空氣污染。葛顯龍等[14]建立了考慮碳排放因素的多車型車輛路徑模型。數(shù)值試驗(yàn)結(jié)果表明車速、車型和碳排放量約束對(duì)配送成本不可忽略。

第三個(gè)方面是柔性路徑。在VRP優(yōu)化過(guò)程中，當(dāng)兩個(gè)節(jié)點(diǎn)之間有多個(gè)路徑可供選擇時(shí)（柔性路徑），也可以有效減少燃料消耗和CO2排放，目前，這方面研究較少，Tadei等[15]較早提出了多路徑旅行推銷員模型，模型中每對(duì)節(jié)點(diǎn)之間有多個(gè)隨機(jī)旅行成本的路徑連結(jié)，通過(guò)建立模型仿真計(jì)算得到運(yùn)輸效率提高，總旅行成本降低的優(yōu)化方案；Huang等[16]提出了具有多路徑的柔性（TDVRP-PF）的時(shí)間相關(guān)車輛路徑問(wèn)題模型，以成本和旅行時(shí)間為優(yōu)化目標(biāo)進(jìn)行求解，結(jié)果表明該模型可以顯著降低燃油消耗量，減少大氣污染。

低碳VRP對(duì)滿足企業(yè)節(jié)能減排的需求和降低油耗成本具有十分重要意義，異質(zhì)車隊(duì)的建立與柔性路徑的選擇是實(shí)現(xiàn)低碳VRP的重要途徑。在實(shí)際運(yùn)輸過(guò)程中，異質(zhì)車隊(duì)與柔性路徑是普遍存在的，異質(zhì)車隊(duì)中不同載重車輛單位行駛里程的碳排放量不同，柔性路徑下車輛可以選擇不同長(zhǎng)度與速度的路徑到達(dá)客戶節(jié)點(diǎn)，從而產(chǎn)生不同的碳排放量。因此，異質(zhì)車隊(duì)與柔性路徑可以對(duì)VRP優(yōu)化過(guò)程中的碳排放量產(chǎn)生直接影響，并且在低碳VRP優(yōu)化過(guò)程中二者相互作用，單一方面優(yōu)化顯然難以得到全局最優(yōu)解。由于需要深入分析異質(zhì)車隊(duì)、柔性路徑與低碳VRP之間的相互作用關(guān)系，且集成優(yōu)化模型的構(gòu)建與求解均較為復(fù)雜，因此，目前尚未看到相關(guān)的文獻(xiàn)，但是以上相關(guān)研究成果為進(jìn)行此方面探索提供了可供借鑒的理論和方法。

本文在上述分析基礎(chǔ)上，提出了異質(zhì)柔性低碳VRP（Heterogeneous Flexible Low-carbon Vehicle Routing Problem，HFLVRP）模型，即多種不同車型、不同碳排放量的異質(zhì)車隊(duì)，進(jìn)行多路徑選擇的VRP模型。并且在模型中考慮了以下約束：（1）到訪不同客戶時(shí)，車輛的載貨重量隨貨物卸載而動(dòng)態(tài)變化，從而影響碳排放量。（2）在模型中，有些節(jié)點(diǎn)之間有多條路徑可供選擇，由于各個(gè)道路的質(zhì)量和暢通程度不同，所以每條路徑上車輛的平均行駛速度不同。（3）根據(jù)單條路徑不同路段的道路質(zhì)量和暢通程度，劃分多個(gè)路段，不同路段，車輛的平均行駛速度不同。

2 問(wèn)題描述

2.1 問(wèn)題說(shuō)明

HFLVRP可以描述為一個(gè)配送中心擁有一組不同車型、不同最大載重質(zhì)量的異質(zhì)車隊(duì)，每輛車從配送中心出發(fā)，為不同客戶提供派送服務(wù)，最后返回配送中心。配送中心及各個(gè)客戶節(jié)點(diǎn)之間的路徑具有不同行駛速度的限制，其中部分節(jié)點(diǎn)之間有多條路徑可供選擇。此外，部分路徑從起始到終點(diǎn)過(guò)程中會(huì)出現(xiàn)較大的車輛平均速度的變化（例如從市區(qū)到郊區(qū)再到高速公路），這里將同一條路徑中不同平均速度的部分劃分為多個(gè)路段進(jìn)行優(yōu)化。為更加符合運(yùn)輸過(guò)程中的實(shí)際情況，在HFLVRP模型中考慮了以下問(wèn)題：

（1）異質(zhì)車隊(duì)中不同車型的車輛，在不同行駛速度下的單位碳排放量不相同。英國(guó)交通研究所（U.K.Transport Research Laboratory）在研究報(bào)告[17]中指出，行駛速度是影響車輛碳排放量的最主要因素，不同車型的最低碳排放量，對(duì)應(yīng)的行駛速度不相同，見(jiàn)圖1所示。并且隨著減少碳排放技術(shù)的發(fā)展，車輛整體的碳排放量會(huì)有所降低，但是碳排放量隨車輛速度變化的關(guān)系基本不變，車輛總是有一個(gè)經(jīng)濟(jì)時(shí)速的范圍。

圖1 車輛的速度與碳排放量關(guān)系

由圖1可知，在異質(zhì)車隊(duì)中合理分配各種類型的車輛，比如在客戶收貨時(shí)間窗口允許的范圍內(nèi)，在限速較低的道路上使用載重較小的車輛配送，可使該路徑上的碳排放量有效減少。

（2）柔性路徑下，合理匹配異質(zhì)車隊(duì)中的車型與路徑，可降低碳排放量。柔性路徑下，對(duì)于兩個(gè)節(jié)點(diǎn)間存在多條不同速度路徑的情況，如果路徑長(zhǎng)度相等，載重量較大的車輛選擇平均速度較大的路徑運(yùn)輸，載重量小的車輛選擇平均速度較小的路徑運(yùn)輸，則可以有效減少總碳排放量。如圖2（a）和（b）所示。

同理，一輛車相同碳排放量下，其在兩條路徑上能夠行駛的距離不同。以最大載重量為35 t的車型為例，在平均速度為75 km/h的路徑上行駛，碳排放量為85.67 kg，行駛距離為100 km，如果在平均速度為50 km/h的路徑上行駛，產(chǎn)生同樣的碳排放量85.67 kg，行駛的距離則為113 km，如如圖2（c）所示。

實(shí)際運(yùn)輸中柔性路徑很常見(jiàn)，在滿足配送時(shí)間前提下，減少碳排放量可以通過(guò)合理調(diào)度車輛類型和選擇適合行駛速度的路徑來(lái)實(shí)現(xiàn)。

（3）兩個(gè)客戶節(jié)點(diǎn)之間，同一條路徑不同路段的平均速度不同。在實(shí)際運(yùn)輸過(guò)程中，同一車輛在兩個(gè)客戶節(jié)點(diǎn)之間行駛，可能經(jīng)過(guò)不同的路段（如高速公路，城市內(nèi)道路，郊區(qū)道路，縣級(jí)、鄉(xiāng)級(jí)公路等），由于各個(gè)路段的質(zhì)量、車流密度等不同，其平均行駛速度也不同，所以使用兩點(diǎn)之間運(yùn)輸距離的總平均速度來(lái)計(jì)算車輛的碳排放量不準(zhǔn)確，如圖2（d）所示，長(zhǎng)度為300 km的路徑，分路段計(jì)算碳排放量為258.21 kg，按照路徑總平均速度計(jì)算則為248.26 kg，兩者相差10 kg。

綜上，HFLVRP模型不僅分別考慮了異質(zhì)車隊(duì)、柔性路徑以及將路徑分為不同平均速度的路段，對(duì)降低VRP模型中的碳排放量的影響，還考慮了上述因素的互相作用對(duì)碳排放的影響，并在模型中對(duì)上述因素進(jìn)行了集成優(yōu)化，來(lái)實(shí)現(xiàn)在VRP中降低碳排放的目的。

2.2 符號(hào)說(shuō)明

（1）網(wǎng)絡(luò)和路徑：G=(V,E)為一個(gè)完全圖，表示配送網(wǎng)絡(luò)，V=(1,2,…,N)為節(jié)點(diǎn)集合，其中1表示配送中心，其余節(jié)點(diǎn)表示客戶；E表示弧集，E={(i,j)|(i,j∈V且i≠j)}；s表示節(jié)點(diǎn)i,j之間多條路徑S中的一條路徑，s∈(1,2,…,S)；r表示路徑s上不同速度的路段，r∈(1,2,…,R)；表示i,j節(jié)點(diǎn)之間的s路徑的r路段距離長(zhǎng)度。

（2）車輛和碳排放：K表示車輛的集合，k表示車輛，且?k∈K；qk表示車輛k的實(shí)時(shí)裝載量；Qk表示車輛k的最大裝載量；zi表示客戶節(jié)點(diǎn)i的需求量，配送中心需求量z1=0；v表示車輛的平均行駛速度；εk(v)表示車輛k在速度v下的單位碳排放量；εu(v)和εl(v)分別表示車輛空載和滿載情況下在速度v下的單位碳排放量；Φ(v)表示車輛在速度v下的負(fù)載因子。

（3）時(shí)間：在客戶節(jié)點(diǎn) j中，[σˉj,-σj]表示服務(wù)最早開(kāi)始和最晚結(jié)束的時(shí)間窗口要求，和表示車輛k實(shí)際到達(dá)和離開(kāi)的時(shí)刻。表示客戶節(jié)點(diǎn) j的服務(wù)時(shí)間，表示交接手續(xù)時(shí)間，表示卸載搬運(yùn)的時(shí)間。

2.3 條件假設(shè)

（1）一定速度下，單位碳排放量與車輛貨物重量的變化（如到達(dá)某一客戶卸載部分貨物）相關(guān)。

（2）車輛到達(dá)客戶后，服務(wù)時(shí)間包括手續(xù)交接時(shí)間和卸載貨物時(shí)間（與卸載量相關(guān)）。

（3）配送中心有足夠的各類型異質(zhì)車輛可供派遣。

（4）每個(gè)客戶都須要服務(wù)到，且只接受某一車輛的一次派送服務(wù)。

（5）每個(gè)客戶的需求量已知，且接受配送車輛到達(dá)有時(shí)間窗口限制。

（6）配送車輛有最大載重量限制，每次從配送中心出發(fā)，完成任務(wù)后返回配送中心。

3 模型構(gòu)建

3.1 模型優(yōu)化目標(biāo)

模型以碳排放總量、車輛總旅行時(shí)間和車輛旅行路程最小作為三個(gè)優(yōu)化目標(biāo)。碳排放量是車輛類型、車輛行駛速度、車輛負(fù)載和車輛行駛里程的函數(shù)。企業(yè)在車輛調(diào)度過(guò)程中較為關(guān)注節(jié)約成本，如燃料成本、人工成本等。碳排放量與燃料消耗成本直接相關(guān)，且呈正比關(guān)系[18]?？偮眯袝r(shí)間中除了車輛的行駛時(shí)間，還包含車輛到達(dá)客戶節(jié)點(diǎn)的服務(wù)時(shí)間。車輛的總旅行時(shí)間最小化可以減少人工成本，提高車輛利用率，提升客戶服務(wù)滿意度。車輛旅行里程最小可以有效減少車輛的燃料消耗，減少碳排放量。

由于每增加一輛運(yùn)輸車輛，碳排放總量將明顯增加，所以模型在優(yōu)化過(guò)程中會(huì)自動(dòng)減少車輛的使用，因此不必將車輛數(shù)量作為優(yōu)化目標(biāo)。

3.2 碳排放量的計(jì)算

一定類型車輛的單位碳排放量和燃料消耗相關(guān)，燃料消耗量和海拔、道路坡度、風(fēng)阻及載重量等密切相關(guān)，而這些因素均會(huì)影響車輛的行駛速度，因此，現(xiàn)有研究大多通過(guò)建立車輛行駛速度和碳排放之間的擬合函數(shù)來(lái)計(jì)算碳排放量[19]?？紤]到隨著減排技術(shù)的進(jìn)步，車輛整體碳排放量會(huì)不斷減少，但是碳排放與速度之間的關(guān)系基本不會(huì)發(fā)生變化，因此可以通過(guò)減排發(fā)展系數(shù)來(lái)調(diào)整不同時(shí)期車輛的碳排放量。本文使用英國(guó)交通研究所（U.K.Transport Research Laboratory），通過(guò)大量的試驗(yàn)分析給出的不同類型車輛速度與碳排放的擬合函數(shù)及相關(guān)參數(shù)[17]，車輛在空載時(shí)的碳排放量εu(g/km)與行駛速度v(km/h)的關(guān)系見(jiàn)公式（1）：

本文采用載重量分別為5、10、20、35 t的異質(zhì)車輛進(jìn)行配送運(yùn)輸，(a0,a1,…,a6)取值如表1所示。

表1 不同車輛空載碳排放量εu的相關(guān)系數(shù)

載貨汽車的碳排放量受載重質(zhì)量的影響較大，文獻(xiàn)[17]中通過(guò)負(fù)載因子Φ(v)來(lái)計(jì)算車輛在滿載情況下的碳排放量εl(v)，如公式（2）所示：

在忽略道路坡度影響的情況下，負(fù)載因子Φ是車輛速度v的函數(shù)，不同載重量的車輛負(fù)載因子與速度關(guān)系如圖3所示?？梢钥闯?，載重16 t以下車型的車輛，其負(fù)載因子與速度相關(guān)性較為明顯。負(fù)載因子函數(shù)的計(jì)算見(jiàn)公式（3），相關(guān)系數(shù)取值如表2所示。

圖3 不同車輛的負(fù)載因子與速度關(guān)系

表2 不同車輛負(fù)載因子Φ的相關(guān)系數(shù)

通過(guò)負(fù)載因子，可以計(jì)算車輛載重量隨卸載貨物而減少的動(dòng)態(tài)碳排放量，如公式（4）所示：

3.3 服務(wù)時(shí)間的計(jì)算

車輛在配送過(guò)程中，和分別表示車輛k到達(dá)和離開(kāi)客戶節(jié)點(diǎn)j的時(shí)刻，模型的時(shí)間優(yōu)化目標(biāo)是在保證客戶的需求時(shí)間窗口條件下，車輛總旅行時(shí)間以及車輛在客戶節(jié)點(diǎn)的服務(wù)時(shí)間之和最小。其中，服務(wù)時(shí)間包括到達(dá)客戶節(jié)點(diǎn)j的交接手續(xù)時(shí)間和裝卸搬運(yùn)時(shí)間。車輛k到達(dá)客戶節(jié)點(diǎn)j的服務(wù)時(shí)間的計(jì)算如公式（5）：

其中，裝卸搬運(yùn)時(shí)間與客戶j的需求量zj成正比，交接手續(xù)時(shí)間為一常數(shù)。

3.4 模型建立

模型的目標(biāo)函數(shù)為：

公式（6）為碳排放量?jī)?yōu)化目標(biāo)，表示車輛在所有旅行路徑上的碳排放量之和最?。还剑?）為完成時(shí)間優(yōu)化目標(biāo)，表示車輛行駛時(shí)間及客戶服務(wù)時(shí)間之和最??；公式（8）為旅行總路程最小。

目標(biāo)函數(shù)約束條件為：

公式（9）表示所有客戶節(jié)點(diǎn)都被訪問(wèn)到，且只訪問(wèn)1次；公式（10）表示任務(wù)車輛每次從配送中心出發(fā)，直到訪問(wèn)完成所有分派節(jié)點(diǎn)后，必須返回配送中心；公式（11）表示車輛在客戶節(jié)點(diǎn)完成任務(wù)后必須離開(kāi)；公式（12）表示車輛訪問(wèn)客戶節(jié)點(diǎn)的時(shí)間窗口約束；公式（13）表示不同車型車輛的最大載重量約束；公式（14）表示車輛行駛不同路徑的決策變量。

4 算法設(shè)計(jì)

旅行商問(wèn)題很早就被證明是NP完全問(wèn)題[20]，難以使用數(shù)學(xué)解析方法求得較優(yōu)解。旅行商問(wèn)題是VRP的特例，所以VRP也是NP完全問(wèn)題。本文提出的HFLVRP模型在傳統(tǒng)VRP基礎(chǔ)上增加了異質(zhì)車隊(duì)、柔性路徑、碳排放量、動(dòng)態(tài)負(fù)載、服務(wù)時(shí)間窗口等約束，使得模型的求解更加復(fù)雜。

智能優(yōu)化算法在求解NP完全問(wèn)題上具有很好的效果，其中，蟻群算法（Ant Colony Optimization，ACO）在求解旅行商問(wèn)題時(shí)效果較為明顯[21]。ACO是一種較新的分布式智能優(yōu)化算法，其特點(diǎn)是利用蟻群每次選擇信息素濃度較強(qiáng)的路徑來(lái)構(gòu)造可行解，算法帶有較強(qiáng)的記憶性。但是ACO每次都需要重新構(gòu)造路徑和更新信息素濃度，且容易出現(xiàn)停滯現(xiàn)象，因此算法效率較低，而且無(wú)法復(fù)制保留完整的較優(yōu)路徑的信息。粒子群算法（Particle Swarm Optimization，PSO）也是一種分布式智能優(yōu)化算法，其根據(jù)兩個(gè)極值：粒子最優(yōu)解 pbest和全局最優(yōu)解gbest來(lái)更新粒子，尋找較優(yōu)解。PSO具有簡(jiǎn)潔、收斂速度快，能夠保留復(fù)制較優(yōu)粒子路徑信息的特點(diǎn)，其粒子更新也具有方向性。

為加強(qiáng)算法的全局搜索能力，避免算法由于收斂速度過(guò)快或者陷入到局部最優(yōu)難以跳出，本文提出在ACPSO流程中增加模擬退火算法中的Metropolis抽樣準(zhǔn)則，當(dāng) f[pbesti(t)]

本文將ACO和PSO算法的特性結(jié)合，提出混合AC-PSO算法，使用ACO中的路徑信息素濃度更新方式作為PSO中粒子的更新方向，AC-PSO能夠提高算法的收斂速度，提高算法效率，同時(shí)保持了粒子更新的方向性。AC-PSO的流程如圖4所示。

圖4 混合AC-PSO運(yùn)算流程

4.1 算法編碼方式

算法中的粒子和可行解采用實(shí)數(shù)編碼，由于單個(gè)粒子涉及的信息較多，因此采用矩陣來(lái)表示不同信息種類，編碼方式如圖5所示。

圖5 實(shí)數(shù)編碼矩陣

實(shí)數(shù)編碼矩陣中第一行表示車輛經(jīng)過(guò)的路徑節(jié)點(diǎn)信息，其中“1”表示配送中心。如圖5中第一行[1，4，3，1，2，5，12，7，1，…]表示車輛從配送中心出發(fā)，經(jīng)過(guò)節(jié)點(diǎn)4和節(jié)點(diǎn)3，完成任務(wù)后返回配送中心，另一車輛經(jīng)過(guò)的節(jié)點(diǎn)是2、5、12、和7；第二、三行實(shí)數(shù)中“0”表示不同車輛單回路配送的分隔標(biāo)記，第二行中的20和35分別表示兩個(gè)回路車輛型號(hào)的最大載重量；第三行表示兩個(gè)節(jié)點(diǎn)之間有多條不同的路徑可以到達(dá)（柔性路徑），其中數(shù)字1、2和3表示選擇的兩點(diǎn)之間的第幾條路徑。例如節(jié)點(diǎn)1到2選擇了第2條路徑，節(jié)點(diǎn)5到12選擇了第3條路徑。

4.2 粒子的更新方式

在AC-PSO中，粒子更新既要保留一部分粒子的自身優(yōu)良特性，還要按照一定的方向性對(duì)粒子部分內(nèi)容進(jìn)行更新，本文采用單點(diǎn)更新的方式，即在粒子可行解中產(chǎn)生一個(gè)隨機(jī)點(diǎn)Rand，如圖6所示。為保證更新后的粒子仍然是可行解，將隨機(jī)點(diǎn)之前的部分直接復(fù)制保留，將隨機(jī)點(diǎn)之后的部分按照ACO中信息素濃度更新方式重新構(gòu)造，通過(guò)信息素濃度變化來(lái)保持粒子的方向性。

圖6 粒子更新方式

迭代過(guò)程中，對(duì)粒子Rand點(diǎn)之后的實(shí)數(shù)進(jìn)行重新編碼，車輛k經(jīng)過(guò)節(jié)點(diǎn)i到達(dá)節(jié)點(diǎn)j，并且選擇了路徑s的概率為ρksij(t)，其計(jì)算如公式（16）：

式中，allowedj'表示Rand點(diǎn)后面未訪問(wèn)的節(jié)點(diǎn)客戶，)表示能見(jiàn)度，是車輛k從節(jié)點(diǎn)i到節(jié)點(diǎn)j選擇路徑s行駛時(shí)，產(chǎn)生的碳排放量、行駛時(shí)間、節(jié)點(diǎn)j服務(wù)時(shí)間以及行駛的路徑長(zhǎng)度的函數(shù)，其計(jì)算方法如公式（17）：

式中，γ1、γ2和γ3為調(diào)節(jié)碳排放量、旅行里程和旅行時(shí)間之間數(shù)量級(jí)系數(shù)，λ1、λ2和λ3為三者之間的權(quán)重系數(shù)。τksij(t)表示車輛k從節(jié)點(diǎn)i出發(fā)到節(jié)點(diǎn)j選擇路徑s的信息素濃度，τksij(t)更新方式如公式（18）：

式中，W表示ACO中螞蟻的數(shù)量，μ表示路徑上信息素的蒸發(fā)速率，0<μ≤1。如果第w只螞蟻由節(jié)點(diǎn)i到節(jié)點(diǎn)j選擇了路徑s和車輛k，則：

4.3 適應(yīng)度函數(shù)

HFLVRP是多目標(biāo)優(yōu)化模型，存在Pareto解集，因此在構(gòu)造適應(yīng)度函數(shù)時(shí)需要考慮三個(gè)優(yōu)化目標(biāo)的數(shù)量級(jí)關(guān)系和三者的權(quán)重系數(shù)。本文采用了自適應(yīng)的方式調(diào)整數(shù)量級(jí)關(guān)系的適應(yīng)度函數(shù)f(t)，如公式（20）所示：

式中C、T和D分別表示可行解t的碳排放總量、總旅行時(shí)間和總旅行路徑長(zhǎng)度。

5 仿真算例

5.1 算例數(shù)據(jù)

為驗(yàn)證HFLVRP模型的適用性和算法的有效性，本文采用計(jì)算機(jī)隨機(jī)算例數(shù)據(jù)的方法，在直徑300 km區(qū)域內(nèi)，隨機(jī)產(chǎn)生30個(gè)節(jié)點(diǎn)的坐標(biāo)，如表3，其中節(jié)點(diǎn)1為配送中心，坐標(biāo)（300，300），在區(qū)域中心。其他29個(gè)節(jié)點(diǎn)為客戶節(jié)點(diǎn)，其需求量為1～15的隨機(jī)正整數(shù)?？蛻艄?jié)點(diǎn)接受車輛到達(dá)時(shí)刻為一個(gè)時(shí)間窗口，例如（7，12）表示上午7點(diǎn)到中午12點(diǎn)之間可以接受服務(wù)，即車輛7點(diǎn)之后可以到達(dá)，12點(diǎn)之前必須離開(kāi)。（0，24）則表示任意時(shí)間均可接受服務(wù)。

表3 隨機(jī)產(chǎn)生節(jié)點(diǎn)的坐標(biāo)、需求量和時(shí)間窗口

這里假設(shè)所有車輛在早上6點(diǎn)出發(fā)，并且貨物需要在6點(diǎn)開(kāi)始之后的24小時(shí)之內(nèi)完成配送。

假設(shè)節(jié)點(diǎn)A到B與節(jié)點(diǎn)B到A的路況一致，根據(jù)節(jié)點(diǎn)坐標(biāo)計(jì)算兩點(diǎn)間直線距離，則30個(gè)節(jié)點(diǎn)共產(chǎn)生435條路徑，將這些路徑作為兩節(jié)點(diǎn)間初始的第一條路徑，再根據(jù)這些路徑隨機(jī)生成柔性路徑。首先假設(shè)所有路徑的平均行駛速度均為75 km/h，且只有一條路徑，然后在這些路徑中隨機(jī)選取其中10%，共44條路徑（如表4）產(chǎn)生以下變化：

表4 柔性路徑的速度和路段長(zhǎng)度

（1）有些路徑行駛速度改變，變化幅度為35～70之間5的整數(shù)倍，例如表4中的路徑1-2、1-23等。

（2）有些路徑劃分為了不同速度的路段，例如表4中的路徑3-23，速度“55（24），75（70），35（6）”表示路徑分為了三段，第一段行駛速度為55 km/h，路段長(zhǎng)度占總路徑長(zhǎng)度的24%；第二段行駛速度為75 km/h，路段長(zhǎng)度占總路徑長(zhǎng)度的70%；第三段行駛速度為35 km/h，路段長(zhǎng)度占總路徑長(zhǎng)度的6%。

（3）某些節(jié)點(diǎn)之間存在柔性路徑，即有二條或者三條平均行駛速度不同的路徑，例如表4中路徑1-9、1-15等。柔性路徑的長(zhǎng)度絕大部分也不同，其第一條路徑為兩點(diǎn)間直線距離，第二條或第三條路徑的長(zhǎng)度按照第一條路徑的±15%隨機(jī)產(chǎn)生，如表5所示。

還有一些路徑混合了上述3種變化，為了測(cè)算一條路徑劃分路段與不劃分路段，車輛在碳排放量與行駛時(shí)間方面的差別，對(duì)上述算例中的含有分路段的路徑進(jìn)行了計(jì)算分析。同一條路徑，分別按照劃分路段和不劃分路段的方式進(jìn)行計(jì)算。車輛按照路徑中所有路段的平均速度行駛，分別選擇載重量為5、10、20和30 t的車輛經(jīng)過(guò)所有路段，計(jì)算結(jié)果表明，與劃分路段相比較，若不劃分路段，相同的行駛里程，車輛碳排放量差別的絕對(duì)值為3.58%～4.61%，車輛行駛時(shí)間差別為4.25%。測(cè)算結(jié)果表明在模型中如果不劃分路段，會(huì)對(duì)優(yōu)化結(jié)果會(huì)產(chǎn)生一定影響。

表5 柔性路徑的第二、三條路徑長(zhǎng)度 km

5.2 仿真結(jié)果

本文以Matlab7.0為工具，對(duì)HFLVRP模型和ACPSO進(jìn)行編程和仿真運(yùn)算。碳排放、旅行時(shí)間和里程最小3個(gè)優(yōu)化目標(biāo)權(quán)重系數(shù)λ1、λ2和λ3取值均為1。服務(wù)手續(xù)交接時(shí)間取值為0.35 h，裝卸搬運(yùn)時(shí)間取值為0.2 h/t。運(yùn)算規(guī)模及模型約束條件等因素的變化會(huì)對(duì)算法的參數(shù)取值產(chǎn)生較大影響，本文采用均勻設(shè)計(jì)試驗(yàn)[22]的方法來(lái)確定AC-PSO中參數(shù)取值，初始種群規(guī)模設(shè)置為600，在更新迭代過(guò)程中，權(quán)重α和β均取值為1，信息素蒸發(fā)率μ取值為0.55，初始退火溫度Γ初始取值為2 000，算法的終止條件為：當(dāng)進(jìn)行1 000次迭代運(yùn)算后，算法的適應(yīng)度函數(shù)值不再變化，則算法終止。

對(duì)HFLVRP模型優(yōu)化仿真30次，優(yōu)化結(jié)果取平均值，C、T、D及車輛數(shù)如表6所示。

表6 HFLVRP模型優(yōu)化結(jié)果

取其中一個(gè)HFLVRP模型優(yōu)化結(jié)果進(jìn)行分析，車輛行駛路徑及使用車型如表7所示，其中“多路徑”列中的數(shù)字1、2、3分別表示經(jīng)過(guò)了柔性路徑的第一、二、三條路徑。配送車輛從6點(diǎn)開(kāi)始出發(fā)，到達(dá)和離開(kāi)節(jié)點(diǎn)的時(shí)刻如表8所示（大于24為第二天到達(dá)）。

表8 車輛到達(dá)和離開(kāi)節(jié)點(diǎn)的時(shí)刻

多目標(biāo)函數(shù)的Pareto解和優(yōu)化目標(biāo)的權(quán)重系數(shù)相關(guān)，HFLVRP模型中碳排放、旅行時(shí)間和里程最小3個(gè)優(yōu)化目標(biāo)，其權(quán)重系數(shù)主要和運(yùn)輸企業(yè)對(duì)三者的重視程度有關(guān)，為了給企業(yè)提供不同權(quán)重下三個(gè)優(yōu)化目標(biāo)的求解范圍參考，本文采用文獻(xiàn)[23]中的方法求解分析HFLVRP模型的多目標(biāo)Pareto解集。即在算法中創(chuàng)建一個(gè)Pareto非支配解集合，根據(jù)Pareto支配關(guān)系對(duì)種群進(jìn)行帕累托分級(jí)，將級(jí)別最高的解放入Pareto非支配集合中，若非支配解集規(guī)模超過(guò)設(shè)定值，則進(jìn)行修剪。利用上述方法求解HFLVRP模型的Pareto解集，得出10個(gè)Pareto非支配解，如表9所示。并求得碳排放、旅行時(shí)間和里程三個(gè)優(yōu)化目標(biāo)的極小值分別為4 002.6 kg、106.4 h和4 926.7 km。

表9 Pareto非支配解集

為了驗(yàn)證AC-PSO算法有效性，對(duì)5.1節(jié)中的算例數(shù)據(jù)，分別使用遺傳算法（Genetic Algorithm，GA）、PSO算法和ACO三種方法進(jìn)行仿真運(yùn)算，采用CPU 3.2 GHz，內(nèi)存8 GB，64位Windows7操作系統(tǒng)的計(jì)算機(jī)，GA中采用實(shí)數(shù)編碼，交叉概率0.2，變異率0.05；PSO中慣性權(quán)重0.73，兩個(gè)加速因子均為1.21；ACO算法取值與ACPSO相同。計(jì)算結(jié)果取30次計(jì)算的平均值，如表10所示，可以看出AC-PSO在計(jì)算耗時(shí)和標(biāo)準(zhǔn)差方面繼承了PSO和ACO的優(yōu)點(diǎn)，綜合計(jì)算結(jié)果表明AC-PSO算法對(duì)HFLVRP模型優(yōu)化效果較好。

表10 HFLVRP模型算法效果比較

為進(jìn)一步對(duì)比分析算法的有效性，本文從TSPLIB中選取3個(gè)經(jīng)典實(shí)例進(jìn)行測(cè)試，算法參數(shù)取值與前面HFLVRP模型中采用的對(duì)比算法相同，結(jié)果如表11所示。

表11 TSP模型算法效果比較

由表11可以得出，AC-PSO對(duì)TSP以及VRP問(wèn)題的優(yōu)化計(jì)算具有較好效果。

為了驗(yàn)證HFLVRP模型的有效性，本文對(duì)同質(zhì)車隊(duì)與異質(zhì)車隊(duì)、柔性路徑與非柔性路徑、固定負(fù)載與動(dòng)態(tài)負(fù)載分別進(jìn)行了仿真對(duì)比分析。每個(gè)仿真模型的結(jié)果均取30次仿真的平均值。

（1）在HFLVRP模型中保持其他條件不變，采用車輛載重量均為20 t和均為35 t的同質(zhì)車隊(duì)（由于部分節(jié)點(diǎn)需求量大于10 t，因此同質(zhì)車隊(duì)不能采用10 t及以下車型運(yùn)輸）。仿真優(yōu)化結(jié)果如表12所示。

表12 同質(zhì)車隊(duì)仿真優(yōu)化結(jié)果

由表12可以得出，與異質(zhì)車隊(duì)仿真結(jié)果相比，采用載重量為20 t和35 t的同質(zhì)車隊(duì)運(yùn)輸，仿真優(yōu)化后行駛的總時(shí)間和總里程變化不明顯，但是碳排放量分別增加了14.9%和6.1%，并且載重量20 t的車隊(duì)需要約9輛車運(yùn)輸。

（2）其他條件不變，將兩節(jié)點(diǎn)間隨機(jī)選擇柔性路徑，改為只選擇多路徑中最短的一條進(jìn)行運(yùn)輸，仿真優(yōu)化結(jié)果如表13所示。

表13 最短路徑運(yùn)輸仿真優(yōu)化結(jié)果

由表13可以看出，多路徑中選擇最短路徑運(yùn)輸，雖然車輛旅行里程數(shù)略有減少，但是與HFLVRP中的柔性路徑相比，碳排放量增加了6.6%。

（3）HFLVRP模型中，將車輛重量隨貨物卸載而動(dòng)態(tài)變化的動(dòng)態(tài)負(fù)載，改為兩類固定負(fù)載：一類固定負(fù)載取值為平均負(fù)載，即車輛出發(fā)時(shí)貨物重量的一半，另一類固定負(fù)載取值為車輛的最大載重量，模型中的其他條件均保持不變，然后進(jìn)行仿真優(yōu)化計(jì)算，結(jié)果如表14所示。

表14 固定負(fù)載仿真優(yōu)化結(jié)果

由表14可以看出，HFLVRP模型中動(dòng)態(tài)負(fù)載碳排放量與固定負(fù)載中的平均負(fù)載和最大負(fù)載相比較，分別降低了3.4%和6.1%。因?yàn)椋绻捎脛?dòng)態(tài)負(fù)載，在模型優(yōu)化過(guò)程中可以通過(guò)調(diào)整車輛行駛路徑，在負(fù)載較大時(shí)選擇較短路徑優(yōu)先配送，負(fù)載較小時(shí)再選擇較長(zhǎng)路徑配送，所以能夠降低整體碳排放量。

綜上，在模型中綜合考慮異質(zhì)車隊(duì)、柔性路徑、動(dòng)態(tài)負(fù)載及劃分路段等因素、變量，在旅行時(shí)間、里程變化不大的情況下，能夠明顯降低碳排放量。

6 結(jié)束語(yǔ)

HFLVRP模型針對(duì)如何減少貨運(yùn)車輛在配送過(guò)程中的碳排放問(wèn)題，結(jié)合生產(chǎn)運(yùn)輸實(shí)際，在優(yōu)化過(guò)程中綜合考慮了異質(zhì)車隊(duì)、柔性路徑、動(dòng)態(tài)負(fù)載等因素，并作為優(yōu)化的關(guān)鍵變量，即載重量大、裝載貨物多的車輛選擇速度較快的路徑，載重量較小、裝載貨物少的車輛選擇速度較慢的路徑，從而減少整個(gè)運(yùn)輸過(guò)程中的碳排放量。模型以碳排放量、旅行時(shí)間和旅行路程作為多優(yōu)化目標(biāo)，并且設(shè)定了配送時(shí)間窗口和劃分路段計(jì)算行駛速度的約束條件。

蟻群算法與粒子群算法都是帶有記憶性的群搜索算法，本文提出AC-PSO使用蟻群算法的信息素強(qiáng)度更新方式來(lái)保持種群的記憶性，同時(shí)結(jié)合了粒子群算法快速收斂的特性，針對(duì)HFLVRP設(shè)計(jì)了編碼解碼方式，最后，通過(guò)算例仿真計(jì)算對(duì)比分析，結(jié)果表明模型中考慮異質(zhì)車隊(duì)、柔性路徑和動(dòng)態(tài)負(fù)載可以在總旅行時(shí)間和總旅行路程變化不大情況下，使碳排放總量顯著降低。

本文模型未考慮不同載重量的車輛轉(zhuǎn)運(yùn)問(wèn)題。后續(xù)研究可以考慮在速度較快的道路上使用載重量大的車輛運(yùn)輸，當(dāng)行駛到速度較慢的道路時(shí)，在轉(zhuǎn)運(yùn)站將貨物派送多個(gè)載重量較小的車輛，以減少配送車輛的碳排放總量。城市配送由于擁堵程度不同，可以劃分為不同速度的時(shí)區(qū)，可以通過(guò)合理組合時(shí)區(qū)來(lái)達(dá)到減少車輛碳排放的目的[24]，后續(xù)也可以考慮在時(shí)變城市配送模型中，研究HFLVRP模型的調(diào)度問(wèn)題。