基于混合蟻群算法的冷鏈電動(dòng)汽車車輛路徑問題

劉志碩，劉若思，陳哲

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

0 引言

隨著居民生活水平的提高，人們對(duì)瓜果蔬菜、禽蛋肉奶等生鮮產(chǎn)品的需求與日俱增。然而，冷鏈物流對(duì)環(huán)境和能源會(huì)產(chǎn)生更大的負(fù)面影響［1］。由于裝載貨物的特殊性，在運(yùn)送途中必須提供低溫環(huán)境以維持貨品的質(zhì)量，這無(wú)疑會(huì)消耗更多的能源和排放更多尾氣。有數(shù)據(jù)顯示，冷藏燃油車行駛過(guò)程中排放的尾氣大約是普通燃油貨車的1.3 倍。由此可見，隨著冷鏈物流市場(chǎng)規(guī)模的不斷擴(kuò)大，其導(dǎo)致的環(huán)境污染和能源消耗問題也會(huì)愈演愈烈。

交通是溫室氣體排放的主要領(lǐng)域之一，隨著我國(guó)私家車保有量的不斷提升，大力發(fā)展“零碳排放”的電動(dòng)汽車是降低交通碳排放的有力手段。電動(dòng)汽車與燃油車相比，具有環(huán)境污染小的特點(diǎn)，將電動(dòng)汽車應(yīng)用于冷鏈物流領(lǐng)域承擔(dān)運(yùn)輸和配送任務(wù)，對(duì)于緩解環(huán)境污染和降低化石能源消耗至關(guān)重要［2］。我國(guó)已經(jīng)有一些冷鏈物流企業(yè)開始嘗試采用電動(dòng)冷藏車開展冷凍食品的末端配送。如何制定科學(xué)合理的配送方案來(lái)解決配送成本高、客戶服務(wù)水平低等難題對(duì)基于電動(dòng)汽車的冷鏈物流配送業(yè)務(wù)來(lái)說(shuō)顯得尤為重要。

本文將電動(dòng)汽車的車輛路徑問題（Vehicle Routing Problem，VRP）與冷鏈物流加以結(jié)合，建立了數(shù)學(xué)模型，設(shè)計(jì)了一種混合蟻群（Hybrid Ant Colony Optimization，HACO）算法求解。

本文的主要工作為：1）場(chǎng)景創(chuàng)新，順應(yīng)綠色物流的發(fā)展，著眼電動(dòng)冷鏈車的路徑規(guī)劃問題，將電動(dòng)汽車路徑優(yōu)化問題與冷鏈物流加以結(jié)合；2）模型創(chuàng)新，針對(duì)研究主體，建立了混合整數(shù)規(guī)劃模型，在目標(biāo)函數(shù)中創(chuàng)新考慮了冷鏈電動(dòng)汽車的制冷成本。設(shè)計(jì)混合蟻群算法進(jìn)行求解并設(shè)計(jì)了適合社會(huì)充電站的轉(zhuǎn)移規(guī)則以及4 種局部?jī)?yōu)化算子，通過(guò)實(shí)驗(yàn)驗(yàn)證了所提算法的性能。

1 相關(guān)工作

1959 年Dantzig等［3］首次提出了車輛路徑問題（VRP），該問題是物流研究領(lǐng)域中一個(gè)具有十分重要理論和現(xiàn)實(shí)意義的問題。目前，國(guó)內(nèi)外已對(duì)車輛路徑問題作了大量而深入的研究。求解性能較好的啟發(fā)式算法主要有模擬退火算法、遺傳算法、禁忌搜索（Tabu Search，TS）算法、粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法、大規(guī)模鄰域搜索算法等。

1996 年Dorigo等［4］提出了蟻群（Ant Colony Optimization，ACO）算法，蟻群算法是一種用來(lái)搜索優(yōu)化路線的幾率型算法。它的開發(fā)受到自然界中螞蟻智能行為的啟示，有關(guān)學(xué)者汲取螞蟻群體的多樣性和內(nèi)部存在的正反饋機(jī)制，開創(chuàng)了具有搜索能力強(qiáng)、收斂速度快等特點(diǎn)的啟發(fā)式算法。蟻群算法在VRP 中得到了廣泛的應(yīng)用。Reed等［5］在研究垃圾回收的車輛路徑問題中，提出使用蟻群算法來(lái)求解多隔艙的車輛路徑問題。Li等［6］設(shè)計(jì)了改進(jìn)的蟻群算法來(lái)解決多車場(chǎng)、多目標(biāo)的車輛路徑問題，提出了一種基于收益最大化，成本、時(shí)間和排放量最小化的多車場(chǎng)綠色車輛路徑問題，設(shè)計(jì)改進(jìn)的蟻群算法對(duì)問題進(jìn)行了有效求解。Guo等［7］設(shè)計(jì)了改進(jìn)的混合蟻群算法，以最小化總里程為目標(biāo)求解多車廂車輛路徑問題，并設(shè)計(jì)了基于加速搜索和先動(dòng)策略的兩種變鄰域下降技術(shù)提高數(shù)據(jù)挖掘能力。Mutar等［8］提出一種改進(jìn)的蟻群算法求解帶車輛能力約束的車輛路徑問題。

從冷鏈車輛路徑問題（Refrigerated Electric Vehicle Routing Problem，REVRP）來(lái)看，Osvald等［9］考慮到新鮮蔬菜易變質(zhì)的特點(diǎn)，提出有時(shí)間窗和行程時(shí)間約束下的冷鏈車輛路徑問題，并設(shè)計(jì)了禁忌搜索算法求解。Amorim等［10］為解決葡萄牙食品分銷公司面臨的復(fù)雜的冷鏈車輛路徑問題，構(gòu)建了多時(shí)間窗的異構(gòu)車隊(duì)路徑規(guī)劃問題的模型，并使用自適應(yīng)大鄰域搜索算法求解。Abdi等［11］考慮去送回收作業(yè)的生鮮產(chǎn)品VRP，以同時(shí)提貨和分貨提高供應(yīng)鏈效率，以多產(chǎn)品多周期的形式實(shí)現(xiàn)總成本最小化和客戶服務(wù)最大化，提出了考慮環(huán)境因素和碳排放的車輛路徑問題并求解。Zulvia等［12］提出優(yōu)化運(yùn)營(yíng)成本、變質(zhì)成本、碳排放和客戶滿意度的易腐產(chǎn)品車輛路徑問題，采用多目標(biāo)梯度進(jìn)化算法求解模型。Li等［13］建立綠色生鮮食品物流異質(zhì)車隊(duì)車輛路徑問題模型，提出自適應(yīng)模擬退火變異遺傳算法求解，同時(shí)降低了能源和燃料的消耗。

從電動(dòng)汽車車輛路徑問題來(lái)看，Schneider等［14］針對(duì)時(shí)間窗約束下的電動(dòng)汽車路徑問題，考慮了充電站的因素，構(gòu)建了以總出行距離最短為優(yōu)化目標(biāo)的數(shù)學(xué)模型，并提出一種將變鄰域搜索（Variable Neighborhood Search，VNS）算法與禁忌搜索啟發(fā)式算法相結(jié)合的混合啟發(fā)式算法。Goeke等［15］研究了傳統(tǒng)汽車和電動(dòng)汽車的混合車隊(duì)下帶時(shí)間窗的路徑優(yōu)化問題。揭婉晨等［16］研究了帶有時(shí)間窗的電動(dòng)汽車路徑問題，考慮多車型的問題設(shè)計(jì)，建立了混合整數(shù)規(guī)劃模型并以分支定價(jià)算法求解。Gatay等［17］研究了部分充電策略下的電動(dòng)汽車路徑優(yōu)化問題。Zhang等［18］考慮電動(dòng)汽車行駛途中需訪問充電站，以能耗最小為目標(biāo)建立了數(shù)學(xué)模型，并提供了電動(dòng)汽車能耗的綜合計(jì)算，提出基于蟻群算法的元啟發(fā)式算法進(jìn)行求解。Macrina等［19］提出電動(dòng)汽車和傳統(tǒng)內(nèi)燃機(jī)汽車組成的混合車隊(duì)路線問題，考慮了電動(dòng)汽車的充電時(shí)間窗口，設(shè)計(jì)一種迭代局部搜索啟發(fā)式算法解決問題。Keskin等［20］提出帶有軟時(shí)間窗的充電站排隊(duì)時(shí)間混合整數(shù)線性規(guī)劃模型，設(shè)計(jì)了結(jié)合自適應(yīng)大鄰域搜索和混合整數(shù)線性規(guī)劃的數(shù)學(xué)方法進(jìn)行求解。Karakati?［21］提出了一個(gè)兩層遺傳算法，求解帶時(shí)間窗的多車場(chǎng)車輛路徑問題，進(jìn)一步縮小了理論與實(shí)際的差距。

從上述分析可以看出，對(duì)于冷鏈車輛路徑問題和電動(dòng)汽車路徑問題都開展了許多研究。然而，盡管在冷鏈物流行業(yè)已經(jīng)有一些企業(yè)采用電動(dòng)汽車配送冷凍食品等需要冷藏的商品，但尚沒有研究考慮將電動(dòng)汽車應(yīng)用于冷鏈物流配送優(yōu)化。究其原因，可能是電動(dòng)汽車總體上來(lái)講仍是一個(gè)新事物，無(wú)論技術(shù)上還是應(yīng)用上，還存在諸多不足或不便之處，在冷鏈物流行業(yè)應(yīng)用還非常少，因而還沒有引起學(xué)者的足夠重視。本文將電動(dòng)汽車與冷鏈物流配送相結(jié)合，考慮電動(dòng)汽車能耗特點(diǎn)和社會(huì)充電站的充電需求，提出了基于電動(dòng)汽車的冷鏈車輛路徑問題，建立了以配送總成本最小為優(yōu)化目標(biāo)的數(shù)學(xué)模型，并設(shè)計(jì)了一種混合蟻群算法進(jìn)行求解。

2 問題描述和模型建立

2.1 問題描述

REVRP 可描述為：一個(gè)生鮮配送中心派出電動(dòng)冷鏈車向V個(gè)超市配送同一溫區(qū)的生鮮商品。車輛從配送中心出發(fā)時(shí)完全處于滿電狀態(tài)。車輛的容量為C，續(xù)駛里程有限，中途可能需要充電，充電采用社會(huì)公共充電站，充電方式為快充，且一次充滿，已知配送區(qū)域里分布有F個(gè)充電站。在此問題中，假設(shè)車輛維持行駛狀態(tài)的電能消耗速度與行駛里程成正比，為h/km，車廂維持低溫環(huán)境所需的電能為l/h，要求制定最優(yōu)的配送方案以使得配送總成本最低。

基本假設(shè)：1）配送中心只有一個(gè)，所有車輛出發(fā)之前在配送中心充滿電，中途只能充電一次，且一次充滿；2）每輛車只允許配送一趟；3）各配送點(diǎn)的需求量已知，且不超過(guò)車輛的容量；4）每個(gè)配送點(diǎn)只由一輛車配送一次；5）配送貨物類型單一；6）配送車輛車型單一；7）配送中心和各配送點(diǎn)無(wú)時(shí)間窗要求；8）配送點(diǎn)和充電站的位置不變；9）配送車輛勻速行駛；10）充電速度恒定；11）為提供車輛動(dòng)力所消耗的電能與運(yùn)輸里程成正比；12）制冷所消耗的電能與制冷的時(shí)間成正比。

2.2 模型建立

為便于模型的建立，設(shè)定相關(guān)的集合、參數(shù)和決策變量，如表1～2 所示。

表1 集合和參數(shù)設(shè)置Tab.1 Setting of sets and parameters

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

REVRP 以配送總成本最小為目標(biāo)函數(shù)，由固定成本Z1和可變成本構(gòu)成，其中可變成本包含運(yùn)輸成本Z2和制冷成本Z3。

1）固定成本。

為完成配送任務(wù)，企業(yè)需要投入資金來(lái)維持整個(gè)配送流程的運(yùn)行，包括車輛購(gòu)置、支付員工工資、管理運(yùn)營(yíng)等。這些資金被分配到每輛配送車輛上，則固定成本如下：

2）運(yùn)輸成本。

由于采用電動(dòng)冷鏈車進(jìn)行配送，維持車輛動(dòng)力所消耗的電能構(gòu)成配送過(guò)程中的運(yùn)輸成本，其費(fèi)用在車輛行駛時(shí)產(chǎn)生，用公式表示為：

3）制冷成本。

為保證商品的質(zhì)量，需提供對(duì)應(yīng)的低溫環(huán)境，在這種條件下，電動(dòng)冷鏈車通過(guò)制冷裝備以消耗電能方式給車廂創(chuàng)造合適的溫度，會(huì)產(chǎn)生制冷的費(fèi)用，其費(fèi)用在行駛途中（不包括車輛完成配送任務(wù)回到配送中心的這段路途）、卸貨期間和充電期間產(chǎn)生，用公式表示為：

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

根據(jù)以上定義，將目標(biāo)函數(shù)與所有相關(guān)約束組合即構(gòu)成了所研究問題的數(shù)學(xué)模型，如下所示：

其中：式（4）為目標(biāo)函數(shù)，表示總配送成本最??；式（5）表示車輛給配送點(diǎn)配送后必須離開該配送點(diǎn)；式（6）表示車輛走的是一個(gè)閉合回路；式（7）表示每個(gè)配送點(diǎn)只允許一輛車訪問一次；式（8）表示每輛車所訪問配送點(diǎn)的總需求量不超過(guò)車輛的最大容量；式（9）表示每輛車在配送過(guò)程中最多充一次電；式（10）表示如果車輛需要充電，在充電站的充電量；式（11）表示車輛從配送中心或充電站出發(fā)能訪問任意一個(gè)配送點(diǎn)并返回配送中心；式（12）表示車輛到達(dá)任意節(jié)點(diǎn)的裝載量為非負(fù)值，該節(jié)點(diǎn)的裝載量取決于在上一節(jié)點(diǎn)的裝載量和客戶的需求量；式（13）表示車輛在開始配送任務(wù)之前的裝載量不超過(guò)車輛的最大容量；式（14）表示車輛從配送點(diǎn)出發(fā)有足夠電量到達(dá)其他配送點(diǎn)或充電站；式（15）表示車輛訪問配送點(diǎn)后有足夠電量回到配送中心；式（16）表示車輛從配送中心或充電站出發(fā)有足夠電量到達(dá)配送點(diǎn)；式（17）表示車輛在充電站充完電后有足夠電量回到配送中心。

3 混合蟻群算法

REVRP 的數(shù)學(xué)模型為線性規(guī)劃模型，屬于NP-hard 問題。當(dāng)節(jié)點(diǎn)的規(guī)模比較小時(shí)，可以采用分支定界法、列生成法等精確方法求解；當(dāng)節(jié)點(diǎn)的規(guī)模比較大時(shí)，解空間呈指數(shù)級(jí)增長(zhǎng)，須采用近似方法、元啟發(fā)式方法求解。求解算法主要分為鄰域搜索、群體搜索兩大類［22］。鄰域搜索類有禁忌搜索算法、變鄰域搜索算法、自適應(yīng)大規(guī)模鄰域搜索（Adaptive Large Neighborhood Search，ALNS）算法；群體搜索類有蟻群算法、粒子群優(yōu)化算法。本文將蟻群算法和局部鄰域搜索算法相結(jié)合，構(gòu)造了一個(gè)混合蟻群算法求解REVRP。

蟻群算法［4］的基本流程如圖1 所示。

3.1 轉(zhuǎn)移規(guī)則

轉(zhuǎn)移規(guī)則是蟻群（ACO）算法的關(guān)鍵法則之一，它決定著螞蟻以何種方式選擇下一節(jié)點(diǎn)，是螞蟻在路徑構(gòu)造過(guò)程中不可或缺的計(jì)算準(zhǔn)則。在本文研究的問題中，考慮將信息素濃度、節(jié)約值、兩節(jié)點(diǎn)間的路徑距離及車輛的容量利用率作為衡量轉(zhuǎn)移概率的關(guān)鍵性指標(biāo)，用公式表示如下：

其中：ξij表示節(jié)點(diǎn)j對(duì)節(jié)點(diǎn)i的吸引值；ηij表示節(jié)點(diǎn)i到節(jié)點(diǎn)j距離的倒數(shù)；τij表示節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的信息素濃度；μij表示節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的節(jié)約值；πij表示車輛容量的利用情況，即從節(jié)點(diǎn)i訪問節(jié)點(diǎn)j后車輛的容量利用率；α、β、γ、δ為相關(guān)系數(shù)。

定義allowedk為備選節(jié)點(diǎn)j的集合，從節(jié)點(diǎn)i轉(zhuǎn)移至集合allowedk中節(jié)點(diǎn)j的概率為：

在確定轉(zhuǎn)移規(guī)則后，采用輪盤賭的方法從allowedk中選擇備選節(jié)點(diǎn)j，以此確定路徑的排列方案，最終得到可行的路徑規(guī)劃方案。

此外，為了提高搜索效率，縮小螞蟻轉(zhuǎn)移時(shí)的范圍，減少無(wú)用的轉(zhuǎn)移搜索，對(duì)allowedk里面的候選點(diǎn)數(shù)量進(jìn)行限制，即Bell等［23］提出的小窗口策略。具體地，將allowedk里的候選點(diǎn)數(shù)量上限設(shè)置為客戶總量的1，n一般可取值2、3、4。

3.2 路徑構(gòu)造過(guò)程

在REVRP里，節(jié)點(diǎn)分為三種類型，即配送中心、客戶、充電站。因此，螞蟻轉(zhuǎn)移時(shí)存在多種情形，不同類型的節(jié)點(diǎn)i可以選擇轉(zhuǎn)移的節(jié)點(diǎn)j的類型不盡相同。分別闡述如下：

1）當(dāng)螞蟻位于配送中心。

將尚未配送并且同時(shí)滿足容量約束、電能約束的客戶，放入可行集合allowedk。

電能約束采用look ahead strategy［24］，用于確保螞蟻去了節(jié)點(diǎn)j后，還有足夠的電量返回配送中心N+1，或者到達(dá)離j點(diǎn)最近的充電站f*。電能約束條件如下：

然后使用轉(zhuǎn)移規(guī)則，計(jì)算allowedk中各個(gè)節(jié)點(diǎn)的概率Pij，并按概率從中隨機(jī)選擇一個(gè)節(jié)點(diǎn)j。離開j點(diǎn)時(shí)的剩余電量為：

2）當(dāng)螞蟻位于客戶。

根據(jù)容量約束、電能約束的不同情形，螞蟻可以選擇去下一個(gè)客戶、充電站或者配送中心。電能約束為：

①如果allowedk≠?，則按轉(zhuǎn)移規(guī)則轉(zhuǎn)移到下一個(gè)客戶j或者返回配送中心N+1。若選擇轉(zhuǎn)移至客戶j，則(tij+sj)×l-dij×h。若選擇返回配送中心，則返回配送中心N+1，由于車輛在返回配送中心途中，車廂中的貨物已全部配送完，不再需要制冷。如果還有客戶未配送，則將螞蟻k移至節(jié)點(diǎn)0，再模擬另一臺(tái)車輛，重新出發(fā)配送。

②如果若存在客戶j滿足容量約束，但不滿足電能約束，且≥×h+×l，則將螞蟻直接轉(zhuǎn)移到離i點(diǎn)最近的充電站f*，充電直至充滿。充電時(shí)長(zhǎng)為：

③若上述兩種情形均不能滿足，則螞蟻只能返回配送中心。

3）當(dāng)螞蟻位于充電站。

螞蟻可以選擇去下一個(gè)客戶或者配送中心。電能約束為：

如果沒有可行的客戶，則必須返回配送中心。否則按轉(zhuǎn)移規(guī)則轉(zhuǎn)移到下一個(gè)客戶j或者返回配送中心N+1，若選擇轉(zhuǎn)移至客戶j，則與第1）步一樣更新剩余電量。

算法1 HACS 算法的路徑構(gòu)造過(guò)程。

3.3 信息素更新策略

蟻群算法的信息素更新策略分為局部更新策略和全局更新策略，本文僅采用全局更新策略［25-26］，即在所有節(jié)點(diǎn)間設(shè)定初始信息素濃度，當(dāng)螞蟻構(gòu)造好一個(gè)完整的路徑后，需要對(duì)路徑中的信息素進(jìn)行更新。具體地，采用全局更新策略［25］，僅對(duì)每次迭代的若干個(gè)最好解以及迄今為止的最好解施放信息素。

此外，為了避免蟻群算法的停滯現(xiàn)象，提高算法的全局搜索能力，對(duì)路徑上的信息素濃度設(shè)置固定的范圍，即MIN-MAX 策略［26-27］。

3.4 局部?jī)?yōu)化策略

局部?jī)?yōu)化策略被廣泛證明能夠很好地改善蟻群算法的搜索性能。大部分用于局部?jī)?yōu)化的鄰域算子源于λ-opt［28］，特別是最常用的2-opt［29-30］。本文借鑒前人所設(shè)計(jì)的鄰域算子，針對(duì)REVRP 的特點(diǎn)，先將各個(gè)回路里的充電站去掉。在不考慮電量的條件下，執(zhí)行Balseiro等［31］提出的鄰域算子，分為單回路交換和多回路交換兩類算子。其中單回路交換算子包括Relocate（記為L(zhǎng)S1）、Exchange（記為L(zhǎng)S2）兩種算子；多回路交換算子包括Relocate（記為L(zhǎng)S3）、Exchange（記為L(zhǎng)S4）兩種算子。需要強(qiáng)調(diào)的是，在各個(gè)算子中，每次執(zhí)行操作后還需要判斷是否需要插入充電站，在滿足電量約束和時(shí)間窗約束的前提下以目標(biāo)值大小確定充電站插入的最佳位置。充電站的插入采用Best Station Insertion 算法［32］。

4 數(shù)學(xué)實(shí)驗(yàn)與結(jié)果分析

用于測(cè)試算法性能的算例來(lái)源于文獻(xiàn)［14］，該算例集由文獻(xiàn)［33］中的基準(zhǔn)算例集改編而來(lái)。本文針對(duì)REVRP 的特點(diǎn)，對(duì)文獻(xiàn)［14］中的算例集進(jìn)行改造，制作出滿足要求的算例集。實(shí)驗(yàn)環(huán)境為Windows 10 操作系統(tǒng)，CPU 為Intel Core i7-8550U，頻率為3.4 GHz，內(nèi)存為16 GB，使用Dev-C++版本編程軟件。

4.1 實(shí)驗(yàn)設(shè)計(jì)

所設(shè)計(jì)的算例集按節(jié)點(diǎn)數(shù)目分為大規(guī)模和小規(guī)模兩個(gè)子集。其中，節(jié)點(diǎn)規(guī)模小的算例有18個(gè)，包含5 個(gè)客戶、10個(gè)客戶、15 個(gè)客戶的算例有6 個(gè)。每種數(shù)量規(guī)模的算例按照節(jié)點(diǎn)的分布類型再分為C 類、R 類、RC 類三類，其中C 類表示節(jié)點(diǎn)的分布形態(tài)為集群式分布，R 類表示節(jié)點(diǎn)的分布形態(tài)為隨機(jī)分布，而RC 類則結(jié)合C 類分布和R 類分布的特征，每種類型的算例各4 個(gè)。節(jié)點(diǎn)規(guī)模大的算例有6個(gè)，每個(gè)算例包含100 個(gè)客戶節(jié)點(diǎn)、20 個(gè)充電站節(jié)點(diǎn)，節(jié)點(diǎn)的分布同樣有C類、R 類、RC 三類。每種類型的算例按照分布類型下算例節(jié)點(diǎn)坐標(biāo)區(qū)分各2 個(gè)。每個(gè)算例的信息包括配送中心、客戶、充電站等節(jié)點(diǎn)坐標(biāo)、客戶需求、車輛的額定載重量、額定電量、充電速率。電動(dòng)汽車的性能參數(shù)以及ACO 算法的參數(shù)，如表2～3 所示。

表2 決策變量設(shè)置Tab.2 Setting of decision variables

表2 電動(dòng)汽車的性能參數(shù)Tab.2 Electric vehicle performance parameters

表3 ACO算法的參數(shù)Tab.3 ACO algorithm parameters

4.2 小規(guī)模算例實(shí)驗(yàn)結(jié)果

對(duì)小規(guī)模算例，分別采用CPLEX（WebSphere ILOG CPLEX）12.6.1 和ACO 算法求解。CPLEX 是一款用于線性規(guī)劃、混合整數(shù)規(guī)劃和二次規(guī)劃的高性能數(shù)學(xué)規(guī)劃求解器，它使用精確求解算法，在時(shí)間足夠的條件下，CPLEX 可以求解出數(shù)學(xué)模型的最優(yōu)解；但它的缺點(diǎn)是在大規(guī)模運(yùn)算時(shí)，求解時(shí)間過(guò)長(zhǎng)甚至無(wú)法計(jì)算。因此，本文將ACO 算法與CPLEX 計(jì)算出的最優(yōu)解進(jìn)行對(duì)比，以驗(yàn)證ACO 算法的可行性。實(shí)驗(yàn)結(jié)果如表4 所示，其中：Z表示路徑方案的配送總成本；t表示各方法的程序運(yùn)行時(shí)間。

表4 小規(guī)模算例實(shí)驗(yàn)結(jié)果Tab.4 Experimental results of small-scale examples

小規(guī)模算例實(shí)驗(yàn)結(jié)果表明，ACO 算法取得了和CPLEX相當(dāng)?shù)木_解，能夠有效解決客戶節(jié)點(diǎn)數(shù)少的REVRP。在5客戶、10 客戶和15 客戶的算例中，由于客戶節(jié)點(diǎn)數(shù)少，使用ACO 算法可以找到精確解。從實(shí)驗(yàn)結(jié)果中可以看到：CPLEX能夠在預(yù)先設(shè)置的7 200 s 內(nèi)得到各個(gè)算例的最優(yōu)解，平均用時(shí)94.7 s；而ACO 算法能夠快速搜索到它們的最優(yōu)解，平均運(yùn)算時(shí)間只需要0.36 s，可節(jié)省99.6%的運(yùn)算時(shí)間，可見ACO 算法大幅度縮短了運(yùn)算時(shí)間。

4.3 大規(guī)模算例實(shí)驗(yàn)結(jié)果

針對(duì)大規(guī)模算例，分別采用帶有4 種鄰域算子的混合蟻群算法進(jìn)行求解。HACO-I 表示ACO+LS1 策略，HACO-II 表示ACO+LS2 策略，HACO-III 表示ACO+LS3 策略，HACO-IV表示ACO+LS4 策略，HACO-V 表示ACO+所有鄰域算子。每個(gè)算例各運(yùn)行10次，分別記錄每次運(yùn)行所找到的最佳路徑方案、目標(biāo)值（best）以及發(fā)現(xiàn)最好解的時(shí)間t；并針對(duì)每個(gè)算例，計(jì)算出各個(gè)算法與ACO 之間的偏差（ΔZ），如表5 所示。

從表5 可以看出，5 種策略得到的目標(biāo)值均優(yōu)于ACO 算法；除R201 算例外，其他算例的最好解總是由HACO-V 得到。運(yùn)行時(shí)間方面，ACO 算法的平均用時(shí)21.7 s。ACO 與單獨(dú)鄰域算子組合的算法中，HACO-I 的用時(shí)最少，平均用時(shí)為71.5 s，是ACO 算法的3.3 倍；HACO-III 的平均用時(shí)為130.0 s，是ACO 算法的6 倍；HACO-V 綜合運(yùn)用了4 種鄰域算子，因此用時(shí)最高，平均用時(shí)高達(dá)252.0 s，是ACO 算法的11.7 倍。這是因?yàn)? 種鄰域算子均是對(duì)ACO 算法產(chǎn)生的可行解進(jìn)行改進(jìn)，因此混合蟻群算法的平均運(yùn)行時(shí)間要高于ACO 算法的程序平均運(yùn)行時(shí)間。

為了解不同類算例的整體情況，在表5 結(jié)果的基礎(chǔ)上進(jìn)行進(jìn)一步計(jì)算，計(jì)算結(jié)果如圖2 所示。由圖2（a）可以看出，節(jié)點(diǎn)的分布形式影響了路徑方案的構(gòu)成，C 類算例（集群式分布）的路徑方案中車輛單次配送能夠訪問更多的客戶，導(dǎo)致了C 類算例的平均目標(biāo)值小于R 類和RC 類算例。由圖2（b）可以看出，C 類算例的程序運(yùn)算速度也更快?？梢?，節(jié)點(diǎn)的集群式分布可以降低成本和程序的運(yùn)算時(shí)間。

表5 大規(guī)模算例實(shí)驗(yàn)結(jié)果Tab.5 Experimental results of large-scale examples

圖3 中可以看出每組算例中兩個(gè)不同算例之間的目標(biāo)值存在較大的差異，如C101 和C201、R101 和R201、RC101 和RC201，這是由于C201、R201、RC201 算例對(duì)應(yīng)車型的電池容量分別比C101、R101、RC101 的高，車輛在一次配送任務(wù)中訪問的客戶節(jié)點(diǎn)較多，車輛裝載率較高，使用車輛數(shù)較少，其配送成本也隨之減小?？梢婋姵厝萘繉?duì)配送成本影響較大，相同條件下電池容量越大，配送成本越小。

由表5 可知，5 種策略對(duì)ACO 算法都起到了一定的改進(jìn)作用，求取每種策略下所有算例的目標(biāo)值改進(jìn)率的平均值，如圖4 所示。相較于蟻群算法得到的路徑方案，4 種鄰域算子都能在此基礎(chǔ)上對(duì)解進(jìn)行改進(jìn)，其中ACO 與單獨(dú)鄰域算子組合的策略中，HACO-III 對(duì)于所有算例的目標(biāo)值平均改進(jìn)率最大，為2.81%；HACO-IV 的目標(biāo)值平均改進(jìn)率最小，為0.99%；綜合運(yùn)用了4 種鄰域算子的HACO-V 的性能最好，最好解的改進(jìn)率達(dá)到4.45%。

綜合分析表5 和圖4 可知，在所有6 個(gè)算例中，有5 個(gè)算例的最好解來(lái)自HACO-V，僅R201 的最好解來(lái)自HACO-III，但HACO-III 的平均目標(biāo)值為1 093.1元，不如HACO-V 的1 087.1 元；從平均值來(lái)看，HACO-V 求解所有算例的平均值均是最小的。

如圖5 所示，對(duì)于不同的節(jié)點(diǎn)分布形式，不同策略的改進(jìn)效果不盡相同。HACO-I 和HACO-III 對(duì)R 類節(jié)點(diǎn)分布形式改進(jìn)效果更明顯，其余均對(duì)RC 類改進(jìn)效果更為明顯?？梢姽?jié)點(diǎn)分布形式也會(huì)影響算法的改進(jìn)效果，算法對(duì)于隨機(jī)分布和隨機(jī)、集群混合式節(jié)點(diǎn)分布形式改進(jìn)效果更好，對(duì)集群式節(jié)點(diǎn)分布改進(jìn)效果稍差。

5 結(jié)語(yǔ)

本文研究了基于電動(dòng)汽車的冷鏈物流策略路徑問題。在此基礎(chǔ)上，構(gòu)建了面向社會(huì)充電站的REVRP 的數(shù)學(xué)模型，設(shè)計(jì)了一種混合蟻群算法解決該問題，并制定了基準(zhǔn)算例集。實(shí)驗(yàn)結(jié)果表明，所設(shè)計(jì)的混合蟻群算法能夠有效求解小規(guī)模和大規(guī)模節(jié)點(diǎn)的REVRP。當(dāng)節(jié)點(diǎn)數(shù)量比較少時(shí)，針對(duì)所有算例，蟻群算法均能找到與CPLEX 一樣的最好解；當(dāng)節(jié)點(diǎn)規(guī)模較大時(shí)，蟻群算法與不同局部?jī)?yōu)化算子組合后各自找到的最好解存在明顯差異，意味著在求解大規(guī)模節(jié)點(diǎn)的REVRP中，不同算子所帶來(lái)的算法性能有優(yōu)劣之分。其中，算子LS3 效果最佳，而算子LS4 效果最差，而將所有4 種算子同時(shí)使用時(shí)的性能最佳。