衛(wèi)琛戈, 車阿大

(西北工業(yè)大學(xué)管理學(xué)院,陜西西安 710072)

1 引 言

弧路徑優(yōu)化問題起源于管梅谷提出的中國(guó)郵遞員問題, 與車輛路徑問題(一般指點(diǎn)路徑問題)的核心區(qū)別在于前者的需求分布于節(jié)點(diǎn)間的弧或邊上, 而后者的需求分布于節(jié)點(diǎn)上.因此弧路徑問題需要確定不同弧和邊的訪問順序以及行進(jìn)方向來獲得路徑.考慮容量限制的弧路徑優(yōu)化問題(capacitated arc routing problem,CARP)是弧路徑優(yōu)化問題的一個(gè)分支,最早由Golden[1]提出.經(jīng)典CARP 可以定義在無向圖G=(V,E)上,其中V為點(diǎn)集,E為弧集,ER ?E指需要被服務(wù)的弧的集合.|K|輛容量為Q的同構(gòu)車輛從車場(chǎng)0∈V出發(fā),其中K為車輛集合,|K|為車輛總數(shù),在不違背車輛容量限制的前提下依次服務(wù)所有弧(i,j)∈ER,滿足其需求dij后回到車場(chǎng),其中弧(i,j)間空轉(zhuǎn)成本為cij.該問題的核心在于確定總成本最小的服務(wù)路徑.

CARP 及其變異問題被廣泛應(yīng)用在垃圾回收、道路管理等領(lǐng)域,其研究成果有著豐富的理論及實(shí)踐價(jià)值.然而,已有相關(guān)研究綜述主要關(guān)注弧路徑優(yōu)化問題,缺少直接針對(duì)CARP 及其變異問題的分類、求解算法和應(yīng)用場(chǎng)景方面的綜述.Eiselt 等[2]在弧路徑優(yōu)化綜述中,介紹了1995年前CARP 相關(guān)的問題和求解算法.Corberan 等[3]則在弧路徑優(yōu)化綜述中,對(duì)2010年前CARP 相關(guān)文獻(xiàn)進(jìn)行了分類和綜述.Mourao 等[4]在文獻(xiàn)[3]的基礎(chǔ)上,補(bǔ)充分析了2010年～2017年間弧路徑優(yōu)化的相關(guān)研究成果和其應(yīng)用場(chǎng)景.本文從CARP及其變異問題的類型、求解算法、實(shí)際應(yīng)用三個(gè)方面進(jìn)行綜述,分析CARP 未來研究展望.

2 CARP 問題分類和研究進(jìn)展

CARP 可視為多車情形下考慮容量約束的中國(guó)郵遞員問題和鄉(xiāng)村郵遞員問題.實(shí)際應(yīng)用中容量限制較為常見,因此考慮容量限制的弧路徑優(yōu)化問題受到了越來越多的關(guān)注.圖1 為經(jīng)典CARP 及其變異問題的主要特征.依據(jù)問題的主要特征對(duì)經(jīng)典CARP 及其變異問題進(jìn)行綜述,詳細(xì)文獻(xiàn)分類見表1.

圖1 經(jīng)典CARP 及其變異問題特征Fig.1 Problem characteristics of CARP and its variants

表1 CARP 詳細(xì)分類Table 1 Classification of CARP

續(xù)表1Table 1 Continues

2.1 經(jīng)典CARP

經(jīng)典CARP一般以最小化總成本為目標(biāo),其決策變量包括= 1 當(dāng)且僅當(dāng)車輛k服務(wù)弧(i,j)∈ER,=1 當(dāng)且僅當(dāng)車輛k經(jīng)過弧(i,j)∈E,為用于子回路消除的流變量.數(shù)學(xué)模型為

其中式(1)為目標(biāo)函數(shù),式(2)為流平衡約束,式(3)要求滿足所有弧的需求,式(4)為車輛載重限制,式(5)約束變量間關(guān)系,式(6)限制車輛必須從車場(chǎng)出發(fā),式(7)和式(8)為子回路消除約束,值得注意的是,弧路徑優(yōu)化問題中允許存在合法子回路[1],式(9)和式(10)約束變量取值范圍.

Golden 等[1]首先建立了CARP 的數(shù)學(xué)模型, 設(shè)置兩個(gè)二維0-1 變量分別表示車輛所服務(wù)的弧和空轉(zhuǎn)的弧.考慮到一條弧上可能發(fā)生多次空轉(zhuǎn),Belenguer 等[5]定義整數(shù)變量來表示車在弧上空轉(zhuǎn)的次數(shù).后續(xù)對(duì)CARP 及其變異問題的研究中,決策變量的設(shè)置多沿用此方法.然而,隨著車輛數(shù)的增多,二維變量模型的求解難度增大,Belenguer 等[5]、Letchford 等[6]均提出了聚合空轉(zhuǎn)變量,將二維整數(shù)變量轉(zhuǎn)化為一維,用于表示一條弧被所有車輛空轉(zhuǎn)的次數(shù)之和,利用該變量可以推導(dǎo)出有效不等式,從而加速求解過程.

作為一類點(diǎn)路徑優(yōu)化問題,車輛路徑問題已經(jīng)有大量研究成果.因此, 部分學(xué)者將CARP 轉(zhuǎn)化為考慮容量約束的車輛路徑優(yōu)化問題(capacitated vehicle routing problem,CVRP)進(jìn)行建模.Pearn 等[7]首次提出將r個(gè)弧的CARP 轉(zhuǎn)化為3r+1 個(gè)點(diǎn)的CVRP.隨后,Longo 等[8]及Baldacci 等[9]進(jìn)一步將其優(yōu)化為2r+1 個(gè)點(diǎn)的CVRP.該方法是目前使用較為廣泛的方法.Foulds 等[10]再次縮小了轉(zhuǎn)化問題的規(guī)模,將其轉(zhuǎn)化為r+1個(gè)點(diǎn)的CVRP.

經(jīng)典問題的基準(zhǔn)算例包括KSHS 算例[11]、GDB算例[12]、VAL 算例[13]、EGL 算例[14]、EGL 大規(guī)模算例[15]和BMCV 算例[16].后續(xù)相關(guān)變異問題的研究中,主要是對(duì)以上基準(zhǔn)算例進(jìn)行改造以驗(yàn)證模型和算法.

2.2 混合CARP

經(jīng)典CARP 一般研究的是無向圖上的車輛路徑優(yōu)化,即不限制車輛服務(wù)時(shí)的行進(jìn)方向.但實(shí)際城市道路中存在單行道和雙行道,因此對(duì)有向圖和混合圖的研究受到關(guān)注.混合CARP(mixed CARP,MCARP)定義在混合圖G=(V,E ∪A)上.該問題將原有弧集分為有向弧集A和無向邊集E,設(shè)AR ?A為需要被服務(wù)的有向弧集合,ER ?E為需要被服務(wù)的無向邊集合.MCARP 優(yōu)化模型在經(jīng)典問題模型的基礎(chǔ)上增加約束

式(11)表示只能在確定方向服務(wù)有向弧,而式(3)允許在任一方向滿足無向邊需求.在MCARP 的最優(yōu)路徑中,不僅要考慮弧與弧之間的距離,還要考慮連接順序是否違反道路行進(jìn)方向限制.Lacomme 等[17,18]研究了一類特定的MCARP,同時(shí)考慮了服務(wù)成本和空轉(zhuǎn)成本,設(shè)置禁止左轉(zhuǎn)掉頭、限制最大行駛距離等約束.Xu 等[19]、劉潔等[20]研究了類似的問題.Belenguer 等[21]首次建立MCARP 線性規(guī)劃模型,并求解該問題的上下界.Gouveia 等[22]建立了兩種更為緊湊的MCARP 混合整數(shù)規(guī)劃模型,該聚合模型有效地減少了變量及約束個(gè)數(shù).作者通過引入有效不等式,首次求解了中等規(guī)模的MCARP.Constantino 等[23]提出通過限制不同路徑共有的節(jié)點(diǎn)數(shù)量限制重疊的MCARP,作者認(rèn)為限制重疊的路徑規(guī)劃結(jié)果更具實(shí)踐意義.van Bevern等[24]研究的MCARP 中,服務(wù)成本和遍歷成本與行進(jìn)方向相關(guān).MCARP 常與CARP 的其它變異問題相結(jié)合,將在后文中詳細(xì)介紹.

2.3 多車場(chǎng)/開放CARP

隨著城市規(guī)模的增大,單車場(chǎng)已經(jīng)不能滿足服務(wù)需求,因此出現(xiàn)了關(guān)于多車場(chǎng)CARP(multi-depot CARP,MDCARP)的研究.多車場(chǎng)問題具有更廣泛的適用場(chǎng)景[25].以VD ?V表示車場(chǎng)集合,則經(jīng)典CARP 優(yōu)化模型中關(guān)于車場(chǎng)的約束式(6)轉(zhuǎn)化為

Li 等[14]研究了冬季除雪中的MDCARP.Amberg 等[26]將MDCARP 轉(zhuǎn)化為考慮弧約束的多中心最小生成樹問題進(jìn)行求解.李小花等[27]通過區(qū)域劃分將MDCARP 轉(zhuǎn)化為單車場(chǎng)CARP.Xing 等[28,29]基于Lacomme 等[18]的工作,提出了考慮最大服務(wù)時(shí)間限制的MDCARP.Liu 等[30]研究了考慮有限異構(gòu)車隊(duì)的MDCARP.Krushinsky 等[31]結(jié)合實(shí)際道路網(wǎng)絡(luò),研究建立在大規(guī)模稀疏有向圖上的MDCARP.

Usberti 等[32]和Arakaki 等[33]提出的開放CARP 是一種特殊類型的MDCARP,該問題不限制車輛的出發(fā)和到達(dá)車場(chǎng).Fung 等[34]研究的開放CARP 則限制車輛必須從指定車場(chǎng)出發(fā),但不限制是否返回該車場(chǎng).

2.4 中間設(shè)施CARP

車輛在服務(wù)過程中,受到最長(zhǎng)行駛距離和車艙容量的限制,可能需要中途卸貨或補(bǔ)貨.多次往返車場(chǎng)進(jìn)行補(bǔ)卸貨的問題被定義為多行程CARP,而通過設(shè)置補(bǔ)給點(diǎn)、中轉(zhuǎn)站等中間設(shè)施補(bǔ)貨的問題被稱為考慮中間設(shè)施的CARP(CARP with intermediate facilities,CARPIF).這兩類問題中,一輛車的路徑被分為若干段,每一段都需要滿足行駛距離和車艙容量限制.相比經(jīng)典問題,此類問題還需決策弧被服務(wù)時(shí)所處的段,因此設(shè)置變量,用于決策弧(i,j)∈ER是否在車輛k的第t段被服務(wù),則決策空轉(zhuǎn)次數(shù).

設(shè)VIF表示中間設(shè)施集合,T表示行程段集合,則有

用式(13)～式(15)替換經(jīng)典CARP 模型中的式(6),分別約束車輛從車場(chǎng)出發(fā)到中間設(shè)施補(bǔ)貨,從中間設(shè)施出發(fā)到中間設(shè)施補(bǔ)貨和從中間設(shè)施出發(fā)回到車場(chǎng)三類行程段.

Mourao 等[35]和Tirkolaee 等[36?39]研究車場(chǎng)與卸貨點(diǎn)分開的多行程問題,該問題更貼近CARPIF.Ghiani等[40]的研究給出了CARPIF 的兩類下界和兩類上界.Ghiani 等[41]、Polacek 等[42]求解了行駛距離受限的CARPIF.Rodrigues 等[43]的研究中,將中間設(shè)施分為有容量限制和有訪問次數(shù)容量限制兩種情況.

Amaya 等[44,45]研究的考慮補(bǔ)給點(diǎn)的CARP,可以被看作中間設(shè)施可移動(dòng)的CARPIF.該問題中存在服務(wù)和補(bǔ)貨兩類車輛,服務(wù)車輛可多次通過補(bǔ)貨車輛裝載補(bǔ)貨.胡珊等[46]研究了交通道路維修服務(wù)中類似的問題.De Rosa 等[47]研究了垃圾回收中帶轉(zhuǎn)運(yùn)的弧路徑調(diào)度問題.CARPIF 屬于該問題的回收階段,而中間設(shè)施到最終處理點(diǎn)的調(diào)度屬于轉(zhuǎn)運(yùn)階段.現(xiàn)有研究中,通過協(xié)調(diào)回收階段和轉(zhuǎn)運(yùn)階段的調(diào)度來優(yōu)化全流程路徑的研究較為有限.

2.5 多艙車輛CARP

對(duì)于不能混裝的需求,用單艙車輛多次服務(wù)會(huì)產(chǎn)生不必要的成本,因此研究人員提出了考慮多艙車輛的CARP(multi-compartment CARP,MCCARP).MCCARP 可用于解決垃圾分類回收等實(shí)際問題.相較于單艙車輛,該問題在決策時(shí)需要確定提供服務(wù)的車艙,因此決策變量表示弧(i,j)∈ER是否被車輛k的第m個(gè)車艙服務(wù),M為車艙集合.對(duì)于限制每個(gè)車艙容量的問題,需要將經(jīng)典CARP 模型中的式(4)調(diào)整為

其中參數(shù)Qm為車艙容量,式(16)保證不違反車艙容量限制.

對(duì)于不限制每個(gè)車艙容量只考慮整車容量的問題,則約束調(diào)整為

Muyldermans 等[48]首次提出了考慮多艙車輛的CARP,研究了單艙車輛多次運(yùn)輸和多艙車輛運(yùn)輸?shù)倪m用情況.Zbib 等[49]對(duì)比了垃圾分類回收問題中使用單艙車和多艙車回收的區(qū)別.多艙車回收系統(tǒng)在行駛距離上更優(yōu),而單艙車回收系統(tǒng)在路線數(shù)量上更優(yōu).Mofid-Nakhaee 等[50]建立了MCCARP 的數(shù)學(xué)模型,但該模型不考慮單個(gè)車艙的容量限制.Kiilerich 等[51]根據(jù)弧是否可以被多輛車服務(wù)將問題分為需求可分和需求不可分兩種MCCARP.依據(jù)實(shí)際回收工作中,同一車艙多次回收垃圾的類型必須一致,作者提出固定車艙類型的MCCARP.Zbib 等[52]研究了考慮垃圾分類的MCCARP,并將問題分為三個(gè)決策階段: 確定每種類型的車輛數(shù)量,為每一輛所選車輛的車艙分配垃圾類型,并規(guī)劃車輛回收路徑.

2.6 受時(shí)間影響的CARP

考慮到CARP 的實(shí)際應(yīng)用中司機(jī)安全駕駛時(shí)間等限制因素, 研究人員提出了受時(shí)間限制(time restrictions)的弧路徑優(yōu)化問題.假設(shè)車輛以速度ρ在距離為cij的弧(i,j)上勻速行駛,則行駛時(shí)間為cij/ρ.設(shè)sij ∈S為服務(wù)弧(i,j)∈ER時(shí)除行駛時(shí)間外的服務(wù)時(shí)間.當(dāng)Tmax為服務(wù)總時(shí)長(zhǎng)限制時(shí),該問題模型中需增加約束

Willemse 等[53?55]的研究中將時(shí)間限制轉(zhuǎn)化為路徑長(zhǎng)度約束.Chen 等[56,57]的研究考慮對(duì)超過最大工作時(shí)間限制的車輛實(shí)施援助,研究以最小化服務(wù)成本和援助成本為目標(biāo)的隨機(jī)CARP.為保證工作效率,實(shí)際作業(yè)會(huì)考慮避開交通高峰期和道路維修期,因此考慮時(shí)間窗(time window)的CARP 被提出,且在道路灑水、綠化帶灌溉等市政項(xiàng)目中,考慮時(shí)間窗可以減少對(duì)市民正常生活的不良影響.設(shè)[eij,lij]為弧(i,j)的時(shí)間窗,已有研究主要考慮軟時(shí)間窗,即在時(shí)間窗范圍外允許作業(yè)但會(huì)產(chǎn)生懲罰成本,ce為等待成本,cl為遲到成本,表示車輛k開始經(jīng)過弧(i,j)的時(shí)刻,則目標(biāo)函數(shù)為

Vansteenwegen 等[58]研究了負(fù)責(zé)采集街道信息的“地圖車”調(diào)度問題,引入軟時(shí)間窗以避免背光拍照影響采集結(jié)果.Haghani 等[59]考慮不同優(yōu)先級(jí)的弧,通過設(shè)置時(shí)間窗保證優(yōu)先服務(wù)更重要的弧.Thomaz 等[60]研究了帶時(shí)間窗的多周期CARP.考慮到冬季除雪容易受到時(shí)間影響,不同除雪時(shí)間所需成本不同,除雪效果也存在差異,因此研究人員引入了受時(shí)間影響(time dependent)的CARP,包括成本受時(shí)間影響和速度受時(shí)間影響(時(shí)變速度),即考慮與時(shí)間相關(guān)的成本函數(shù)cij(t)和速度函數(shù)ρ(t).Tagmouti 等[61?63]研究了受時(shí)間影響的CARP,將服務(wù)成本定義為與開始服務(wù)時(shí)間相關(guān)的分段函數(shù),而服務(wù)時(shí)間則不受影響.作者設(shè)置了類似于軟時(shí)間窗的最佳服務(wù)時(shí)間間隔,在時(shí)間間隔外服務(wù)會(huì)導(dǎo)致額外的成本.de Armas 等[64]的研究以最小化總服務(wù)時(shí)間為目標(biāo),考慮服務(wù)成本、空轉(zhuǎn)成本和車艙容量均受時(shí)間影響的情況.對(duì)于考慮時(shí)變速度的問題,已有針對(duì)單車情況的研究[65,66],但是多車問題尚未解決.

2.7 多目標(biāo)CARP

實(shí)際應(yīng)用中,除了考慮成本的影響,工作量均衡、環(huán)境因素等也可能成為影響決策的因素,因此衍生出了多目標(biāo)CARP(multi-objective CARP,MOCARP).例如考慮最小化總成本和單個(gè)車輛最大成本的雙目標(biāo)問題

Lacomme 等[67]研究考慮成本最小和不同車輛工作時(shí)間平衡的MOCARP,以最小化總成本和最大完工時(shí)間(makspan)為目標(biāo),也是MOCARP 中研究較為廣泛的一組目標(biāo)[38,68?72].以上目標(biāo)是相互矛盾的,因此不存在唯一全局最優(yōu)解.Mei 等[73]、Zhang 等[74]、Chen 等[75]研究的多周期CARP 中考慮了主要和次要兩個(gè)目標(biāo),即首要目標(biāo)優(yōu)化車輛數(shù)和次要目標(biāo)優(yōu)化總成本.作者通過加權(quán)和的方式聚合兩個(gè)目標(biāo),從而對(duì)整體進(jìn)行優(yōu)化.Grandinetti 等[76]提出了最小化運(yùn)輸總成本、最大完工時(shí)間和車輛數(shù)量(路線總數(shù))的無向MOCARP.Amponsah 等[77]針對(duì)高溫天氣垃圾回收問題,提出了考慮最小化成本和環(huán)境影響的MOCARP.現(xiàn)有研究成果更多的是對(duì)多目標(biāo)問題在算法上的創(chuàng)新,對(duì)目標(biāo)類型的創(chuàng)新較為有限.

2.8 多周期CARP

在完成冬季除雪、垃圾回收、道路清掃等實(shí)際工作時(shí),考慮到人口密度、地理位置和運(yùn)營(yíng)成本等因素,周期性服務(wù)可以節(jié)約成本, 方便管理.因此, 多周期CARP(periodic CARP,PCARP)得到了研究人員的關(guān)注.PCARP 在經(jīng)典CARP 的基礎(chǔ)上考慮|P|個(gè)周期,其中P為周期集合.服務(wù)頻率fij表示弧(i,j)在總時(shí)間范圍內(nèi)需要被服務(wù)的次數(shù),決策變量表示弧(i,j)∈ER是否在第p個(gè)周期被車輛k服務(wù),=1 則表示空轉(zhuǎn).經(jīng)典CARP 模型中,約束式(3)應(yīng)替換為

式(21)要求總時(shí)間范圍內(nèi)每條弧的服務(wù)次數(shù)等于其服務(wù)頻率,式(22)約束每周期內(nèi)每個(gè)弧至多被服務(wù)一次.

Lacomme 等[78]研究了混合圖上考慮禁止轉(zhuǎn)向和轉(zhuǎn)向懲罰的PCARP,作者認(rèn)為PCARP 中考慮累積每周期產(chǎn)生的新需求時(shí),分布于弧上的實(shí)際需求受到上一周期服務(wù)時(shí)間的影響,例如:雜草收割、垃圾回收.以總時(shí)間范圍一周為例,一天為一個(gè)周期,|P|= 7,假設(shè)一周內(nèi)有兩個(gè)周期需要服務(wù),pf為第一個(gè)需要服務(wù)的周期,pl為第二個(gè)需要服務(wù)的周期.dijp為弧(i,j)在周期p產(chǎn)生的新需求,則本周第一次服務(wù)時(shí)的實(shí)際需求為

Chu 等[79,80]建立了PCARP 的線性規(guī)劃模型, 提出了PCARP 的初步下界.Mei 等[73]認(rèn)為已有研究缺少對(duì)車輛數(shù)的優(yōu)化, 因此研究了同時(shí)考慮成本和車輛數(shù)的PCARP.Zhang 等[74]、Chen 等[75]研究了類似的問題.Monroy 等[81]考慮周期中包含時(shí)間間隔不完全相同的子周期的情形,提出服務(wù)周期不均勻的PCARP.Riquelme-Rodriguez 等[82,83]基于灑水抑塵作業(yè)提出了考慮庫存約束的PCARP, 用庫存來描述弧的需求.Wohlk 等[84]提出了考慮垃圾分類的協(xié)調(diào)CARP,其目的是協(xié)調(diào)多周期垃圾回收問題中不同種類垃圾的回收時(shí)間,以方便居民傾倒垃圾.現(xiàn)有多周期問題的研究更多以國(guó)外人口密度小的居民區(qū)為背景,缺少適用于國(guó)內(nèi)人口集中、垃圾產(chǎn)量高、道路灑掃任務(wù)重情景的相關(guān)研究.

2.9 隨機(jī)CARP

現(xiàn)實(shí)作業(yè)中,弧上的需求量、服務(wù)成本、服務(wù)時(shí)間等參數(shù)往往是隨機(jī)變化的,例如:垃圾回收時(shí)垃圾量不確定、灑水車作業(yè)時(shí)路況變化導(dǎo)致遍歷時(shí)間隨機(jī).基于此,研究人員提出了隨機(jī)CARP,其中大部分研究考慮了需求量的隨機(jī)性.現(xiàn)有研究成果中主要考慮兩階段隨機(jī)CARP.假設(shè)需求服從某種分布,第一階段以其期望值代替隨機(jī)需求,計(jì)算確定性CARP 中車輛k的最優(yōu)路徑δk,C(δk)為其遍歷成本.第二階段考慮隨機(jī)需求,則δk中總需求可能大于車輛容量Q導(dǎo)致服務(wù)失敗,產(chǎn)生追索成本ξ(δk).兩階段隨機(jī)CARP 的目標(biāo)函數(shù)為

即以遍歷成本與追索成本期望值之和最小為目標(biāo),其中E 為期望算子.

Fleury 等[85,86]研究需求服從截?cái)嗾龖B(tài)分布的隨機(jī)CARP, 分析解受隨機(jī)需求波動(dòng)的影響, 評(píng)估解的魯棒性.Christiansen 等[87]針對(duì)需求服從泊松分布的隨機(jī)CARP 建立集劃分模型.Laporte 等[88]研究類似的問題, 并推導(dǎo)出期望成本的表達(dá)式.王立斌等[89,90]建立基于需求期望與方差的隨機(jī)CARP 數(shù)學(xué)模型.MacLachlan 等[91]引入車輛協(xié)同作業(yè)的思想來規(guī)避隨機(jī)CARP 中需求不確定性造成的服務(wù)失敗.Gonzalez-Martin 等[92]通過設(shè)計(jì)安全庫存(車輛的額外載荷)來解決突發(fā)需求.該方法雖然會(huì)造成固定成本增加,但能降低大部分算例的期望成本和總成本.

Wang 等[93]同時(shí)考慮需求和服務(wù)成本的隨機(jī)性,通過增強(qiáng)確定性問題的魯棒性來規(guī)避隨機(jī)性所帶來的影響.Chen 等[56]研究了道路養(yǎng)護(hù)問題中考慮隨機(jī)服務(wù)時(shí)間及空轉(zhuǎn)時(shí)間的CARP,建立以最小化總成本為目標(biāo)的機(jī)會(huì)約束模型.Chen 等[57]在此基礎(chǔ)上建立對(duì)服務(wù)時(shí)間不敏感的魯棒優(yōu)化模型,并與機(jī)會(huì)約束模型進(jìn)行對(duì)比.徐磊等[94]、劉洋等[95]研究了類似的問題.Su 等[96]建立機(jī)會(huì)約束模型,并求解鐵路檢修中零部件老化率隨機(jī)的CARP.隨機(jī)CARP 更貼近實(shí)際應(yīng)用,但由于其復(fù)雜性,研究成果有限,主要依賴建立期望值模型和機(jī)會(huì)約束規(guī)劃模型等傳統(tǒng)處理方式,存在魯棒性差或運(yùn)算時(shí)間過長(zhǎng)的問題[97],需要進(jìn)一步研究.

2.10 其余問題

經(jīng)典CARP 一般考慮同構(gòu)車隊(duì),而異構(gòu)車隊(duì)問題中需要考慮車輛容量Qk、成本ckij等與車輛k的類型有關(guān)的參數(shù).Ulusoy[98]的研究最早涉及異構(gòu)車隊(duì).文獻(xiàn)[30,43,99,100]中均考慮到異構(gòu)車隊(duì).Sniezek 等[101]研究了一類車輛/站點(diǎn)依賴的CARP.如果一類或多類車輛不能穿過該弧,而其它類別的車輛可以穿過該弧,則該弧存在車輛/站點(diǎn)依賴.

需求可分的CARP(split-delivery CARP,SDCARP)指一條弧可以被多輛車服務(wù)的情況.相比假設(shè)每條弧只能被一輛車訪問, 需求可分的策略可以顯著地節(jié)約成本.Eskandarzadeh 等[102]和Belenguer 等[103]分別建立了SDCARP 的非線性規(guī)劃模型和整數(shù)規(guī)劃模型.Yu 等[104]研究了城市道路灑水過程中混合圖上的SDCARP.

Kirlik 等[105]和Bartolini 等[106]研究考慮空轉(zhuǎn)需求的CARP,與經(jīng)典問題的區(qū)別在于空轉(zhuǎn)的弧上也會(huì)產(chǎn)生需求,因此要考慮服務(wù)需求和空轉(zhuǎn)需求之和不超過車艙容量約束.Archetti 等[107]、Zachariadis 等[108]、金倩倩等[109]研究了帶收益值的無向CARP,要求在滿足工作時(shí)間限制的前提下,保證利潤(rùn)最大化.Benavent等[110]研究了混合圖上考慮利潤(rùn)的CARP.Tagmouti 等[63]研究動(dòng)態(tài)CARP,考慮天氣變化對(duì)最佳服務(wù)時(shí)間間隔的影響.Padungwech 等[111]則研究了服務(wù)過程中出現(xiàn)新任務(wù)的動(dòng)態(tài)CARP.孫錫梅等[112]研究了同時(shí)配送和回收的CARP.

3 CARP 求解算法分類和研究進(jìn)展

CARP 求解算法主要分為精確算法和啟發(fā)式算法.考慮到CARP 是典型的NP 難問題,部分精確算法會(huì)在求解子問題時(shí)引入啟發(fā)式方法,從而加快精確算法的求解速度.啟發(fā)式算法以構(gòu)造啟發(fā)式算法和元啟發(fā)式算法為主.早期研究中,大多應(yīng)用構(gòu)造啟發(fā)式算法來求解CARP.隨著計(jì)算機(jī)技術(shù)的發(fā)展,元啟發(fā)式算法受到了更多的關(guān)注.近期的研究中,更多的學(xué)者選擇融合構(gòu)造啟發(fā)式和元啟發(fā)式算法的混合算法,用構(gòu)造啟發(fā)式獲得高質(zhì)量的初始可行解或初始種群,再應(yīng)用元啟發(fā)式算法進(jìn)一步優(yōu)化.

3.1 精確算法

考慮到CARP 及其變異問題的NP 難特性,精確算法只能求解小規(guī)模算例,少量文獻(xiàn)直接建立數(shù)學(xué)模型,調(diào)用商業(yè)優(yōu)化軟件精確求解[43,82].CARP 中的常見精確算法包括割平面算法、分支切割算法、分支定價(jià)算法和分支切割定價(jià)算法等.

對(duì)于經(jīng)典CARP, Pearn[113]拓展單車弧路徑優(yōu)化問題的已有下界, 提出了CARP 的下界.Benavent等[13]給出了四種CARP 的新下界, 其中基于動(dòng)態(tài)規(guī)劃求出的下界直接考慮了車輛容量約束.Belenguer等[5]結(jié)合有效不等式應(yīng)用割平面算法求解單位需求的CARP.Belenguer 等[114]提出了CARP 的三組新有效不等式, 應(yīng)用割平面算法求得新的下界.Wohlk[115]針對(duì)CARP, 提出了一種新的下界(multiple cuts node duplication lower bound),并證明了該下界對(duì)已有下界占優(yōu).Longo 等[8]、Baldacci 等[9]和Foulds 等[10]將CARP轉(zhuǎn)化為CVRP,設(shè)計(jì)分支切割算法[8,9]和分支切割定價(jià)算法[10]求解.

Hirabayashi 等[116]開發(fā)了一種基于分支定界算法的路徑構(gòu)造精確算法.Letchford 等[6]利用圖的稀疏性提高求解定價(jià)子問題的效率,從而改進(jìn)求解CARP 的分支切割定價(jià)算法.Bartolini 等[117]提出了一種分支定價(jià)算法和新的路徑生成動(dòng)態(tài)規(guī)劃算法,該方法改進(jìn)大量已知下界,并首次精確求解27 個(gè)CARP 基準(zhǔn)算例.Bode 等[118?120]通過割平面算法和分支定價(jià)算法兩個(gè)階段求解CARP,采用結(jié)合(k,2)-loop 消除的標(biāo)號(hào)法求解定價(jià)子問題,進(jìn)一步提高部分下界.Pecin 等[121]研究了現(xiàn)有精確算法求解CARP 的模型、割集和分支策略,討論其適用的情況及定價(jià)問題的復(fù)雜性,并構(gòu)建新的分支切割定價(jià)算法求解CARP.Martinelli 等[122]基于精確分離算法,改進(jìn)已有精確容量不等式分離方法,并通過對(duì)偶上升(dual ascent)算法進(jìn)一步加速求解大規(guī)模CARP.該方法也可用于加速其它精確算法.

Porumbel[123]的研究關(guān)注列生成算法中的對(duì)偶多面體, 定義了一種交集子問題(intersection subproblem)對(duì)其進(jìn)行優(yōu)化.作者提出了整數(shù)射線法(integer ray method, IRM), 使用基于IRM 的動(dòng)態(tài)規(guī)劃方案來求解子問題.相比列生成算法的分離子問題,交集子問題更易求解,并且在處理具有容量約束的問題上,IRM 更具優(yōu)勢(shì).Porumbel 等[124]結(jié)合列生成算法與迭代鄰域搜索混合求解CARP,并首次在大規(guī)?；鶞?zhǔn)算例中應(yīng)用列生成算法.其中,列生成過程通過反復(fù)傳送由定價(jià)子問題構(gòu)造的路徑來影響迭代鄰域搜索.

對(duì)于CARP 變異問題,Belenguer 等[21]設(shè)計(jì)割平面算法求解混合CARP 的下界.Krushinsky 等[31]建立了多車場(chǎng)CARP 的混合整數(shù)規(guī)劃模型,設(shè)計(jì)了多組有效不等式改進(jìn)原模型的線性松弛模型,應(yīng)用分支切割算法精確求解.Chen 等[56,57]和劉洋等[95]設(shè)計(jì)分支切割算法精確求解隨機(jī)CARP.Christiansen 等[87]和Bartolini等[106]分別設(shè)計(jì)分支定價(jià)算法求解隨機(jī)CARP 和考慮空轉(zhuǎn)需求的CARP.綜上,經(jīng)典CARP 精確算法的研究已較為成熟,而鑒于CARP 變異問題的復(fù)雜性,求解變異問題的精確算法較有限.

3.2 構(gòu)造啟發(fā)式算法

對(duì)于經(jīng)典CARP,常見構(gòu)造啟發(fā)式算法包括Path-Scanning,Augment-Merge 和Construct-Strike 三類構(gòu)造啟發(fā)式算法[12];并行插入算法(parallel insert method)[125]和三階段分割算法[98].后續(xù)研究改進(jìn)上述構(gòu)造啟發(fā)式算法,以提高其求解速度或用于求解CARP 變異問題.

Pearn[126]將Construct-strike 算法和最小生成樹算法相結(jié)合以提高計(jì)算效率,將Path-scanning 算法的單一路徑掃描準(zhǔn)則改進(jìn)為混合準(zhǔn)則.隨后Pearn[127]又提出兩種新的Augment-Insert 算法.Prins 等[128]通過改進(jìn)路徑分割準(zhǔn)則,獲得更高效的Ulusoy 啟發(fā)式算法求解CARP 及其變異問題.Santos 等[129]基于Path-Scanning算法提出了一種基于橢圓法則的CARP 啟發(fā)式算法.當(dāng)車輛接近每條路線的終點(diǎn)時(shí), 只選擇橢圓內(nèi)的邊.Arakaki 等[130]引入效率法則的概念,在給定當(dāng)前車輛位置、行駛距離和服務(wù)需求的情況下,選擇最有希望的弧進(jìn)行下一步服務(wù),基于此提出一種新的Path-Scanning 算法.以上兩種法則均顯著提高已有Path-Scanning算法的效率.Gonzalez-Martin 等[131]根據(jù)C-W 節(jié)約法, 設(shè)計(jì)了基于節(jié)約的啟發(fā)式算法, 并據(jù)此設(shè)計(jì)了多起點(diǎn)隨機(jī)算法RandSHARP.Wohlk 等[132]提出了一種先將圖分解為區(qū)域,然后迭代優(yōu)化、合并和分割的思路.這種方法避免了每次迭代都對(duì)完整的圖進(jìn)行搜索,從而快速求解大規(guī)模CARP.對(duì)于CARP 變異問題,Belenguer 等[21]針對(duì)五種更貼近實(shí)際應(yīng)用的CARP 變異問題,拓展了求解CARP 的三種構(gòu)造啟發(fā)式算法.Kirlik 等[105]改進(jìn)Ulusoy 啟發(fā)式算法,并求解考慮空轉(zhuǎn)需求的CARP.Willemse 等[53,54]則改進(jìn)了Ulusoy 啟發(fā)式算法、Path-Scanning 算法和Improved-Merge 算法,求解考慮時(shí)間限制和中間設(shè)施的CARP.Amponsah等[77]設(shè)計(jì)了一種基于前瞻性策略(look-ahead strategy)的啟發(fā)式算法求解多目標(biāo)CARP.Oliveira 等[133]將原始模型分解為更易求解的子模型, 設(shè)計(jì)Relax-and-Fix 啟發(fā)式算法求解多周期CARP.該分解形式可減少45%的不可行問題.融合問題特性的構(gòu)造啟發(fā)式算法可以得到高質(zhì)量的可行解,而元啟發(fā)式算法能夠進(jìn)一步優(yōu)化初始可行解,因此更多研究關(guān)注集成構(gòu)造啟發(fā)式算法和元啟發(fā)式算法的混合算法.

3.3 元啟發(fā)式算法

1)禁忌搜索算法

Hertz[134]首次提出求解經(jīng)典CARP 的禁忌搜索(tabu search,TS)算法——CARPET,測(cè)試GDB 和VAL 基準(zhǔn)算例分別求得約87% 和62% 的最優(yōu)解.Greistorfer[135]提出了一種TS 和分散搜索混合算法.Brandao等[15]提出了一種確定性TS 算法,該算法不需要設(shè)置隨機(jī)參數(shù)值,因此其計(jì)算結(jié)果是可復(fù)現(xiàn)的.以上兩種算法求解效率均高于CARPET.Mei 等[136]提出了一種將全局修復(fù)算子與TS 算法結(jié)合的修復(fù)禁忌搜索算法,該算子有效提高了禁忌搜索的效率,并適用于其它元啟發(fā)式算法.Tfaili 等[137]設(shè)計(jì)基于稀疏圖的禁忌搜索算法,其性能優(yōu)于商業(yè)優(yōu)化求解器CPLEX.但正剛等[138]設(shè)計(jì)小環(huán)路算法構(gòu)造經(jīng)典CARP 可行解,應(yīng)用TS算法進(jìn)一步優(yōu)化.Amberg 等[26]針對(duì)多車場(chǎng)CARP 設(shè)計(jì)基于先排序后聚類方法的TS 算法,該算法在求解回路多、無需求弧少的算例時(shí)更有優(yōu)勢(shì).Yu 等[104]應(yīng)用基于樹模型的禁忌搜索(forest-based TS)算法求解需求可分的混合CARP.

2)鄰域搜索算法

Beullens 等[16]設(shè)計(jì)導(dǎo)向局部搜索(guided local search, GLS)算法求解經(jīng)典CARP,利用鄰域列表和邊緣標(biāo)記機(jī)制來提高求解質(zhì)量和速度,并測(cè)試GDB、KSHS 和VAL 基準(zhǔn)算例,相比CARPET 改進(jìn)了8 個(gè)上界.Muyldermanse 等[48]提出了類似的GLS 算法求解考慮多車艙的CARP.Chen 等[75]則提出了兩階段混合鄰域搜索算法求解最小化車輛數(shù)和總成本的多周期CARP.第一階段給出車輛數(shù)盡可能小的可行解,第二階段在第一階段基礎(chǔ)上應(yīng)用局部搜索算法優(yōu)化可行解,以降低總成本.Wang 等[93]提出一種基于隨機(jī)鄰域搜索的分布估計(jì)算法,用于求解隨機(jī)CARP.Herzt 等[139]設(shè)計(jì)了求解經(jīng)典CARP 的變鄰域下降(variable neighborhood descent, VND)算法, 對(duì)變鄰域搜索中不同鄰域進(jìn)行多次下降, 直到達(dá)到所有考慮鄰域的局部最優(yōu)值.在處理大規(guī)模問題時(shí), 該算法優(yōu)于CARPET.Tagmouti 等[62]設(shè)計(jì)VND 算法求解受時(shí)間影響的CARP.孫錫梅等[112]針對(duì)同時(shí)配送和回收的CARP 設(shè)計(jì)局部搜索算法,混合5 種鄰域結(jié)構(gòu),并采用了一種分層的局部搜索策略,擴(kuò)大VND 算法的搜索空間.Polacek 等[42]、金倩倩等[109]分別應(yīng)用變鄰域搜索算法求解考慮中間設(shè)施和帶收益的CARP.自適應(yīng)大規(guī)模鄰域搜索(adaptive large neighbourhood search,ALNS)算法與一般鄰域搜索算法的區(qū)別在于其能夠根據(jù)歷史解的質(zhì)量自適應(yīng)選擇好的算子對(duì)解進(jìn)行破壞與修復(fù),從而提高解的質(zhì)量.Laporte 等[88]設(shè)計(jì)ALNS 算法求解隨機(jī)CARP,實(shí)驗(yàn)驗(yàn)證ALNS 優(yōu)于已有算法.Riquelme-Rodriguez 等[83]針對(duì)多周期CARP,設(shè)計(jì)了結(jié)合8 種鄰域搜索算子的ALNS.Mofid-Nakhaee 等[50]將ALNS 算法與鯨魚優(yōu)化算法相混合,求解考慮多車艙異構(gòu)車輛的CARP.王立斌等[89,90]采用隨機(jī)路徑掃描構(gòu)建初始解集,設(shè)計(jì)求解隨機(jī)CARP 的自適應(yīng)局部搜索算法和概率型鄰域搜索算法,實(shí)驗(yàn)證明了該算法優(yōu)于ALNS 算法.

貪婪隨機(jī)自適應(yīng)搜索過程(greedy randomized adaptive search procedure, GRASP)是一種半貪婪算法與多起點(diǎn)框架中的局部搜索方法混合的元啟發(fā)式算法.Usberti 等[140]在GRASP 中加入路徑重連(pathrelinking)機(jī)制以提高經(jīng)典CARP 的求解速度.Prins 等[128]設(shè)計(jì)基于Tour-Splitting 啟發(fā)式的GRASP 和迭代鄰域搜索算法求解CARP 及其變異問題.Belenguer 等[103]針對(duì)需求可分CARP 提出了集成GRASP、迭代局部搜索等算法的多起點(diǎn)進(jìn)化局部搜索算法,并結(jié)合變鄰域下降過程進(jìn)一步強(qiáng)化算法.

3)蟻群算法

Lacomme 等[141]首次提出應(yīng)用蟻群優(yōu)化算法(ant colony optimization, ACO)求解經(jīng)典CARP.Santos等[142]提出了一種改進(jìn)的蟻群優(yōu)化算法求解經(jīng)典CARP,對(duì)路徑選擇準(zhǔn)則、鄰域搜索算子、解的排序方式和迭代終止準(zhǔn)則進(jìn)行優(yōu)化,求解效率顯著優(yōu)于前者.張煒等[143]將ACO 與構(gòu)造啟發(fā)式算法相結(jié)合,設(shè)計(jì)了基于先排序后聚類原則下求解經(jīng)典CARP 的分割算法.Bautista 等[144]將考慮轉(zhuǎn)向限制的混合CARP 問題轉(zhuǎn)化為不對(duì)稱的點(diǎn)路徑問題,應(yīng)用基于ACO 的啟發(fā)式算法求解.劉潔等[20]將CARP 轉(zhuǎn)化為CVRP,設(shè)計(jì)聚類蟻群算法求解類似問題.Xing 等[19]則提出一種根據(jù)已獲得的解信息動(dòng)態(tài)調(diào)整算法參數(shù)的混合蟻群優(yōu)化算法求解該問題.Ghiani 等[41]設(shè)計(jì)了求解考慮中間設(shè)施和行駛距離受限的CARP 的蟻群優(yōu)化算法.Tirkolaee等[37,39]針對(duì)中等規(guī)模和大規(guī)模的多行程CARP 提出了基于田口參數(shù)設(shè)計(jì)方法的蟻群優(yōu)化算法.

4)模因算法

Lacomme 等[17]首次提出將遺傳算法與局部搜索結(jié)合求解CARP 及其變異問題的模因算法(memetic algorithm,MA),求解結(jié)果優(yōu)于CARPET.Lacomme 等[18]進(jìn)一步改進(jìn)了前文的模因算法,提高了求解CARP及其變異問題的效率,并證明該算法在解決不同目標(biāo)函數(shù)問題時(shí)的適應(yīng)性.Lacomme 等[67]設(shè)計(jì)包含鄰域搜索的多目標(biāo)遺傳算法求解多目標(biāo)CARP,該算法在求解單目標(biāo)問題時(shí)同樣有優(yōu)勢(shì).

Tang 等[145]提出了具有擴(kuò)展鄰域的模因算法(MA with extended neighborhood search, MAENS)求解混合CARP,設(shè)計(jì)了MS(merge-split)局部搜索算子,確保不陷入局部最優(yōu).在其基礎(chǔ)上,文獻(xiàn)[68–70]針對(duì)多目標(biāo)CARP 提出了基于分解的MAENS 和多種群協(xié)同進(jìn)化算法框架,通過合作的方式為相鄰子問題提供有用的信息.Mei 等[146]、Shang 等[71]采用協(xié)同進(jìn)化框架和路徑距離分組(route distance grouping)分解大規(guī)模問題,再應(yīng)用MAENS 算法求解分解后的小問題,分別求解最大包含375 條弧的混合和多目標(biāo)CARP 大規(guī)模算例.Liu 等[147]設(shè)計(jì)基于多序列對(duì)比的模因算法求解包含999 條弧的大規(guī)?；旌螩ARP 算例.Tang 等[148]則針對(duì)混合CARP 開發(fā)基于分層分解的模因算法,求解最大包含3 584 條弧的基準(zhǔn)算例.

局部搜索算子的設(shè)計(jì)直接影響模因算法的求解效率, 因此部分學(xué)者對(duì)局部搜索算子進(jìn)行研究.除了Tang 等[145]提出的MS 算子外, Chen 等[149]針對(duì)經(jīng)典CARP, 設(shè)計(jì)了基于路徑的交叉算子.劉天堂等[150]和Liu 等[151]則通過加強(qiáng)局部搜索提高求解經(jīng)典CARP 的效率.Wang 等[152]提出了一種基于排序(rank-based)的鄰域搜索算子,并求解混合CARP.Zhang 等[74]提出了一種新的路徑分解(route decomposition)局部搜索算子,并求解多周期CARP.

5)其它算法

Shang 等[153]提出了求解混合CARP 的免疫克隆選擇(immune clonal selection, ICS)算法.首先, 應(yīng)用GRASP 生成初始抗體種群.其次, 通過對(duì)同一抗體的不同克隆采用不同的策略, 促進(jìn)抗體之間的合作和信息交換,而且增加多樣性, 加快收斂速度.Shang 等[72]設(shè)計(jì)基于有向進(jìn)化的免疫克隆算法求解多目標(biāo)CARP.

6)算法總結(jié)

元啟發(fā)式算法適用范圍廣且求解效果好,因此受到廣泛的關(guān)注.其中,結(jié)構(gòu)較為簡(jiǎn)單的禁忌搜索算法最早受到研究人員的關(guān)注,同時(shí)期易于拓展到其它問題的模因算法得到重視,但考慮到模因算法參數(shù)復(fù)雜,部分研究人員關(guān)注到結(jié)果可復(fù)現(xiàn)的導(dǎo)向局部搜索和確定性禁忌搜索算法,隨后變鄰域搜索、蟻群優(yōu)化、自適應(yīng)大規(guī)模鄰域搜索和貪婪隨機(jī)自適應(yīng)搜索過程等算法均被應(yīng)用于求解CARP 及其變異問題,表2 為以上算法求解經(jīng)典CARP 基準(zhǔn)算例的結(jié)果比較.如何發(fā)揮各算法的優(yōu)勢(shì),設(shè)計(jì)高效的混合元啟發(fā)式算法是近期研究的主要方向之一.

表2 元啟發(fā)式算法求解經(jīng)典CARP 基準(zhǔn)算例結(jié)果匯總Table 2 Summary of comparison results for CARP meta-heuristics

4 CARP 應(yīng)用分類和研究進(jìn)展

考慮容量限制的弧路徑優(yōu)化問題的應(yīng)用背景非常廣泛,已有研究主要集中在垃圾回收和道路管理兩方面.隨著問題的逐步細(xì)化,研究人員也應(yīng)用CARP 解決其它實(shí)際問題,例如:“地圖車”調(diào)度問題(mapping van problem)、農(nóng)業(yè)灌溉問題等.

4.1 垃圾回收

根據(jù)垃圾回收的具體情況,回收車輛路徑規(guī)劃可以被抽象為CARP 或CVRP.一般對(duì)于每個(gè)回收點(diǎn)垃圾產(chǎn)量遠(yuǎn)小于車艙容量的情況,或者需求和成本數(shù)據(jù)是以弧為單位存儲(chǔ)的情況,會(huì)優(yōu)先選擇建立CARP 模型[154,155]來求解.

文獻(xiàn)[35,144,156]研究了里斯本和巴塞羅那垃圾回收車輛的CARP 問題.文獻(xiàn)[36–39]研究了多行程、多目標(biāo)、多周期、不確定性、考慮碳排放以及考慮工作時(shí)長(zhǎng)等城市垃圾回收CARP 問題.劉潔等[20]研究考慮實(shí)際交通情況的城市垃圾回收車輛路徑問題,根據(jù)成都市雙楠轄區(qū)的真實(shí)數(shù)據(jù)求解該問題.

Sniezek 等[101]研究了考慮住宅區(qū)部分狹小道路大車通行不便情況下車輛/站點(diǎn)依賴的CARP.De Rosa等[47]研究了在垃圾回收中, 清運(yùn)車回收分布于弧上的垃圾, 運(yùn)至中轉(zhuǎn)站粉碎或壓縮, 再通過大容量卡車運(yùn)輸?shù)嚼幚韴?chǎng)的弧路徑調(diào)度問題.Thomaz 等[60]解決了垃圾回收中帶時(shí)間窗的多周期CARP 問題.Amponsah 等[77]考慮了垃圾回收中的環(huán)境影響.

隨著垃圾分類的推進(jìn),關(guān)于垃圾分類回收問題的研究受到了關(guān)注.Kiilerich 等[51]提出了垃圾分類回收催生的一系列新問題.Zbib 等[49]、Mofid-Nakhaee 等[50]、Zbib 等[52]主要研究垃圾分類回收中應(yīng)用多艙車輛分類清運(yùn)的問題.Wohlk 等[84]關(guān)注垃圾分類回收多周期協(xié)調(diào)問題.

4.2 冬季道路管理

冬季道路管理問題中的道路消雪、除冰等可被抽象成CARP.Li 等[14]以冬季除雪為背景,研究了考慮多車場(chǎng)、中途補(bǔ)貨、時(shí)間限制和道路優(yōu)先級(jí)等實(shí)際約束的CARP 問題.Tagmouti 等[63]研究了冬季除雪中,需求和服務(wù)成本隨氣候變化的動(dòng)態(tài)CARP.Perrier 等[157]建立考慮轉(zhuǎn)彎限制、等級(jí)目標(biāo)、負(fù)載平衡和串聯(lián)服務(wù)需求的CARP 模型優(yōu)化冬季除雪問題.謝秉磊等[158]建立了融雪劑撒布車輛路徑模型和帶臨時(shí)補(bǔ)充點(diǎn)的融雪劑撒布車輛路徑模型.Liu 等[159]研究了加拿大埃德蒙頓市冬季除雪案例,并對(duì)CARP 的參數(shù)進(jìn)行靈敏度分析,為冬季道路養(yǎng)護(hù)工作提供決策依據(jù).

4.3 灑水車調(diào)度

灑水車調(diào)度問題分為城市道路的灑水車調(diào)度問題和露天礦場(chǎng)等特殊場(chǎng)所的灑水車調(diào)度問題.李小花等[27]研究了城市道路中考慮多車場(chǎng)的灑水車路徑規(guī)劃問題.Yu 等[104]考慮到城市道路灑水過程中,一條道路可以由多輛車提供服務(wù)的情況,求解需求可分的CARP.Riquelme-Rodriguez 等[82,83]研究了露天礦場(chǎng)灑水抑塵作業(yè)中考慮庫存約束的PCARP.將道路濕度(需求)轉(zhuǎn)化為庫存約束,通過設(shè)置最大庫存(濕度)和安全庫存(濕度)來判斷是否需要灑水.

4.4 其它應(yīng)用

Chapleau 等[125]研究了關(guān)于校車路徑規(guī)劃的CARP.Vansteenwegen 等[58]研究了“地圖車”調(diào)度問題.Chen等[56,149]、徐磊等[94]、劉洋等[95]研究了高速路網(wǎng)日常養(yǎng)護(hù)工作中的隨機(jī)CARP.胡珊等[46]研究了路面交通標(biāo)志刷漆問題.Su 等[96]研究鐵路檢修中的隨機(jī)CARP.Khajepour 等[160]建立CARP 模型,解決了農(nóng)業(yè)灌溉中田間收獲路徑規(guī)劃問題,并找到最佳遍歷順序.CARP 及其變異問題已經(jīng)被廣泛應(yīng)用在各類生活場(chǎng)景中,但提煉問題依賴大量假設(shè),設(shè)計(jì)更貼合實(shí)際的模型對(duì)指導(dǎo)實(shí)踐更有意義.

5 結(jié)束語

經(jīng)過近40年的發(fā)展,帶容量限制的弧路徑優(yōu)化問題已有豐富的研究成果.經(jīng)典問題的研究較成熟,近幾年等多集中在CARP 的變異問題及其高效求解算法的研究.根據(jù)國(guó)內(nèi)外研究現(xiàn)狀來看, 國(guó)內(nèi)學(xué)者目前對(duì)CARP 變異問題的研究較為有限,更傾向于算法研究,缺少結(jié)合國(guó)內(nèi)實(shí)際管理問題的應(yīng)用研究.后續(xù)研究主要考慮三個(gè)方向:非線性和隨機(jī)問題的攻克、融合機(jī)器學(xué)習(xí)等新技術(shù)的算法設(shè)計(jì)和CARP 及其變異問題的新應(yīng)用.

1)非線性和隨機(jī)CARP

現(xiàn)有研究以混合整數(shù)線性優(yōu)化問題為主,較少涉及非線性問題.目前,單車弧路徑優(yōu)化問題和考慮容量約束的點(diǎn)路徑優(yōu)化問題中已經(jīng)出現(xiàn)了關(guān)于非線性問題的建模及求解研究,如何拓展這些方法求解多車問題,需要進(jìn)一步的研究.隨機(jī)問題更具有實(shí)際應(yīng)用價(jià)值,現(xiàn)有隨機(jī)問題的研究主要考慮需求的不確定性,對(duì)考慮時(shí)間等要素不確定性和動(dòng)態(tài)調(diào)度的研究較為有限,且處理方法主要依賴提供救援服務(wù)[56,161]或增大調(diào)度方案的魯棒性[57,92].后續(xù)研究考慮應(yīng)用隨機(jī)規(guī)劃的相關(guān)技術(shù)優(yōu)化隨機(jī)CARP 及其變異問題.

2)融合機(jī)器學(xué)習(xí)機(jī)制的高效算法

隨著機(jī)器學(xué)習(xí)、大數(shù)據(jù)等新技術(shù)的發(fā)展,越來越多的新技術(shù)被用于求解組合優(yōu)化問題.后續(xù)研究考慮設(shè)計(jì)與機(jī)器學(xué)習(xí)相結(jié)合的元啟發(fā)式算法.例如, 通過機(jī)器學(xué)習(xí)方法來自適應(yīng)選擇鄰域搜索算法, 從而提高CARP 及其變異問題的求解速度.充分利用CVRP 和CARP 的相似性,通過域間學(xué)習(xí)的思想提高求解效率[162].與大數(shù)據(jù)分析相結(jié)合,研究實(shí)時(shí)路徑規(guī)劃問題,設(shè)計(jì)針對(duì)CARP 及其變異問題的數(shù)據(jù)驅(qū)動(dòng)算法[52].

3) CARP 及其變異問題的新應(yīng)用

未來研究考慮從應(yīng)用角度進(jìn)行拓展,設(shè)計(jì)符合特定應(yīng)用場(chǎng)景下的特定約束,設(shè)計(jì)更符合實(shí)踐的CARP新模型,例如:與國(guó)內(nèi)垃圾分類大趨勢(shì)結(jié)合,研究更適合發(fā)展中國(guó)家或者人口密集城市的回收管理模式及其CARP 模型,解決現(xiàn)有回收工作中運(yùn)輸效率低下、垃圾中轉(zhuǎn)站負(fù)荷過重、垃圾卸載環(huán)節(jié)擁堵等問題;關(guān)注道路灑掃、垃圾清運(yùn)等市政工作對(duì)環(huán)境及市民正常生活的不良影響,研究與能耗、環(huán)境結(jié)合的多目標(biāo)CARP或考慮時(shí)間窗和收益值的問題[163]; 與新興產(chǎn)業(yè)技術(shù)相結(jié)合, 研究與無人機(jī)、無人車路徑優(yōu)化問題相關(guān)的CARP[164]等;關(guān)注開放、多行程、動(dòng)態(tài)CARP 在應(yīng)急管理相關(guān)問題[165]中的應(yīng)用.