摘 要：針對一類考慮客戶分類、隨機旅行時間、隨機服務(wù)時間及時間窗約束的車輛路徑問題構(gòu)建了機會約束規(guī)劃模型，該模型考慮兩類客戶（普通客戶與優(yōu)質(zhì)客戶），并通過添加機會約束條件確保優(yōu)質(zhì)客戶獲得準時服務(wù)的概率。同時，設(shè)計了變鄰域迭代局部搜索算法，并給出了一種基于最小等待時間的初始解生成啟發(fā)式規(guī)則?；赟olomon算例進行了多組仿真實驗。仿真實驗結(jié)果表明，所設(shè)計生成初始解的啟發(fā)式規(guī)則是有效的；所給算法能夠在短時間內(nèi)找到確定問題和隨機問題的近似最優(yōu)解；客戶比與車輛使用數(shù)目呈正相關(guān)關(guān)系。研究結(jié)果對解決資源有限條件下克服隨機不確定性因素帶來的不利影響、保證客戶服務(wù)水平等問題有一定的參考意義。

關(guān)鍵詞：車輛路徑； 客戶分類； 隨機旅行及服務(wù)時間； 機會約束； 變鄰域迭代局部搜索

中圖分類號：TP301.6 文獻標(biāo)志碼：A

文章編號：1001-3695（2022）07-009-1979-06

doi：10.19734/j.issn.1001-3695.2021.12.0673

基金項目：國家自然科學(xué)基金資助項目（61673228，62072260）；青島市科技計劃資助項目（21-1-2-16-zhz）

作者簡介：馬俊（1995-），男，安徽宿州人，碩士，主要研究方向為車輛路徑優(yōu)化；張紀會（1969-），男（通信作者），山東濰坊人，教授，博導(dǎo)，博士，主要研究方向為智能優(yōu)化理論與方法、系統(tǒng)工程（zhangjihui@qdu.edu.cn）；郭乙運（1979-），男，山東日照人，高級工程師，碩士，主要研究方向為現(xiàn)代物流與供應(yīng)鏈管理.

Optimization model and algorithm for vehicle routing problem with

stochastic time and customer classification

Ma Jun^1a，1b， Zhang Jihui^1a，1b?， Guo Yiyun²

（1.a.Institute of Complexity Science， b.Shandong Key Laboratory of Industrial Control Technology， Qingdao University， Qingdao Shandong 266071， China; 2.Qingdao Port International Co.， Ltd.， Qingdao Shandong 266011， China）

Abstract：For the vehicle routing problem with time window， stochastic travel and service time， and customer classification， this paper constructed a chance constrained programming model， which considered two class customers （ordinary customers and priority customers） and adopted the chance constraint to guarantee the punctual service possibility of priority customers. Meanwhile， this paper designed a variable neighborhood iterated local search algorithm to solve the model， and proposed a minimum waiting time heuristic rule to generate initial solution. Based on Solomon benchmarks， it conducted series of simulation experiments. The results show that the initial solution generation method is valid， the given algorithm can get approximate optimal solutions for both of the deterministic and stochastic problems in a short time， and the customer ratio is positively relative to the number of vehicle usage. The results have a certain reference significance to solve the problem of low customer ser-vice level caused by the limited resources and uncertain factors.

Key words：vehicle routing; customer classification; stochastic travel and service time; chance constrained; variable neighborhood iterated local search

0 引言

隨著生活水平的普遍提高以及電商物流行業(yè)的快速發(fā)展，使得客戶對物流配送服務(wù)的時效性和準時性要求愈發(fā)嚴格，如何在有限的服務(wù)資源下給出經(jīng)濟可行且滿足客戶要求的配送路徑已成為眾多企業(yè)面臨的難題?？蛻舴诸愂瞧髽I(yè)應(yīng)對上述問題的主要措施之一，其利用有限的資源確保優(yōu)質(zhì)客戶的服務(wù)水平，以實現(xiàn)提高企業(yè)收益、維持客戶忠誠度等目的。在大數(shù)據(jù)技術(shù)廣泛使用的背景下，決策人員能夠大量獲得與客戶相關(guān)的信息，已知客戶相關(guān)信息的前提下，對客戶分類的方法有很多，如文獻［1］的DBSCAN方法。本文不涉及客戶分類方法，重點研究已知客戶分類，考慮隨機旅行時間、隨機服務(wù)時間及時間窗約束的車輛路徑問題（vehicle routing problem with time window，stochastic travel and service time，and customer classification，VRPTWSTSCC），旨在給出經(jīng)濟可行的配送方案，揭示客戶分類對企業(yè)運營成本及客戶服務(wù)水平的影響。該問題有著廣泛的應(yīng)用背景，如美團、餓了么等平臺提供的“準時達”配送服務(wù)，對購買“準時達”服務(wù)的顧客，若騎手的實際到達時刻晚于預(yù)計到達時刻，則平臺依據(jù)遲到程度給予不同金額的補償。這里預(yù)計到達時刻是一個期望值，而實際到達時刻受到諸如天氣狀況、路段車流量等因素的影響，其本身是一個不確定的變量。

VRP（車輛路徑問題）是由Dantzig等人^［2］提出的一類經(jīng)典的組合優(yōu)化問題，其基本提法是：對一個擁有若干車輛的車場而言，存在已知數(shù)量需要服務(wù)的顧客，決策者在滿足某些約束條件下，規(guī)劃若干條從車場出發(fā)并完成所有顧客服務(wù)需求的路線，以實現(xiàn)最小化配送成本或最大化顧客服務(wù)水平等目的。有關(guān)VRP的最新研究綜述參見文獻［3］。傳統(tǒng)VRP一般假設(shè)所涉及的參數(shù)信息是確定的，這一假設(shè)忽略了VRP固有的不確定性，使得傳統(tǒng)VRP的某些研究成果無法滿足實際需求。隨機變量是描述參數(shù)不確定性的一種常見方法，近年來越來越多的學(xué)者關(guān)注隨機VRP。隨機因素可分為隨機時間、隨機需求、隨機客戶請求等，有關(guān)隨機VRP的研究綜述參見文獻［4～6］。

隨機VRP常見的建模方法有機會約束規(guī)劃（chance constrained programming，CCP）和帶修正策略的隨機規(guī)劃（stochastic programming with recourse，SPR）兩種。CCP是包含一個或多個約束條件，需滿足一定置信水平的最優(yōu)化問題，求解該問題的難點在于機會約束檢查。對VRPTWSTS中的到達時刻機會約束有離散化方法和隨機試驗方法兩種常見的檢查方法。離散化方法采用離散變量近似表示連續(xù)變量（如旅行時間及服務(wù)時間），計算待檢查變量（如到達時刻）的離散分布函數(shù)，并進行機會約束檢查?；陔x散化方法，文獻［7，8］研究了單目標(biāo)VRPTWSTS，文獻［9］研究了多目標(biāo)VRPTWSTS。Li等人^［10］運用隨機試驗方法檢查給定路徑是否滿足車輛到達時刻及司機工作時長機會約束。此外，也有學(xué)者采用正態(tài)分布、對數(shù)正態(tài)分布等近似表示到達時刻分布函數(shù)，如文獻［11，12］。CCP模型中的最優(yōu)路徑是在一定置信水平下求得的，實際運行過程中存在“失敗”的可能性。“失敗”是指車輛沿先驗路徑行駛過程中，由于隨機因素的存在使得車輛無法按照顧客要求提供服務(wù)^［13］。對VRPTWSTS，SPR分兩個階段進行求解：a）依據(jù)先驗知識，確定先驗路徑；b）運用給定的修正策略對車輛實際運行中發(fā)生“失敗”的先驗路徑給予修正。VRPTWSTS常見的修正策略有TWVC（time window violation cost）和跳過策略兩種。TWVC策略中客戶接受車輛提供的延遲服務(wù)，但需根據(jù)延遲程度施加一定的懲罰成本^［10］；跳過策略是指當(dāng)車輛到達某一客戶的時刻晚于要求的右時間窗時，為保證對后續(xù)客戶的準時服務(wù)，車輛跳過對當(dāng)前客戶的服務(wù)^［14］。

考慮客戶分類的VRP常見于服務(wù)行業(yè)，于江霞等人^［1］研究了考慮客戶分類的即時配送路徑優(yōu)化問題，從客戶消費行為角度將其分為三類，對三類違反時間窗約束的客戶施加不同程度的懲罰成本以體現(xiàn)企業(yè)對不同客戶的重視程度。針對帶有隨機旅行時間、隨機服務(wù)時間、多車場及客戶分類的現(xiàn)場服務(wù)路徑問題（field service routing problem），Binart等人^［15］將客戶分為強制客戶（mandatory customers）及可選客戶（optional customers），并給出了一種兩階段方法。其中，強制客戶的服務(wù)必須在時間窗內(nèi)進行，可選客戶在計劃周期內(nèi)的服務(wù)與否不作要求。張力婭等人^［16］研究了考慮顧客優(yōu)先級的多目標(biāo)外賣即時配送路徑優(yōu)化問題，優(yōu)先級取決于客戶是否購買“準時達”服務(wù)。陳夢玲^［17］研究了考慮服務(wù)優(yōu)先級的共享汽車維護路徑規(guī)劃問題，依據(jù)任務(wù)緊急程度確定服務(wù)優(yōu)先級別。除文獻［15］外，其余研究均忽略了VRP固有的不確定性，存在一定的局限性。

本文進一步研究了VRPTWSTSCC，該問題是對隨機時間VRP和考慮客戶分類VRP的進一步拓展。相關(guān)研究結(jié)果對企業(yè)解決有限資源限制和復(fù)雜道路環(huán)境帶來的客戶服務(wù)水平低、運營成本高等問題有一定的參考意義。主要貢獻如下：a）構(gòu)建了刻畫VRPTWSTSCC的CCP模型，該模型同時考慮客戶分類和機會約束條件；b）設(shè)計了變鄰域迭代局部搜索算法（vari-able neighborhood iterated local search，VNILS），并分別給出了用于求解確定問題、隨機問題的初始解生成方法，仿真實驗結(jié)果表明，VNILS可有效快速地求解VRPTW和VRPTWSTSCC，能夠滿足實際應(yīng)用需求。針對VRPTW，基于最小等待時間啟發(fā)式規(guī)則（minimum waiting time heuristic，MWTH）的初始解生成方法具備優(yōu)越性、可推廣性；針對VRPTWSTSCC，采用增加旅行時間和服務(wù)時間后VRPTW的近似最優(yōu)解作為初始解，該方法能夠有效提高隨機問題初始解的可行性，同時大幅降低算法運行時間，為決策人員在不確定環(huán)境下制定配送路徑提供參考。最后研究了客戶比對實驗結(jié)果的影響，結(jié)果表明：客戶分類有助于降低企業(yè)運營成本；客戶比與車輛使用數(shù)呈正相關(guān)關(guān)系。

1 機會約束規(guī)劃模型

用于構(gòu)建VRPTWSTSCC數(shù)學(xué)模型的相關(guān)變量符號及含義如表1所示。其中，旅行時間和服務(wù)時間均為服從某一分布的隨機變量，車場處可用的車輛數(shù)遠大于實際需求。本文采用硬時間窗約束，即車輛在客戶i的開始服務(wù)時刻必須位于對應(yīng)的時間間隔內(nèi)，若車輛到達時刻早于左時間窗ei，則需等待至ei才能開始服務(wù)；若車輛到達時刻晚于右時間窗l(fā)i，則客戶不接受服務(wù)。

CCP是一種研究隨機決策系統(tǒng)的數(shù)學(xué)工具，特點在于存在一個或多個概率約束條件，一般形式如下：

其中：f（x）為目標(biāo)函數(shù);x為決策變量;X為約束條件集合;α為置信水平。在VRPTWSTSCC中僅考慮車輛到達時刻機會約束，表示為

βi可以理解為客戶i所需的服務(wù)水平，服務(wù)水平體現(xiàn)了問題的求解難度（若服務(wù)水平取值較高如95%，則難以在短時間內(nèi)找到滿足約束條件的可行解）。為進一步降低模型求解難度，可將式（3）替換為一個較弱的機會約束條件，即只需保證車輛到達客戶i的時刻早于右時間窗l(fā)i的概率不小于βi。該簡化處理方法能夠在保證問題特征不變的前提下提高算法找到可行解的概率。本文進一步將客戶分為優(yōu)質(zhì)客戶及普通客戶兩類，服務(wù)優(yōu)質(zhì)客戶的車輛到達時刻滿足機會約束條件，服務(wù)普通客戶的車輛到達時刻機會約束條件的滿足與否不作要求。記優(yōu)質(zhì)客戶集合為V01，同時假設(shè)所有優(yōu)質(zhì)客戶所需的服務(wù)水平均為β，上述機會約束條件可進一步表示為P{ATi～≤li}≥β，i∈V01。結(jié)合VRPTW模型的約束條件，VRPTWSTSCC的CCP模型如下所示：

式（4）為目標(biāo)函數(shù)，表示最小化總成本，包括車輛使用成本（主目標(biāo)）和期望運行成本（次目標(biāo)），其中車輛單位時間運行成本為1，m0=∑j∈V0∑k∈Kx0jk；式（5）表示任一客戶僅由一輛車服務(wù)；式（6）（7）表示車輛由車場發(fā)出并最終返回車場；式（8）表示車輛在任一客戶處的入度與出度相同；式（9）為車輛固定載重約束；式（10）為子回路消除約束，其中S為V的真子集；式（11）為車輛在優(yōu)質(zhì)客戶處的到達時刻機會約束。

2 迭代局部搜索算法

迭代局部搜索（iterated local search，ILS）是一種基于鄰域的元啟發(fā)式算法，運用鄰域算子進行局部搜索，并通過擾動算子避免算法陷入局部最優(yōu)。ILS憑借較好的尋優(yōu)能力及較高的運算速度常用于求解大規(guī)模組合優(yōu)化問題。該算法由初始解、鄰域算子、擾動算子及解的接受準則構(gòu)成，基本尋優(yōu)過程為：給定初始解s0，從s0出發(fā)執(zhí)行局部搜索，得到局部最優(yōu)解s*；對s*施加擾動，得到擾動解s′；同時從s′出發(fā)再次執(zhí)行局部搜索得到局部最優(yōu)解s^*′；根據(jù)解的接受準則，選擇s*或s^*′進入下次循環(huán)。重復(fù)該過程，直至滿足算法停止準則。變鄰域搜索有助于擴大解空間，提升求解質(zhì)量^［18］。在ILS的基礎(chǔ)上給出VNILS，具體步驟如下：

a）產(chǎn)生初始解。針對VRPTW，給出了基于最小等待時間的初始解生成啟發(fā)式規(guī)則。對待分配配送車輛的客戶，按照某種規(guī)則選取客戶插入當(dāng)前配送路徑中（插入操作必須滿足載重和時間窗約束），直到當(dāng)前路徑配送需求大于車輛載重約束，此時增加車輛數(shù)量。重復(fù)該過程，直至所有客戶均完成插入操作，常見的插入規(guī)則包括最小行駛成本、最大旅行距離等。然而，上述插入規(guī)則均單純考慮旅行距離，忽略了問題最重要的特征時間窗。采用上述兩種規(guī)則會使得初始解中的車輛數(shù)較多，原因在于：如果車輛在某一客戶處的等待時間較長，那么其所能服務(wù)的客戶數(shù)量就相對較少。等待時間由客戶間旅行距離和時間窗決定，更能體現(xiàn)問題特征。基于此，本文采用最小等待時間作為選擇客戶插入當(dāng)前路徑的規(guī)則，計算公式如下：

其中：UC為待分配客戶構(gòu)成的集合。針對VRPTWSTSCC，采用增加旅行及服務(wù)時間（分別乘以λ，λgt;1）后VRPTW的近似最優(yōu)解作為隨機問題的初始解，目的在于提高隨機問題初始解的可行性和減少算法運行時間。

b）鄰域算子。共采用四種鄰域搜索算子，分別為swap、2-opt、2-opt*和破壞/修復(fù)算子。各算子具體操作說明如下：（a）swap算子，隨機交換兩條路徑上的兩個客戶；（b）2-opt算子，對一條路徑，隨機選取兩個節(jié)點并逆序節(jié)點間的客戶順序；（c）2-opt*算子，作用在兩條路徑上，對每條路徑均隨機選取一個節(jié)點，按圖1的操作過程進行解的搜索；（d）破壞/修復(fù)算子，通過移除與插入操作提高解的質(zhì)量，具體步驟參見文獻［19，20］。基本思想為：依據(jù)客戶間的相關(guān)性選擇待移除的客戶；對每一個待插入的客戶，插入操作會引起路徑成本增加，選擇最小增加成本對應(yīng)的位置作為客戶的插入位置。對VRPTWSTSCC的求解進行如下調(diào)整：對包含m0條路徑的解s，通過離散化方法找到并移除當(dāng)前解s中所有不滿足到達時刻機會約束的客戶，記該類客戶構(gòu)成的集合為O。對每一個將要被插入的客戶cus∈O，依次從第1～m0條路徑尋找滿足約束條件的插入位置，將滿足約束條件的插入位置稱為可能位置。插入客戶cus將增加路徑成本，選擇最小增加成本對應(yīng)的可能位置作為客戶cus的插入位置。然后更新當(dāng)前解s和集合O。重復(fù)該過程，直至集合O為空集或者集合O中的客戶均不存在可能位置。若集合O不為空集，將集合O中的客戶按照左時間窗大小升序排列，同時將產(chǎn)生的新路徑并入當(dāng)前解s中，完成插入操作過程。

變鄰域搜索的偽代碼如算法1所示。其中，localsearch（s，Ni）表示采用鄰域搜索算子i對解s進行局部搜索。這里不再給出局部搜索算法的偽代碼，但需要強調(diào)的是：局部搜索是在一條或兩條路徑間進行，故在進行解的優(yōu)劣判斷時，只需計算搜索過程中涉及到的路徑成本即可，如此可避免部分相同路徑重復(fù)計算情形的發(fā)生，加速搜索過程。

算法1 變鄰域搜索

begin

定義鄰域結(jié)構(gòu)Ni={swap，2-opt，2-opt*，破壞/修復(fù)}；

給定解s；

repeat

i1， tag1；

while i≤imax（imax為鄰域搜索算子個數(shù)）

s*=localsearch（s，Ni）；

if f（s*）lt;f（s）

tagture；

ss*；

end if

ii+1；

end while

until tag1

return s

end

c）擾動算子。擾動強度在很大程度上決定了擾動效果，若擾動強度過大，則算法退化為隨機多起點算法；若擾動強度過小，則算法無法逃離局部最優(yōu)解。參考文獻［21］，采用cross-change擾動算子，操作流程如圖2所示，詳細步驟如下：隨機選擇兩條路徑，并隨機生成每條路徑上的第1個節(jié)點，第2個節(jié)點的選擇取決于節(jié)點間（截斷部分）的客戶數(shù)量。其中，節(jié)點間的客戶數(shù)量服從U［2，4］。若第2個節(jié)點的位置大于當(dāng)前路徑長度，則截斷部分為第1個節(jié)點至該路徑上的最后一個顧客。按圖2的交換規(guī)則，完成對當(dāng)前路徑的擾動。

d）解的接受準則。對每一個局部最優(yōu)解s均施加一個擾動，記擾動解為s′；從解s′出發(fā)，再次執(zhí)行局部搜索，得到局部最優(yōu)解為s^*′。若f（s^′）lt;f（s*），記當(dāng)前最優(yōu)解為s^*′；否則，記當(dāng)前最優(yōu)解為s。針對VRPTW和VRPTWSTSCC，f（s）的表達形式分別如式（13）（14）所示。

其中：γ（k）=ε×∑nki=1{ATi－li，0}表示車輛在路徑k上違反時間窗約束的懲罰成本;ε為懲罰系數(shù);nk為路徑k上的顧客數(shù)量；φ（k）=ω×max{∑nki=1qi－Q，0}表示車輛在路徑k上違反載重約束的懲罰成本;ω為懲罰系數(shù)；ξ同樣為懲罰系數(shù);DP（k）為布爾型變量，取值為1，表示路徑k為不可行路徑，取值為0，表示路徑k為可行路徑。

3 路徑可行性判斷

針對CCP模型中的到達時刻機會約束條件，下面給出用于機會約束檢查的離散化方法和路徑可行性定義。假設(shè)車輛在客戶i和j間的旅行時間為服從正態(tài)分布的隨機變量，表示為TT～ij～N（uij，σ²ij）；車輛在客戶i的服務(wù)時間同樣為服從正態(tài)分布的隨機變量，表示為ST～i～N（ui，σ²i）。這里，同樣假設(shè)隨機變量之間相互獨立。由于硬時間窗約束的存在，使得車輛在客戶j處的到達時刻為左截斷變量，記為AT～^trj，函數(shù)表達形式如下：

其中：t為截斷點。同時，令Y～j為車輛在客戶j和j+1間旅行時間及在客戶j處服務(wù)時間之和，故Y～j同樣為服從正態(tài)分布的隨機變量，記Y～j～N（uj（j+1）+uj，σ²j（j+1）+σ²j）。車輛在客戶j+1處的到達時刻為AT～^trj+1=AT～^trj+Y～j，對一條包含nk個客戶的路徑而言，需要從j=0至j=nk－1依次計算AT～^trj+1的累積分布函數(shù)，計算公式如下：

式（16）的直接計算難度較大。此時，可通過式（17）近似估計給定c值的累積概率。

其中：y0和yf為積分的上下界;I為離散點的個數(shù);dykt=FAT^trj～（c－ykt）fY～（ykt），kt∈{1，2，…，I}。式（17）的詳細計算過程參見文獻［7］。借助式（17）可獲得任意一條路徑上所有客戶的到達時刻分布函數(shù)，進而執(zhí)行機會約束檢查。若旅行時間、服務(wù)時間（一般假設(shè)為連續(xù)變量）服從其他分布，其基本的計算過程是一致的。

對一條給定路徑，若所有客戶的服務(wù)水平均不小于給定置信水平，則稱該路徑為可行路徑；反之，則稱該路徑為不可行路徑。定義路徑可行性的目的在于：a）便于算法在搜索過程中能夠有效地評價解的優(yōu)劣，使得算法具備較好的收斂性；b）不同應(yīng)用背景下路徑可行性的定義是不同的，這里明確給出路徑可行性定義也是為了避免理解上的混淆。

4 仿真實驗與結(jié)果分析

4.1 案例選擇

選用標(biāo)準Solomon算例進行仿真實驗，該算例共分為三種類型。其中，R系列客戶的位置為隨機分布，C系列客戶的位置為聚類分布，RC系列客戶的位置則為混合型分布。在R1、C1和RC1系列中，車輛單次服務(wù)客戶數(shù)量少、計劃時間短，適用于研究VRPTWSTSCC?？蛻糸g的旅行時間為服從正態(tài)分布的隨機變量，其對應(yīng)均值為客戶間距離，變異系數(shù)服從U［0.1，0.6］。車輛在任意客戶處的服務(wù)時間同樣為服從正態(tài)分布的隨機變量，其對應(yīng)均值為給定的服務(wù)時間，變異系數(shù)服從U［0.1，0.6］。兩組變異系數(shù)的選取源于文獻［7］。第2章中判斷解優(yōu)劣的相關(guān)懲罰系數(shù)ε、ω和ξ分別取值為1 000、100和2 000，算法最大運行時間設(shè)置為240 s。所有實驗均在MATLAB 2016b軟件中實現(xiàn)，計算機版本為Intel i7-6700 CPU 3.40 GHz desktop。

4.2 實驗結(jié)果分析

本文共進行三組實驗：a）運用VNILS求解VRPTW，對比不同初始解生成啟發(fā)式規(guī)則實驗結(jié)果，用于驗證MWTH和VNILS的有效性；b）運用VNILS求解VRPTWSTS（該問題是VRPTWSTSCC的簡單變形，即所有客戶均為優(yōu)質(zhì)客戶），用于說明VNILS可快速求解VRPTWSTS；c）研究客戶分類及客戶比同企業(yè)運營成本、客戶服務(wù)水平間的關(guān)系。其中，實驗a）b）均是對模型的直接求解；實驗a）中的結(jié)果為程序10次運行中發(fā)現(xiàn)的最好解，其余兩組實驗中的結(jié)果均為程序10次運行結(jié)果的平均值；實驗b）中所有客戶對應(yīng)的服務(wù)水平不小于80%，實驗c）中僅優(yōu)質(zhì)客戶對應(yīng)的服務(wù)水平不小于80%。

4.2.1 VRPTW

為驗證MWTH和VNILS的有效性，對C101等29組算例進行仿真實驗，實驗結(jié)果如表2所示。表中，OS為已知最優(yōu)解，VEH為車輛使用數(shù)，DC為車輛行駛距離，NUM為對應(yīng)初始解生成啟發(fā)式規(guī)則找到最好解的次數(shù)；NNH（nearest-neighbor heuristic）和FIH（farthest insertion heuristic）分別為最近鄰啟發(fā)式、最遠插入啟發(fā)式^{［22，23］}。由表2可知，在C1、R1和RC1系列中MWTH對應(yīng)的平均車輛使用數(shù)為11.64，小于NNH和FIH分別對應(yīng)的11.71、11.68；MWTH對應(yīng)的平均車輛行駛距離較NNH和FIH波動幅度較小；MWTH找到最好解的比例為58.62%，遠大于NNH和FIH分別對應(yīng)的34.48%、48.28%。因此，MWTH優(yōu)于NNH和FIH（比例之和不為1的原因是對同一算例，存在采用MWTH、NNH和FIH均能找到最好解的情形）。29組算例的詳細實驗結(jié)果如表3所示。由表3可知，VNILS的平均車輛使用數(shù)較已知最優(yōu)解增加了0.50，相對誤差為4.50%；平均車輛行駛距離增加了17.56，相對誤差為1.54%。這里，相對誤差是指VNILS與已知最優(yōu)解的絕對差值同已知最優(yōu)解的比值。綜上所述，VNILS在求解質(zhì)量及求解速度上均滿足實際需求。

4.2.2 VRPTWSTS

本節(jié)進一步研究VNILS求解VRPTWSTS時的性能表現(xiàn)。文獻［7，14］同樣研究了VRPTWSTS，可通過對比求解結(jié)果驗證VNILS的有效性，對比結(jié)果如表4所示。表中VEH為車輛使用數(shù)，TT為車輛運行成本，MIN_SL為最小服務(wù)水平，AV_SL為平均服務(wù)水平，AV_SLE為平均誤差，MAX_SLE為最大誤差（誤差是指離散化方法同隨機實驗方法平均服務(wù)水平的絕對差值），time為程序運行時間（s）。有關(guān)隨機試驗方法判斷路徑可行性的具體步驟參見文獻［10］。

與文獻［7］中的ILS相比，VNILS所得解的平均車輛使用數(shù)增加了0.44，占ILS車輛使用數(shù)的2.75%。車輛使用數(shù)的略微增加并沒有引起車輛運行成本的增加，相反，VNILS的平均車輛運行成本減少了212.08，占ILS車輛運行成本的12.09%。VNILS所得解的平均最小服務(wù)水平和平均服務(wù)水平較ILS分別增加了1.78%、0.62%，平均程序運行時間較ILS降低了1.45 s（占ILS程序運行時間的7.55%）。與文獻［14］中的多種群模因算法（multi-population memetic algorithm，MPMA）相比，VNILS所得解的平均車輛使用數(shù)增加了0.55，占MPMA車輛使用數(shù)的3.46%；平均車輛運行成本增加了113.45，占MPMA車輛運行成本的7.94%。車輛使用數(shù)及運行成本的小幅增加，同樣也使得平均最小服務(wù)水平、平均服務(wù)水平分別增加了2.27%、0.70%。此外，VNILS所需的平均程序運行時間較MPMA減少了14.29 s，占MPMA程序運行時間的44.60%。

這里誤差是描述離散化方法與隨機仿真方法平均客戶服務(wù)水平的接近程度，并不能反映算法優(yōu)劣，故此處不作比較。綜上所述，VNILS不劣于ILS^［7］和MPMA^［14］，可用于VRPTWSTS的求解；文中給出的求解VRPTWSTSCC的初始解生成方法是有效的，能夠顯著降低算法運行時間，為決策人員在不確定環(huán)境下制定配送路徑提供參考。

4.2.3 VRPTWSTSCC

以C106為例研究客戶分類及客戶比對實驗結(jié)果的影響，實驗結(jié)果如表5所示。客戶比為優(yōu)質(zhì)客戶數(shù)占總客戶數(shù)的比例。優(yōu)質(zhì)客戶產(chǎn)生方法如下：隨機生成一個1～n的自然數(shù)序列，對客戶比μ（采用百分數(shù)表示）而言，將序列中小于等于n×μ的元素對應(yīng)的客戶記為優(yōu)質(zhì)客戶。由表5知，考慮客戶分類有助于降低企業(yè)運營成本。以客戶比50%為例，考慮客戶分類的平均車輛使用數(shù)較未分類時降低了1.5，占未分類車輛使用數(shù)的10.27%。圖3直觀地展示了平均車輛使用數(shù)、平均顧客服務(wù)水平與客戶比之間的關(guān)系。由圖3可知，客戶比與車輛使用數(shù)呈正相關(guān)關(guān)系，這是符合實際情形的；除客戶比為0.00%外（采用VRPTW的最優(yōu)解），其余客戶比下的平均客戶服務(wù)水平（平均最小客戶服務(wù)水平）波動較小，原因在于文中的客戶服務(wù)水平是由置信水平β決定的，與客戶比的相關(guān)性較小。

5 結(jié)束語

本文研究了VRPTWSTSCC，該問題同時具備隨機性和客戶分類兩個特征，設(shè)計了VNILS算法，分別給出了確定問題、隨機問題的初始解生成方法，并通過大量的仿真實驗驗證了算法的有效性。同時，討論了MWTH和客戶分類對實驗結(jié)果的影響，分析表明MWTH優(yōu)于NNH和FIH；客戶分類有助于降低企業(yè)運營成本；客戶比與車輛使用數(shù)量呈正相關(guān)關(guān)系。本文得出的研究結(jié)論為企業(yè)管理人員應(yīng)對不確定性和有限資源帶來的不利影響（如顧客服務(wù)水平低、企業(yè)運營成本高等）提供了可行的決策參考。進一步的研究方向如下：a） 本文忽略了時間相關(guān)性，可進一步研究考慮時間相關(guān)性的VRPTWSTSCC，該類問題更具實際意義；b）本文沒有給出與客戶分類相關(guān)的指標(biāo)或特征，可進一步同物流企業(yè)等展開合作交流，獲取與客戶相關(guān)的數(shù)據(jù)并明確與客戶分類相關(guān)的指標(biāo)或特征；c）離散化方法在用于到達時刻機會約束檢查時存在準確度低的問題，可嘗試采用自適應(yīng)采樣或神經(jīng)網(wǎng)絡(luò)等方法。

參考文獻：

[1]于江霞，杜紅亞，羅太波.基于客戶分類的即時配送路徑優(yōu)化研究［J］.交通運輸系統(tǒng)工程與信息，2020，20（4）：202-208.（Yu Jiang-xia，Du Hongya，Luo Taibo.Real-time delivery routing optimization based on customer classification［J］.Journal of Transportation Systems Engineering and Information Technology，2020，20（4）：202-208.）

［2]Dantzig G B，Ramser J H.The truck dispatching problem［J］.Manage-ment Science，1959，6（1）：80-91.

［3]Braekers K，Ramaekers K，Nieuwenhuyse I V.The vehicle routing problem：state of the art classification and review［J］.Computers amp; Industrial Engineering，2016，99（9）：300-313.

［4]Oyola J，Arntzen H，Woodruff D L.The stochastic vehicle routing problem，a literature review，part Ⅰ：models［J］.EURO Journal on Transportation amp; Logistics，2018，7（3）：193-221.

［5]Oyola J，Arntzen H，Woodruff D L.The stochastic vehicle routing problem，a literature review，part Ⅱ：solution methods［J］.EURO Journal on Transportation amp; Logistics，2018，7（9）：193-221.

［6]Michel G，Ola J，Walter R .Future research directions in stochastic vehicle routing［J］.Transportation science，2016，50（4）：1163-1173.

［7]Miranda D M，Conceicao S V.The vehicle routing problem with hard time windows and stochastic travel and service time［J］.Expert Systems with Applications，2016，64（12）：104-116.

［8]Zhang Junlong，Lam W H K，Chen Biyu.A stochastic vehicle routing problem with travel time uncertainty：trade-off between cost and customer service［J］.Networks amp; Spatial Economics，2013，13（4）：471-496.

［9]Miranda D M，Branke J，Conceicao S V.Algorithms for the multi-objective vehicle routing problem with hard time windows and stochastic travel time and service time［J］.Applied Soft Computing，2018，70（9）：66-79.

［10]Li Xiangyong，Tian Peng，Leung S C H.Vehicle routing problems with time windows and stochastic travel and service times：models and algorithm［J］.International Journal of Production Economics，2010，125（1）：137-145.

［11]Ehmke J F，Campbell A M，Urban T L.Ensuring service levels in routing problems with time windows and stochastic travel times［J］.European Journal of Operational Research，2015，240（2）：539-550.

［12]Bomboi F，Buchheim C，Pruente J.On the stochastic vehicle routing problem with time windows，correlated travel times，and time depen-dency［J］.4OR，2022，20：217-239.

［13]馬俊，張紀會，郭乙運.基于混合修正策略的隨機時間車輛路徑優(yōu)化方法［J］.交通運輸工程與信息，2021，19（4）：87-97.（Ma Jun，Zhang Jihui，Guo Yiyun.Hybrid recourse policy for the vehicle routing problem with stochastic time［J］.Journal of Transportation Engineering and Information，2021，19（4）：87-97.）

［14]Gutierrez A，Dieulle L，Labadie N，et al.A multi-population algorithm to solve the VRP with stochastic service and travel times［J］.Computers amp; Industrial Engineering，2018，125（11）：144-156.

［15]Binart S，Dejax P，Gendreau M，et al.A 2-stage method for a field service routing problem with stochastic travel and service times［J］.Computers amp; Operations Research，2016，65（1）：64-75.

［16]張力婭，張錦，肖斌.考慮顧客優(yōu)先級的多目標(biāo)O2O外賣即時配送路徑優(yōu)化研究［J］.工業(yè)工程與管理，2021，26（2）：196-204.（Zhang Liya，Zhang Jin，Xiao Bin.Multi-objective O2O take-out instant delivery routing optimization considering customer priority［J］.Industrial Engineering and Management，2021，26（2）：196-204.）

［17]陳夢玲.考慮服務(wù)優(yōu)先級的共享汽車維護路徑規(guī)劃問題研究［D］.大連：東北財經(jīng)大學(xué)，2019.（Chen Mengling.Research on shared vehicle maintenance path planning considering service priority［D］.Dalian：Dongbei University of Finance amp; Economics，2019.）

［18]Penna P H V，Subramanian A，Ochi L S.An iterated local search heuristic for the heterogeneous fleet vehicle routing problem［J］.Journal of Heuristics，2013，19（2）：201-232.

［19]Shaw P.Using constraint programming and local search methods to solve vehicle routing problems［C］//Proc of the 4th International Conference on Principles and Practice of Constraint Programming.Berlin：Springer，1998：417-431.

［20]Emec U，Catay B，Bozkaya B.An adaptive large neighborhood search for an e-grocery delivery routing problem［J］.Computers amp; Operations Research，2016，69（5）：109-125.

［21]陳萍.啟發(fā)式算法及其在車輛路徑問題中的應(yīng)用［D］.北京：北京交通大學(xué)，2009.（Chen Ping.Research on heuristic algorithms and their applications in the vehicle routing problem［D］.Beijing：Beijing Jiaotong University，2009.）

［22]Solomon M M.Algorithms for the vehicle routing and scheduling problems with time window constraints［J］.Operations Research，1987，35（2）：254-265.

［23]穆東，王超，王勝春，等.基于并行模擬退火算法求解時間依賴型車輛路徑問題［J］.計算機集成制造系統(tǒng)，2015，21（6）：1626-1636.（Mu Dong，Wang Chao，Wang Shengchun，et al.Solving TDVRP based on parallel-simulated annealing algorithm［J］.Computer Integrated Manufacturing Systems，2015，21（6）：1626-1636.）