考慮客戶分類的隨機時間車輛路徑優化模型與算法

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

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

中圖分類號：TP301.6 文獻標志碼：A

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

doi：10.19734/j.issn.1001-3695.2021.12.0673

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

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

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 引言

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

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

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

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

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

1 機會約束規劃模型

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

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

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

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

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

2 迭代局部搜索算法

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

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

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

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

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

算法1 變鄰域搜索

begin

定義鄰域結構Ni={swap，2-opt，2-opt*，破壞/修復}；

給定解s；

repeat

i1， tag1；

while i≤imax（imax為鄰域搜索算子個數）

s*=localsearch（s，Ni）；

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

tagture；

ss*；

end if

ii+1；

end while

until tag1

return s

end

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

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

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

3 路徑可行性判斷

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

其中：t為截斷點。同時，令Y～j為車輛在客戶j和j+1間旅行時間及在客戶j處服務時間之和，故Y～j同樣為服從正態分布的隨機變量，記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的累積分布函數，計算公式如下：

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

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

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

4 仿真實驗與結果分析

4.1 案例選擇

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

4.2 實驗結果分析

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

4.2.1 VRPTW

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

4.2.2 VRPTWSTS

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

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

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

4.2.3 VRPTWSTSCC

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

5 結束語

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

參考文獻：

[1]于江霞，杜紅亞，羅太波.基于客戶分類的即時配送路徑優化研究［J］.交通運輸系統工程與信息，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]馬俊，張紀會，郭乙運.基于混合修正策略的隨機時間車輛路徑優化方法［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]張力婭，張錦，肖斌.考慮顧客優先級的多目標O2O外賣即時配送路徑優化研究［J］.工業工程與管理，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]陳夢玲.考慮服務優先級的共享汽車維護路徑規劃問題研究［D］.大連：東北財經大學，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]陳萍.啟發式算法及其在車輛路徑問題中的應用［D］.北京：北京交通大學，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］.計算機集成制造系統，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.）