考慮客戶分類的隨機(jī)時(shí)間車輛路徑優(yōu)化模型與算法

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

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

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

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

doi：10.19734/j.issn.1001-3695.2021.12.0673

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

作者簡介：馬俊（1995-），男，安徽宿州人，碩士，主要研究方向?yàn)檐囕v路徑優(yōu)化；張紀(jì)會(huì)（1969-），男（通信作者），山東濰坊人，教授，博導(dǎo)，博士，主要研究方向?yàn)橹悄軆?yōu)化理論與方法、系統(tǒng)工程（zhangjihui@qdu.edu.cn）；郭乙運(yùn)（1979-），男，山東日照人，高級工程師，碩士，主要研究方向?yàn)楝F(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ù)的時(shí)效性和準(zhǔn)時(shí)性要求愈發(fā)嚴(yán)格，如何在有限的服務(wù)資源下給出經(jīng)濟(jì)可行且滿足客戶要求的配送路徑已成為眾多企業(yè)面臨的難題。客戶分類是企業(yè)應(yīng)對上述問題的主要措施之一，其利用有限的資源確保優(yōu)質(zhì)客戶的服務(wù)水平，以實(shí)現(xiàn)提高企業(yè)收益、維持客戶忠誠度等目的。在大數(shù)據(jù)技術(shù)廣泛使用的背景下，決策人員能夠大量獲得與客戶相關(guān)的信息，已知客戶相關(guān)信息的前提下，對客戶分類的方法有很多，如文獻(xiàn)［1］的DBSCAN方法。本文不涉及客戶分類方法，重點(diǎn)研究已知客戶分類，考慮隨機(jī)旅行時(shí)間、隨機(jī)服務(wù)時(shí)間及時(shí)間窗約束的車輛路徑問題（vehicle routing problem with time window，stochastic travel and service time，and customer classification，VRPTWSTSCC），旨在給出經(jīng)濟(jì)可行的配送方案，揭示客戶分類對企業(yè)運(yùn)營成本及客戶服務(wù)水平的影響。該問題有著廣泛的應(yīng)用背景，如美團(tuán)、餓了么等平臺提供的“準(zhǔn)時(shí)達(dá)”配送服務(wù)，對購買“準(zhǔn)時(shí)達(dá)”服務(wù)的顧客，若騎手的實(shí)際到達(dá)時(shí)刻晚于預(yù)計(jì)到達(dá)時(shí)刻，則平臺依據(jù)遲到程度給予不同金額的補(bǔ)償。這里預(yù)計(jì)到達(dá)時(shí)刻是一個(gè)期望值，而實(shí)際到達(dá)時(shí)刻受到諸如天氣狀況、路段車流量等因素的影響，其本身是一個(gè)不確定的變量。

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

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

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

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

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

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

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

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

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

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

2 迭代局部搜索算法

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

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

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

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

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

算法1 變鄰域搜索

begin

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

給定解s；

repeat

i1， tag1；

while i≤imax（imax為鄰域搜索算子個(gè)數(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）擾動(dòng)算子。擾動(dòng)強(qiáng)度在很大程度上決定了擾動(dòng)效果，若擾動(dòng)強(qiáng)度過大，則算法退化為隨機(jī)多起點(diǎn)算法；若擾動(dòng)強(qiáng)度過小，則算法無法逃離局部最優(yōu)解。參考文獻(xiàn)［21］，采用cross-change擾動(dòng)算子，操作流程如圖2所示，詳細(xì)步驟如下：隨機(jī)選擇兩條路徑，并隨機(jī)生成每條路徑上的第1個(gè)節(jié)點(diǎn)，第2個(gè)節(jié)點(diǎn)的選擇取決于節(jié)點(diǎn)間（截?cái)嗖糠郑┑目蛻魯?shù)量。其中，節(jié)點(diǎn)間的客戶數(shù)量服從U［2，4］。若第2個(gè)節(jié)點(diǎn)的位置大于當(dāng)前路徑長度，則截?cái)嗖糠譃榈?個(gè)節(jié)點(diǎn)至該路徑上的最后一個(gè)顧客。按圖2的交換規(guī)則，完成對當(dāng)前路徑的擾動(dòng)。

d）解的接受準(zhǔn)則。對每一個(gè)局部最優(yōu)解s均施加一個(gè)擾動(dòng)，記擾動(dòng)解為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）的表達(dá)形式分別如式（13）（14）所示。

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

3 路徑可行性判斷

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

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

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

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

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

4 仿真實(shí)驗(yàn)與結(jié)果分析

4.1 案例選擇

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

4.2 實(shí)驗(yàn)結(jié)果分析

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

4.2.1 VRPTW

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

4.2.2 VRPTWSTS

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

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

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

4.2.3 VRPTWSTSCC

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

5 結(jié)束語

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

參考文獻(xiàn)：

[1]于江霞，杜紅亞，羅太波.基于客戶分類的即時(shí)配送路徑優(yōu)化研究［J］.交通運(yùn)輸系統(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]馬俊，張紀(jì)會(huì)，郭乙運(yùn).基于混合修正策略的隨機(jī)時(shí)間車輛路徑優(yōu)化方法［J］.交通運(yùn)輸工程與信息，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外賣即時(shí)配送路徑優(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)先級的共享汽車維護(hù)路徑規(guī)劃問題研究［D］.大連：東北財(cái)經(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]穆東，王超，王勝春，等.基于并行模擬退火算法求解時(shí)間依賴型車輛路徑問題［J］.計(jì)算機(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.）