考慮一致性約束的車輛路徑問題綜述

李路遙，沈一帆，夏 俊，沈海輝

考慮一致性約束的車輛路徑問題綜述

李路遙，沈一帆，夏 俊，沈海輝

(上海交通大學(xué)，中美物流研究院，上海 200030)

車輛路徑問題是物流和交通運(yùn)輸領(lǐng)域的研究熱點(diǎn)。近年來，為應(yīng)對激烈的市場競爭，越來越多的企業(yè)開始關(guān)注如何在降低成本的同時保證服務(wù)效率和服務(wù)質(zhì)量。實(shí)踐表明提高車輛路徑方案的一致性不僅可以提高服務(wù)效率，還能顯著提高客戶滿意度。因此，考慮一致性約束的車輛路徑問題(又稱一致性車輛路徑問題)應(yīng)運(yùn)而生。一致性車輛路徑問題是相對較新的車輛路徑問題變種，相關(guān)成果具有重要的實(shí)踐和學(xué)術(shù)價值。隨著多樣化一致性約束的提出以及相關(guān)數(shù)學(xué)模型和優(yōu)化方法的迭代更新，目前針對一致性車輛路徑問題已有一定數(shù)量的研究積累。本文從車輛路徑問題的分類、一致性車輛路徑問題的背景介紹、模型、求解算法等方面對該問題進(jìn)行了綜述。在一致性車輛路徑問題中，一致性約束主要有時間一致性、人員一致性和路線一致性要求。時間一致性和人員一致性約束較為常見，路線一致性約束則相對更為新穎。一致性車輛路徑問題的求解方法以啟發(fā)式算法為主，尤其是大、中型實(shí)例(時間周期5d，客戶數(shù)量50以上)的求解；而部分精確式算法對中小型實(shí)例(時間周期3～5d，客戶數(shù)量50及以下)也展現(xiàn)了良好的性能。

物流工程；一致性車輛路徑問題；時間一致性；人員一致性；路徑一致性；文獻(xiàn)綜述

0 引 言

隨著物流行業(yè)的不斷發(fā)展，物流業(yè)對國民生產(chǎn)總值的貢獻(xiàn)程度越來越大，作為“第三利潤源”的物流業(yè)也受到越來越廣泛的關(guān)注。面對激烈的市場競爭，如何降本增效是物流企業(yè)持續(xù)關(guān)注的問題。在物流運(yùn)輸中，燃油消耗是主要的成本。車輛路徑問題(Vehicle Routing Problem，VRP)的目的就是在滿足運(yùn)輸要求的前提下縮短車輛總行駛距離，以達(dá)到節(jié)約運(yùn)輸成本的效果。這不僅可以節(jié)約成本、增加利潤，還可以減少尾氣排放，提升客戶滿意度。因此，VRP一直是物流服務(wù)領(lǐng)域研究的熱點(diǎn)問題。

VRP最早由Dantzig和Ramser[1]于1959年提出，其目的是在滿足服務(wù)需求約束的前提下，尋找到最優(yōu)路線或近似最優(yōu)路線。經(jīng)典VRP可以簡述為：已知一個配送起點(diǎn)和若干客戶需求點(diǎn)的位置和兩點(diǎn)之間的距離，在滿足車輛容積約束和所有客戶需求的條件下，求解出一條距離最短的車輛行駛路徑。隨著實(shí)際需求的不斷變化，各種變種VRP層出不窮，較為常見的VRP變種問題有以下幾大類：

(1)有裝載約束的車輛路徑問題。裝載約束是車輛路徑問題中最關(guān)鍵的因素之一，在實(shí)際應(yīng)用中也最為常見。主要的裝載約束有車輛容積約束、裝載方式約束。有車輛容積約束的車輛路徑問題可分為容積限制的車輛路徑問題(CapacitatedVehicle Routing Problem，CVRP)、多車型車隊的車輛路徑問題(Heterogeneous Fleet Vehicle Routing Problem，HFVRP)和甩掛運(yùn)輸車輛路徑問題(Truck and Trailer Vehicle Routing Problem，TTVRP)。CVRP的約束中，車輛的類型和容積都是相同的[2]，但是在實(shí)際問題中，運(yùn)輸企業(yè)的車輛并不一定完全相同，因此有了HFVRP。不同于CVRP，HFVRP擁有不同容積和使用成本的車型[3]。隨著實(shí)際情況的變化，有些企業(yè)的貨物是通過甩掛運(yùn)輸?shù)姆绞綖榭蛻暨M(jìn)行配送[4]，因此有了TTVRP。裝載方式約束主要是指在車輛路徑問題中，貨物的裝箱方式、裝箱順序和方向有一定的要求。例如二維裝載車輛路徑問題(Vehicle Routing Problem with Two-dimensional Loading Constraints, 2L-CVRP)不僅要規(guī)劃車輛路線，還要考慮貨物的長度和寬度限制。根據(jù)貨物的裝箱順序和方向要求，也可以將其作為問題的約束，于是出現(xiàn)了有方向的2L-CVRP[5]等變種問題。除此之外，在實(shí)際問題中，部分貨物尤其是易碎品的運(yùn)輸需要考慮貨物的高度或堆疊問題，例如家電在運(yùn)輸過程中需要利用廂式貨車運(yùn)輸并遵循“不可堆疊”或“重不壓輕”的原則，三維裝載車輛路徑問題[6]應(yīng)運(yùn)而生(Vehicle Routing Problem with Three-dimensional Loading Constraints, 3L-CVRP)。

(2)同時取送貨的車輛路徑問題。經(jīng)典的VRP要求車輛完成配送后返回出發(fā)地即可，但在實(shí)際運(yùn)營中，貨物交付并不完全意味著運(yùn)輸過程的完成，客戶的退換貨、郵件收取等業(yè)務(wù)還要求配送車輛在送貨后完成取貨的過程。因此，出現(xiàn)了同時取送貨的車輛路徑問題(VRP with Simultaneous Pickups and Deliveries, VRPSPD)。VRPSPD要求車輛在為客戶配送貨物的過程中同時收取客戶的退貨或是郵件并裝入車輛后返回出發(fā)地[7]。

(3)帶時間窗的車輛路徑問題。帶時間窗的車輛路徑問題(VRP with Time Windows, VRPTW)十分常見，即客戶希望在某一時段中收到貨物，運(yùn)輸車輛需要在該時段內(nèi)到達(dá)配送點(diǎn)。VRPTW又可以分為帶硬時間窗的VRP和帶軟時間窗的VRP。硬時間窗要求車輛不能晚于時間窗結(jié)束的時間到達(dá)，如果到達(dá)過早需要等待[8]；軟時間窗對時間窗的約束有了一定的松弛，允許車輛遲到，但是車輛遲到需要付出額外的成本[9]。

(4)周期性車輛路徑問題。周期性車輛路徑問題(Period Vehicle Routing Problem, PVRP)是指在服務(wù)周期內(nèi)，客戶可能需要多天的服務(wù)，因此公司會生成幾天的路線來拜訪已知服務(wù)頻率的客戶[10]，即針對一段時期內(nèi)的固定訂單制定配送計劃，目標(biāo)是使得車輛總行駛距離最小。PVRP最早由Beltrami和Bodin[11]于1974年提出，其最初目的是解決城市垃圾車輛的路徑規(guī)劃問題，后來PVRP廣泛應(yīng)用于一些有固定服務(wù)需求的問題，例如快遞配送、電梯的保養(yǎng)和維修、自動售貨機(jī)和便利店補(bǔ)貨[12]等。

除了上述四類常見的VRP變種問題外，還有諸如動態(tài)VRP、開放式VRP、多級VRP、綠色VRP[13]等問題。本文討論的一致性車輛路徑問題(Consistent Vehicle Routing Problem, ConVRP)屬于考慮服務(wù)水平和客戶滿意度的周期性VRP，其中一致性要求是指在一定周期內(nèi)的服務(wù)水平需要保持一致，例如在多天的服務(wù)周期內(nèi)，同一司機(jī)需要大約在每個服務(wù)日的同一時間段內(nèi)拜訪同一個客戶[14]。ConVRP是由CVRP和PVRP擴(kuò)展而來[15]，部分ConVRP中也增加了時間窗約束或是同時取送貨約束。與PVRP類似，ConVRP也是在一定時期內(nèi)的多次規(guī)劃，不同點(diǎn)在于PVRP重點(diǎn)是成本最低，ConVRP重點(diǎn)在于一致性要求，當(dāng)關(guān)注重點(diǎn)不同時，整體方法會產(chǎn)生不一致的路線安排[16]。

1 一致性車輛路徑問題背景介紹

一致性車輛路徑問題最早由Gro?r等[14]于2009年提出，其出現(xiàn)源于快遞公司和小件物流公司對客戶服務(wù)水平的關(guān)注。2000年以來，國際快遞物流公司逐漸將重點(diǎn)從以車隊為中心轉(zhuǎn)移到以客戶為中心，通過提升客戶滿意度以增加每個客戶的終身價值。在周期性車輛路徑問題中，客戶滿意度是持續(xù)服務(wù)的結(jié)果，要求一定周期內(nèi)服務(wù)水平的一致性。例如，一些小件物流公司的實(shí)踐表明，提供一致的服務(wù)比節(jié)省1%～3%的運(yùn)輸成本更為重要[14]。以UPS為例，其司機(jī)通常會在一條固定的路線上工作很多年，司機(jī)與客戶間存在密切聯(lián)系[17]。在此基礎(chǔ)上，早在2007年，UPS就已正式提供一致性服務(wù)，使得司機(jī)可以維護(hù)良好的客戶關(guān)系，在配送同時能收集客戶周圍的業(yè)務(wù)信息或銷售線索，產(chǎn)生額外的收益，這為公司帶來了巨大的經(jīng)濟(jì)效益[14]。從此，一致性車輛路徑問題逐漸進(jìn)入人們視野。

所有ConVRP描述基本相似，即一組司機(jī)在多個時間段內(nèi)訪問同一組客戶，目標(biāo)通常是一致性要求下的運(yùn)輸成本最小。該操作過程也會受到車輛容積、有限的時間窗、有限工作人員等條件的約束。每天的輸入?yún)?shù)是波動的，例如客戶只需要一定周期內(nèi)某些天的服務(wù)，因此需求每天都在變化。應(yīng)對每天變化的需求，最簡單的方法是每天都重新優(yōu)化路線。然而，這種方法實(shí)際并不可行，因?yàn)橐环矫妫拘枰刻飓@取客戶數(shù)據(jù)，在很短的時間內(nèi)計算新的路線，并將路線轉(zhuǎn)發(fā)給司機(jī)，這個過程工作量較大、對計算效率要求高；另一方面，司機(jī)面對每天不同的路線，學(xué)習(xí)負(fù)擔(dān)重，容易降低服務(wù)質(zhì)量。因此不能單純地將每天優(yōu)化路線作為解決此類問題的辦法，針對ConVRP設(shè)計專門的方法就顯得尤為重要。

1.1 ConVRP應(yīng)用場景

ConVRP在實(shí)際中有很多應(yīng)用場景，主要有以下幾類：

(1)快遞配送中的一致性。近年來隨著電商行業(yè)的迅速發(fā)展，包裹量激增，快遞行業(yè)也迎來了快速發(fā)展時期。在激烈的市場競爭中，不少快遞公司選擇采用“價格戰(zhàn)”的方式搶占市場份額。然而除了價格優(yōu)勢外，快遞公司在市場競爭的另一關(guān)鍵因素是服務(wù)質(zhì)量。2008年，Richard[18]調(diào)研發(fā)現(xiàn)，快遞配送及小件物流與其他運(yùn)輸?shù)闹饕獏^(qū)別在于對服務(wù)一致性的要求。經(jīng)常需要快遞服務(wù)的客戶希望每天能在大致相同的時間被拜訪，因此一致性高的服務(wù)可以改善客戶關(guān)系；并且更高的客戶滿意度和司機(jī)對區(qū)域和客戶的熟悉程度帶來的經(jīng)濟(jì)效益會抵消因一致性而產(chǎn)生的更高的路線成本。例如快遞行業(yè)巨頭UPS在2003年就開始斥巨資研發(fā)可以提高一致性水平的路線規(guī)劃系統(tǒng)，盡管該系統(tǒng)部署成本超過2.95億美元，但是預(yù)計每年將為UPS節(jié)省3至4億美元，同時每年可以減少10萬t二氧化碳排放[19]。

(2)家庭護(hù)理中的一致性。隨著老齡化加劇及綜合醫(yī)院服務(wù)模式的轉(zhuǎn)變，衛(wèi)生保健從形式固定的保健護(hù)理(如療養(yǎng)院等)轉(zhuǎn)向家庭護(hù)理。家庭護(hù)理服務(wù)使病人能夠盡可能自主地住在家里，同時由熟練的工作人員進(jìn)行探視和支持。通常，這項(xiàng)服務(wù)包括家政、送餐上門和醫(yī)療保健等[20]。醫(yī)護(hù)服務(wù)人員通常將護(hù)理連續(xù)性視為質(zhì)量目標(biāo)[21]，服務(wù)人員應(yīng)熟悉客戶的習(xí)慣、特點(diǎn)及身體狀況。因此，人員一致性簡化了相關(guān)人員的溝通和交接，可以顯著提高家庭護(hù)理的服務(wù)質(zhì)量。

(3)供應(yīng)商庫存管理中的一致性。在供應(yīng)商庫存管理中，補(bǔ)貨訂單的時間和數(shù)量從由客戶決策轉(zhuǎn)變?yōu)橛晒?yīng)商決策。對供應(yīng)商而言，面對激烈的市場競爭，單純關(guān)注成本已經(jīng)不足以滿足客戶需求，Coelho等[16]在IRP(Inventory Routing Problems)模型中加入了一致性要求，從而平衡了成本和服務(wù)質(zhì)量要求。

通過對一致性車輛路徑問題應(yīng)用場景的梳理，可以發(fā)現(xiàn)一致性要求在實(shí)際中具有重要意義。一方面，對于被服務(wù)的客戶而言，其享受到了更高質(zhì)量的服務(wù)；另一方面，對于企業(yè)和服務(wù)人員而言，它有利于企業(yè)在激烈的市場競爭中獲得優(yōu)勢，降低服務(wù)人員和司機(jī)的學(xué)習(xí)成本，提升人員的工作效率。

1.2 一致性需求的分類

ConVRP的一致性要求一般分為三類：時間一致性(Time Consistency, TC)、人員一致性(Driver Consistency, DC)和路線一致性(Route Consistency, RC)。TC表示在服務(wù)周期內(nèi)，同一個客戶在每個服務(wù)日的同一時間段內(nèi)被服務(wù)，主要應(yīng)用在快遞配送、牛奶配送等場景中；DC表示在服務(wù)周期內(nèi)，同一個客戶每次都由同一個(或幾個)服務(wù)人員服務(wù)，主要應(yīng)用于家庭護(hù)理、家政服務(wù)等問題中；RC表示在服務(wù)周期內(nèi)，企業(yè)給每個司機(jī)安排的路線盡量保持一致，主要通過考慮服務(wù)人員對路線或區(qū)域的熟悉程度來安排調(diào)度。TC和DC都是從客戶角度出發(fā)進(jìn)行研究，目的是提高客戶滿意度；而RC主要聚焦于企業(yè)，目的是提高管理效率，降低成本。

2 一致性車輛路徑問題模型

2.1 同時考慮TC和DC的ConVRP

Gro?r等[14]的模型具有開創(chuàng)性意義，后續(xù)的學(xué)者在研究ConVRP時都會參考該模型對問題進(jìn)行建模分析。Tarantilis等[23]、Kovacs等[24]、Xu等[25]在后續(xù)對求解ConVRP算法的研究中也基本沿用了Gro?r的模型。Campelo等[26]以醫(yī)藥配送中心的實(shí)際案例為基礎(chǔ)建立了具有TC和DC要求的ConVRP模型，基本思路與Gro?r的模型一致，區(qū)別是目標(biāo)函數(shù)由原來的最小化總行駛時間改為了最小化總行駛距離，其根本目的都是最小化成本；Goeke等[27]將Gro?r的模型進(jìn)一步優(yōu)化，使得變量更少，從而利用精確式算法解決ConVRP；Stavropoulou等[28]考慮實(shí)際應(yīng)用中的運(yùn)輸問題，在一致性車輛路徑問題模型的基礎(chǔ)上增加了對利潤的考慮，在Gro?r模型的基礎(chǔ)上將目標(biāo)函數(shù)更改為最大化企業(yè)利潤，對利潤和一致的客戶服務(wù)之間的權(quán)衡進(jìn)行研究，得出了管理見解；Zhen等[29]考慮了逆向物流中的客戶服務(wù)，將ConVRP與VRPSPD進(jìn)行結(jié)合，定義了同時取送貨的一致性車輛路徑問題并建立了相應(yīng)的混合整數(shù)規(guī)劃模型，在處理TC與DC的做法上與Gro?r等[14]一致。

之后，Kovacs等[31]繼續(xù)在單目標(biāo)模型的基礎(chǔ)上拓展，提出了多目標(biāo)廣義一致性車輛路徑問題(Multi-Objective Generalized Consistent Vehicle Routing Problem，MOGenConVRP)，其將DC、TC以及最小化路徑成本作為問題的多個獨(dú)立目標(biāo)。多目標(biāo)優(yōu)化方法能夠在沖突的目標(biāo)函數(shù)之間進(jìn)行更徹底的權(quán)衡分析，從而使得研究結(jié)果能輔助物流公司在成本和服務(wù)水平之間進(jìn)行權(quán)衡。Lian等[32]在研究中同樣提出了一個多目標(biāo)模型，將時間和人員一致性約束作為目標(biāo)進(jìn)行建模，該模型與Kovacs等[31]的模型類似，目標(biāo)函數(shù)如下：

式中：目標(biāo)函數(shù)(15)最小化總行駛時間；目標(biāo)函數(shù)(16)尋求最大限度地減少拜訪單個客戶的不同司機(jī)數(shù)量，即最優(yōu)化人員一致性；目標(biāo)函數(shù)(17)使到達(dá)不同客戶處的時間差最小化，即最優(yōu)化時間一致性。

2.2 考慮TC或DC的ConVRP

以上模型都是同時考慮了TC和DC要求，也有少量問題只需要考慮這兩種要求中的一種。Feillet等[33]針對殘疾人交通問題設(shè)計了時間一致性的車輛路徑問題模型，由于面對的實(shí)際問題不同，作者沒有通過限制最晚和最早服務(wù)時間之間的差異來確保時間一致性，而是通過時間類進(jìn)行時間一致性建模。作者定義了求解時間類最小類別數(shù)的模型，同時在Gro?r等[14]的模型基礎(chǔ)上不考慮DC，將TC限制為每個客戶允許的最大時間類別數(shù)，從而解決了殘疾人交通的時間一致性車輛路徑問題。

Lespay等[34]根據(jù)一個食品配送中心的實(shí)際問題，設(shè)計了有時間窗的人員一致性車輛路徑問題。不同于Gro?r等[14]的模型中沒有客戶時間窗約束的假定，該問題基于標(biāo)準(zhǔn)的VRPTW對問題建模，將時間窗作為硬性約束，除此之外，該問題還考慮DC要求，即服務(wù)周期內(nèi)每位客戶只由一位司機(jī)來服務(wù)，但該問題不考慮TC要求。在傳統(tǒng)的ConVRP中，駕駛員的數(shù)量是固定的，目標(biāo)是最小化總行駛時間，同時，客戶沒有時間窗口限制，但是訪問客戶應(yīng)該以最小的到達(dá)時間差來安排。而Lespay等[34]的模型以最小化駕駛員數(shù)量為目標(biāo)，同時保證人員一致性要求。

2.3 考慮RC的ConVRP

約束(18)和約束(19)保證了如果司機(jī)在不同的兩天內(nèi)行駛了同一條路徑，則司機(jī)在這兩天內(nèi)訪問的顧客及訪問順序是一致的。

2.4 考慮其他條件的ConVRP

除了對TC、DC和RC要求的考慮，劉恒宇等[35]還研究了交通擁堵及快遞人員工作量平衡性因素對配送路徑的影響，通過在模型中增加擁堵因子、利用均方差的形式刻畫工作量不平衡性，建立了混合整數(shù)規(guī)劃模型并利用基于模板路徑的模擬退火算法求解。結(jié)果發(fā)現(xiàn)：交通擁堵使最優(yōu)配送路徑的總行駛時間平均增加18.38%，使快遞人員在任意兩天到達(dá)同一顧客的最早與最晚時刻之差平均增加12.92%；當(dāng)快遞人員配件量的不平衡性平均下降35.82%后，二者僅分別平均增加2.29%和1.68%。黃琳[15]在論文中也考慮了路徑一致性和工作量平衡的車輛路徑問題，并分析了基于RC派生出的實(shí)際路徑行駛方案帶來的TC和DC效果。

綜上，ConVRP建模方法匯總于表1。

表1 一致性車輛路徑問題模型匯總

續(xù)表1

3 一致性車輛路徑問題求解方法

VRP是NP-hard問題，由于參數(shù)與約束眾多，求解較為困難，因此VRP求解通常使用啟發(fā)式算法。ConVRP約束比VRP更為復(fù)雜，是一個NP-hard組合優(yōu)化問題，因此大多數(shù)文獻(xiàn)中采用的是啟發(fā)式算法，極少數(shù)文獻(xiàn)采用精確式算法。

3.1 啟發(fā)式算法求解ConVRP

Gro?r等[14]首先提出了ConVRP并建立了整數(shù)規(guī)劃模型，然而該模型僅適用于小規(guī)模問題，對于大規(guī)模問題并不適用，因此作者根據(jù)ConVRP問題的特點(diǎn)基于記錄更新(Record-to- Record Travel, RTR)的算法設(shè)計了兩階段的啟發(fā)式算法。在第一階段，通過只考慮那些需要多天服務(wù)的客戶來生成一組模板路線；在第二階段，基于模板路線，通過從模板中刪除在第天不需要服務(wù)的客戶并加入僅在第天需要服務(wù)的客戶來創(chuàng)建所有日期的路線。該過程既保證了客戶在需要服務(wù)時總是由同一輛車來訪問，又保證了客戶訪問的順序?qū)⒆裱瓋?yōu)先原則。在設(shè)計路線的過程中主要采用局部搜索算法來改進(jìn)路線，保證客戶能在每天大致相同的時間接受服務(wù)。

Tarantilis等[23]設(shè)計了基于模板路線的禁忌搜索算法(Template-based Tabu Search Algorithm, TTS)，算法分為兩階段：首先，構(gòu)建一個主模板路線時間表，以確定服務(wù)順序和對需求頻繁客戶的服務(wù)分配；之后，基于主模板，為需求頻繁和不頻繁的客戶設(shè)計多天的實(shí)際車輛路線和服務(wù)時間表。在模板路線的基礎(chǔ)上，采用了禁忌搜索改進(jìn)方法，以順序的方式修改模板路線和實(shí)際的每日時間表，得到了比Gro?r等[14]的算法更好的結(jié)果：成本降低了4.76%，客戶最大的等待時間差異降低17%，部署車輛的平均數(shù)量從10.5輛減少到9.9輛。Kovacs等[24]提出了一種基于模板的自適應(yīng)大鄰域搜索算法，在求解速度和質(zhì)量上有了進(jìn)一步提升。劉恒宇等[36]提出用基于模板路徑的模擬退火算法求解ConVRP問題，算法分為兩階段，第一階段求解模板路徑，第二階段以所得模板路徑為參考獲得各天車輛具體配送路徑方案，兩個階段均采用模擬退火法進(jìn)行優(yōu)化，該方法在中小規(guī)模基準(zhǔn)數(shù)據(jù)集上得到了良好的驗(yàn)證。卞晨[37]借助蟻群算法，通過兩階段的信息素更新規(guī)則求解ConVRP，并驗(yàn)證了算法具有較高的求解效率和求解質(zhì)量。

對于GenConVRP，Kovacs等[30]沒有采用基于模板路徑的方法，而是基于靈活的大鄰域搜索算法設(shè)計了幾種破壞和修復(fù)試探法以便將顧客從路線上移除并重新插入到更合適的位置，TC約束通過簡單的2-opt算子改善。對于MOGenConVRP, Kovacs等[31]通過多方向大鄰域搜索算法最大可求解周期為5d、客戶數(shù)量為199的大型算例，并且發(fā)現(xiàn)該方法在提升70%到達(dá)時間一致性的同時僅增長3.84%的行駛成本，優(yōu)化效果較好。

Xu等[25]使用變鄰域搜索算法解決ConVRP，該算法由兩階段組成。在第一階段，應(yīng)用變鄰域搜索算法獲得近似最優(yōu)解，獲得的解決方案可能不可行。如果解決方案質(zhì)量可接受，則通過第二階段使其可行并進(jìn)一步優(yōu)化。通過數(shù)值實(shí)驗(yàn)對比，該算法優(yōu)化效果最好，盡管平均運(yùn)行時間上相比Kovacs等[24]的算法要長，但是考慮現(xiàn)在的CPU計算性能，多出的運(yùn)行時間可以忽略不計。Campelo等[26]在設(shè)計解決大規(guī)模算例的算法時，指出ConVRP的復(fù)雜性主要在于節(jié)點(diǎn)的數(shù)量，因此他們設(shè)計了一種基于FO(Fix-and-optimize)的方法，目的在于減少節(jié)點(diǎn)數(shù)量，試圖利用其結(jié)構(gòu)特點(diǎn)來解決這個問題；同時結(jié)合可變鄰域分解搜索原理，通過將問題分解為只考慮解空間的不同部分來解決大規(guī)模的問題，作者利用該方法分析了一家醫(yī)藥分銷公司的案例。Zhen等[29]分別根據(jù)記錄更新算法、可變鄰域局部搜索算法和基于禁忌搜索算法的原理提出了三種啟發(fā)式方法，數(shù)值實(shí)驗(yàn)表明在小規(guī)模實(shí)例中，基于記錄更新的啟發(fā)式方法具有優(yōu)勢。但是，對于中等規(guī)模的實(shí)例，最好的選擇是基于可變鄰域局部搜索的啟發(fā)式算法，它可以在10s內(nèi)解決40個客戶和5d的實(shí)例。呂文雅[38]開發(fā)了一個集成了記錄更新算法、變鄰域深度搜索算法和禁忌搜索算法的Web端系統(tǒng)，以便于使用相關(guān)算法對車輛路徑進(jìn)行優(yōu)化。Lespay等[34]提出了一個兩階段啟發(fā)式方法來最小化ConVRPTW的路線數(shù)量：第一步，基于插入啟發(fā)法構(gòu)造一個可行的初始解；第二步，通過啟發(fā)式方法減少第一步中獲得的解決方案中的路線數(shù)量；最后，根據(jù)總行駛距離重新優(yōu)化第二步的結(jié)果從而獲得最終解決方案。

3.2 精確式算法求解ConVRP

通過對以上文獻(xiàn)中解決ConVRP問題的方法歸納可以發(fā)現(xiàn)，幾乎所有的大規(guī)模ConVRP都需要利用啟發(fā)式方法來求解，但是也有部分學(xué)者利用精確式算法求解該問題。

綜上，求解ConVRP的算法匯總于表2。

表2 一致性車輛路徑問題求解算法匯總

4 總結(jié)與展望

VRP作為物流與交通運(yùn)輸領(lǐng)域的經(jīng)典問題，其求解方法已經(jīng)逐漸趨于成熟，研究成果也較為豐富。但隨著應(yīng)用場景的不斷豐富，新的需求及約束也不斷被提出，VRP變種也層出不窮。在眾多VRP變種中，ConVRP是相對較新的VRP變種，相關(guān)成果具有重要的實(shí)踐和學(xué)術(shù)價值。本文從VRP分類、ConVRP背景介紹、ConVRP模型、ConVRP求解算法等方面對該問題進(jìn)行了綜述。

ConVRP的出現(xiàn)源于物流公司對客戶服務(wù)水平的關(guān)注，在有固定需求的物流配送服務(wù)中，穩(wěn)定一致的服務(wù)時間及服務(wù)人員有助于公司維護(hù)良好的客戶關(guān)系，提升客戶滿意度，從而產(chǎn)生額外的經(jīng)濟(jì)效益。實(shí)踐表明，對于物流公司而言，保持一致性的服務(wù)水平比節(jié)省1%～3%的成本更為重要。尤其是快遞公司，其運(yùn)營的核心在于為客戶提供標(biāo)準(zhǔn)的、一致性的服務(wù)。同時，司機(jī)對于一致性的線路安排也更為熟悉，有利于公司提升運(yùn)力管理效率，降低運(yùn)營成本。除了在物流配送領(lǐng)域有用武之地外，ConVRP在家庭護(hù)理、供應(yīng)商庫存管理中亦有廣泛的應(yīng)用場景，具有重要的實(shí)踐價值。

從ConVRP的模型來看，除了一致性約束外，模型的主要約束與經(jīng)典VRP基本一致。現(xiàn)有的研究成果中，大多數(shù)ConVRP應(yīng)用場景及模型同時考慮了TC和DC要求，在物流配送中尤其常見。少部分應(yīng)用場景及模型僅考慮TC或DC要求，例如殘疾人交通問題中僅需要考慮TC要求、家庭護(hù)理問題中則更側(cè)重考慮DC要求。對于RC要求的研究相對較少，目前有兩種處理方法：一種是根據(jù)司機(jī)對區(qū)域的熟悉程度設(shè)計路線，司機(jī)訪問某區(qū)域線路的次數(shù)越多，單次訪問成本就越低，通過最小化司機(jī)對配送區(qū)域的訪問成本實(shí)現(xiàn)RC；另一種是通過計算不一致路段占總路段的比例量化路線一致性水平。此外，在目標(biāo)函數(shù)的設(shè)計中，大多數(shù)文獻(xiàn)采用單目標(biāo)建模方法，目標(biāo)多為考慮最小化總成本(行駛時間/行駛距離)或司機(jī)數(shù)量等；少部分文獻(xiàn)采用多目標(biāo)的建模方法，例如在考慮RC要求時增加最小化司機(jī)對配送區(qū)域訪問成本的目標(biāo)來實(shí)現(xiàn)RC，同時多目標(biāo)模型能夠在沖突的目標(biāo)函數(shù)之間進(jìn)行更徹底的權(quán)衡分析，有助于檢驗(yàn)不同維度的一致性要求之間的關(guān)系。

從求解方法來看，絕大多數(shù)ConVRP都是通過啟發(fā)式算法解決的，尤其是在時間周期達(dá)到或超過5 d、客戶數(shù)量超過50的大規(guī)模算例中。常用的求解算法有基于模板路徑的禁忌搜索算法、鄰域搜索算法、模擬退火算法、蟻群算法等，其中Lespay等[34]利用多階段啟發(fā)式算法求解了時間周期為19～27 d、客戶數(shù)量達(dá)1 600以上的超大規(guī)模算例。極少數(shù)的中小規(guī)模算例可以通過精確式算法求解，值得關(guān)注的是，Wang等[22]通過列切割與生成技術(shù)實(shí)現(xiàn)了利用精確式算法求解客戶數(shù)達(dá)50的中型算例，進(jìn)一步提升了精確式算法在求解ConVRP中的算例規(guī)模。

展望未來，對于有TC要求的ConVRP，可以考慮更多隨機(jī)因素的影響，保證在不可預(yù)見的場景下訪問客戶時間的穩(wěn)定性，例如考慮交通事故、交通管制、司機(jī)在客戶處等待時間的不確定場景等；對于有DC要求的ConVRP，在考慮服務(wù)人員一致性的同時可以進(jìn)一步考慮人員之間工作量的平衡；對于有RC要求的ConVRP，在量化RC水平的同時，可以進(jìn)一步研究RC與TC和DC的關(guān)系，通過提升RC水平來優(yōu)化TC和DC效果。在求解方法上，可以針對同時包含TC、DC和RC約束的ConVRP定制化設(shè)計啟發(fā)式方法實(shí)現(xiàn)對大規(guī)模算例的求解，進(jìn)一步豐富ConVRP的求解方法。

[1] DANTZIG G B, RAMSER J H. The truck dispatching problem[J]. Management Science, 1959, 6(1): 80-91.

[2] KONSTANTAKOPOULOS G D, GAYIALIS S P, KECHAGIAS E P. Vehicle routing problem and related algorithms for logistics distribution: a literature review and classification[J]. Operational Research, 2020: 1-30.

[3] CHOI E, TCHA D. A column generation approach to the heterogeneous fleet vehicle routing problem[J]. Computers & Operations Research, 2007, 34(7): 2080- 2095.

[4] LIN S, YU V F, CHOU S. A note on the truck and trailer routing problem[J]. Expert Systems with Applications, 2010, 37(1): 899-903.

[5] IORI M, SALAZAR-GONZALEZ J, VIGO D. An exact approach for the vehicle routing problem with two- dimensional loading constraints[J]. Transportation Science, 2007, 41(2): 253-264.

[6] GENDREAU M, IORI M, LAPORTE G, et al. A tabu Search algorithm for a routing and container loading problem[J]. Transportation Science, 2006, 40(3): 342-350.

[7] MONTANE F A T, GALVAO R D. A tabu search algorithmfor the vehicle routing problem with simultaneous pick-upand delivery service[J]. Computers & Operations Research, 2006, 33(3): 595-619.

[8] OLIVEIRA H B, VASCONCELOS G C. A hybrid search method for the vehicle routing problem with time windows[J]. Annals of Operations Research, 2010, 180(1): 125-144.

[9] FIGLIOZZI M A. An iterative route construction and improvement algorithm for the vehicle routing problem with soft time windows[J]. Transportation Research Part C: Emerging Technologies, 2010, 18(5): 668-679.

[10] GULCZYNSKI D, GOLDEN B, WASIL E. The period vehicle routing problem: new heuristics and real-world variants[J]. Transportation Research Part E: Logistics and Transportation Review, 2011, 47(5): 648-668.

[11] BELTRAMI E J, BODIN L D. Networks and vehicle routing for municipal waste collection[J]. Networks, 1974, 4(1): 65-94.

[12] 姜貴山, 姬長虹. 周期性車輛路徑問題在物流中的應(yīng)用: 案例研究[J]. 科學(xué)技術(shù)與工程, 2010, 10(11): 2694-2697.

[13] 龐燕, 羅華麗, 邢立寧, 等. 車輛路徑優(yōu)化問題及求解方法研究綜述[J]. 控制理論與應(yīng)用, 2019, 36(10): 1573-1584.

[14] GRO?R C, GOLDEN B, WASIL E. The consistent vehicle routing problem[J]. Manufacturing & Service Operations Management, 2009, 11(4): 630-643.

[15] 黃琳. 考慮路徑一致性和工作量平衡的車輛路徑優(yōu)化問題[D]. 上海: 上海大學(xué), 2019.

[16] COELHO L C, CORDEAU J, LAPORTE G. Consistency in multi-vehicle inventory-routing[J]. Transportation Research Part C: Emerging Technologies, 2012, 24: 270-287.

[17] SMILOWITZ K, NOWAK M, JIANG T. Workforce management in periodic delivery operations[J]. Transportation Science, 2013, 47(2): 214-230.

[18] RICHARD T W. Vehicle routing for small package delivery and pickup services[M]// BRUCE G S R, EDWARD W. The vehicle routing problem: lastest advances and new challenges. New York: Springer, 2008: 475-485.

[19] HOLLAND C, LEVIS J, NUGGEHALLI R, et al. UPS optimizes delivery routes[J]. Interfaces(Providence), 2017, 47(1): 8-23.

[20] KOVACS A A, GOLDEN B L, HARTL R F, et al. Vehicle routing problems in which consistency considerations are important: A Survey[J]. Networks, 2014, 64(3): 192-213.

[21] BORSANI V, MATTA A, BESCHI G, et al. A home care scheduling model for human resources[C]// 2006 International Conference on Service Systems and Service Management. Troyes: IEEE 2006: 449-454.

[22] WANG K, LU Z, XIA J, et al. Routing optimization with generalized consistency requirements[Z]. Article Submitted to Transportation Science, 2021.

[23] TARANTILIS C D, STAVROPOULOU F, REPOUSSIS P P. A template-based tabu search algorithm for the consistent vehicle routing problem[J]. Expert Systems with Applications, 2012, 39(4): 4233-4239.

[24] KOVACS A A, PARRAGH S N, HARTL R F, et al. A template-based adaptive large neighborhood search for the consistent vehicle routing problem[J]. Networks, 2014, 63(1): 60-81.

[25] XU Z, CAI Y. Variable neighborhood search for consistent vehicle routing problem[J]. Expert Systems with Applications, 2018, 113: 66-76.

[26] CAMPELO P, NEVES-MOREIRA F, AMORIM P, et al. Consistent vehicle routing problem with service level agreements: a case study in the pharmaceutical distribution sector[J]. European Journal of Operational Research, 2019, 273(1): 131-145.

[27] GOEKE D, ROBERTI R, SCHNEIDER M. Exact and heuristic solution of the consistent vehicle-routing Problem[J]. Transportation Science, 2019, 53(4): 1023- 1042.

[28] STAVROPOULOU F, REPOUSSIS P P, TARANTILIS C D. The vehicle routing problem with profits and consistency constraints[J]. European Journal of Operational Research, 2019, 274(1): 340-356.

[29] ZHEN L, LV W, WANG K, et al. Consistent vehicle routing problem with simultaneous distribution and collection[J]. The Journal of the Operational Research Society, 2020, 71(5): 813-830.

[30] KOVACS A A, GOLDEN B L, HARTL R F, et al. The generalized consistent vehicle routing problem[J]. Transportation Science, 2015, 49(4): 796-816.

[31] KOVACS A A, PARRAGH S N, HARTL R F. The multi-objective generalized consistent vehicle routing problem[J]. European Journal of Operational Research, 2015, 247(2): 441-458.

[32] LIAN K, MILBURN A B, RARDIN R L. An improved multi-directional local search algorithm for the multi- objective consistent vehicle routing problem[J]. IIE Transactions, 2016, 48(10): 975-992.

[33] FEILLET D, GARAIX T, LEHUéDé F, et al. A new consistent vehicle routing problem for the transportation of people with disabilities[J]. Networks, 2014, 63(3): 211-224.

[34] LESPAY H, SUCHAN K. A case study of consistent vehicle routing problem with time windows[J]. International Transactions in Operational Research, 2021, 28(3): 1135-1163.

[35] 劉恒宇, 汝宜紅. 考慮交通擁堵及工作量平衡性的一致性車輛路徑問題[J]. 西南交通大學(xué)學(xué)報, 2016, 51(5): 931-937.

[36] 劉恒宇, 汝宜紅. 一致性車輛路徑問題下基于模板路徑的模擬退火法[J]. 交通運(yùn)輸系統(tǒng)工程與信息, 2015, 15(6): 177-183.

[37] 卞晨. 基于蟻群算法的一致性車輛路徑問題的研究[D]. 淮南: 安徽理工大學(xué), 2017.

[38] 呂文雅. 集配一體化一致性車輛路徑問題研究[D]. 上海: 上海大學(xué), 2020.

[39] COELHO L C, LAPORTE G. A branch-and-cut algorithm for the multi-product multi-vehicle inventory-routing problem[J]. International Journal of Production Research, 2013, 51(23-24): 7156-7169.

[40] SUBRAMANYAM A, GOUNARIS C E. A branch-and- cut framework for the consistent traveling salesman problem[J]. European Journal of Operational Research, 2016, 248(2): 384-395.

A Survey of the Consistent Vehicle Routing Problem

LI Lu-yao, SHEN Yi-fan, XIA Jun, SHEN Hai-hui

(Sino-US Global Logistics Institute, Shanghai Jiao Tong University, Shanghai 200030, China)

The vehicle routing problem (VRP) is a major research topic in the field of logistics and transportation. In recent years, to cope with the fierce market competition, increasingly more enterprises have begun to focus on how to reduce costs while ensuring service efficiency and service quality. Practice shows that improving the consistency of vehicle routing solutions can not only improve service efficiency but also significantly enhance customer satisfaction. Therefore, the VRP considering consistency constraints (also known as the consistent VRP (ConVRP)) has emerged. The ConVRP is a relatively new variant of the VRP, and the related research results have important practical and academic value. With the consideration of diverse consistency constraints and the development of related mathematical models and solution methods, a considerable amount of research has been accumulated on the ConVRP. This study summarizes the classification, background, models and algorithms of the ConVRP. Consistent constraints mainly include time consistency, driver consistency, and route consistency. Time consistency and driver consistency constraints are common, whereas route consistency constraints are more novel. ConVRP methods are usually based on heuristic algorithms, especially for large and medium-sized instances (with time periods of 5 days and >50 customers). For small and medium-sized instances (with time periods of 3～5 days and <50 customers), some exact algorithms also exhibit good performance.

logistics engineering;consistent vehicle routing problem; time consistency; driver consistency; route consistency; literature review

U116.2

A

10.19961/j.cnki.1672-4747.2021.07.036

1672-4747(2021)04-0062-13

2021-07-27

2021-08-08

2021-08-11

2021-07-27～07-30； 08-07～08-08

“科技助力經(jīng)濟(jì)2020”重點(diǎn)專項(xiàng)；國家自然科學(xué)基金項(xiàng)目(72031006)；上海交通大學(xué)科技創(chuàng)新專項(xiàng)(17JCYA04)

李路遙(1998—)，男，河北邢臺人，碩士研究生，研究方向?yàn)槲锪鲀?yōu)化，E-mail：liluyao20@sjtu.edu.cn

夏俊(1987—)，男，浙江杭州人，博士，助理研究員，研究方向?yàn)槲锪鲀?yōu)化，E-mail：lgtxiaj@sjtu.edu.cn

李路遙，沈一帆，夏俊，等. 考慮一致性約束的車輛路徑問題綜述[J]. 交通運(yùn)輸工程與信息學(xué)報，2021, 19(4): 62-74.

LI Lu-yao, SHEN Yi-fan, XIA Jun, et al. A Survey of the Consistent Vehicle Routing Problem[J]. Journal of Transportation Engineering and Information, 2021, 19(4): 62-74.

(責(zé)任編輯：李愈)