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

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

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

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

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

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

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

0 引 言

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

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

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

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

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

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

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

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

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

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

1.1 ConVRP應用場景

ConVRP在實際中有很多應用場景，主要有以下幾類：

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

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

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

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

1.2 一致性需求的分類

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

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

2.1 同時考慮TC和DC的ConVRP

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

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

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

2.2 考慮TC或DC的ConVRP

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

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

2.3 考慮RC的ConVRP

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

2.4 考慮其他條件的ConVRP

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

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

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

續(xù)表1

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

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

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

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

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

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

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

3.2 精確式算法求解ConVRP

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

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

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

4 總結與展望

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

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

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

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

展望未來，對于有TC要求的ConVRP，可以考慮更多隨機因素的影響，保證在不可預見的場景下訪問客戶時間的穩(wěn)定性，例如考慮交通事故、交通管制、司機在客戶處等待時間的不確定場景等；對于有DC要求的ConVRP，在考慮服務人員一致性的同時可以進一步考慮人員之間工作量的平衡；對于有RC要求的ConVRP，在量化RC水平的同時，可以進一步研究RC與TC和DC的關系，通過提升RC水平來優(yōu)化TC和DC效果。在求解方法上，可以針對同時包含TC、DC和RC約束的ConVRP定制化設計啟發(fā)式方法實現對大規(guī)模算例的求解，進一步豐富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] 姜貴山, 姬長虹. 周期性車輛路徑問題在物流中的應用: 案例研究[J]. 科學技術與工程, 2010, 10(11): 2694-2697.

[13] 龐燕, 羅華麗, 邢立寧, 等. 車輛路徑優(yōu)化問題及求解方法研究綜述[J]. 控制理論與應用, 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]. 上海: 上海大學, 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]. 西南交通大學學報, 2016, 51(5): 931-937.

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

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

[38] 呂文雅. 集配一體化一致性車輛路徑問題研究[D]. 上海: 上海大學, 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

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

李路遙(1998—)，男，河北邢臺人，碩士研究生，研究方向為物流優(yōu)化，E-mail：liluyao20@sjtu.edu.cn

夏俊(1987—)，男，浙江杭州人，博士，助理研究員，研究方向為物流優(yōu)化，E-mail：lgtxiaj@sjtu.edu.cn

李路遙，沈一帆，夏俊，等. 考慮一致性約束的車輛路徑問題綜述[J]. 交通運輸工程與信息學報，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.

(責任編輯：李愈)