王永超 肖秋迪

摘要：發(fā)行數(shù)據(jù)稽核作為ETC稽核業(yè)務(wù)鏈的開端，高質(zhì)量的發(fā)行數(shù)據(jù)是降低高速公路參與方通行費流失的重要途徑之一。文章以發(fā)行數(shù)據(jù)的車型差異、發(fā)行日期、發(fā)行渠道差異為約束，結(jié)合相應(yīng)稽核業(yè)務(wù)規(guī)程和稽核能力約束，以最小化車型差異為主要目標(biāo)，以最小化稽核平均等待時間和最小化發(fā)行渠道差異為次要目標(biāo)，構(gòu)建了基于變鄰域模擬退火算法的工作計劃問題模型，并將廣西ETC發(fā)行數(shù)據(jù)作為實驗算例集，引入NS算法及VNS算法進(jìn)行對比實驗。實驗結(jié)果表明，該ETC發(fā)行數(shù)據(jù)稽核工作計劃模型與求解算法可行且有效。

關(guān)鍵詞：ETC;VNS-SA算法;發(fā)行數(shù)據(jù);稽核工作計劃;變鄰域搜索;模擬退火

0 引言

2019年5月我國交通運輸部發(fā)布《取消高速公路省界收費站總體技術(shù)方案》，要求年底前基本實現(xiàn)取消全國高速公路省界收費站。為此，各省被分派的ETC標(biāo)簽發(fā)行任務(wù)量劇增，各主體發(fā)行機構(gòu)都在大力布局車載標(biāo)簽在線上和線下的推廣及發(fā)行，積極拓寬業(yè)務(wù)辦理渠道，包括通過自營機構(gòu)，以及與各高速公路運營公司、商業(yè)銀行和第三方機構(gòu)進(jìn)行合作，以擴增ETC用戶量及服務(wù)規(guī)模。

短時間內(nèi)ETC發(fā)行量的暴增，引發(fā)了一些亂象。以廣西為例，在線下業(yè)務(wù)中，沉重的發(fā)行任務(wù)量考核和高額的業(yè)績提成，導(dǎo)致違規(guī)發(fā)行、標(biāo)簽信息錯配、審核缺失等情況頻出;在線上業(yè)務(wù)中，由于主要依靠車主自行完成車輛信息錄入及標(biāo)簽的激活，極易出現(xiàn)虛假行駛證、標(biāo)簽信息錯配等情況。由ETC發(fā)行亂象所引發(fā)大車小標(biāo)、車種不符等情況，造成車輛駕駛?cè)藛T無意或惡意逃費，最終可能會導(dǎo)致收費站現(xiàn)場核查時的秩序混亂或利益相關(guān)方通行費損失的后果。因此，對與日俱增的ETC發(fā)行數(shù)據(jù)進(jìn)行全面高效地稽核成為目前高速公路全網(wǎng)稽核業(yè)務(wù)工作的前哨環(huán)節(jié)。

1 研究綜述

各界針對我國高速公路全網(wǎng)稽核業(yè)務(wù)的研究中，主要關(guān)注于車輛駕駛?cè)藛T實際通行階段由人為因素造成的偷逃通行費的行為，其中包括收費人員違規(guī)操作、運營管理單位管理漏洞、車輛駕駛?cè)藛T惡意逃費等。李銳[2]等提出了治理偷逃通行費主要使用收費稽查的方式，指出偷逃高速通行費的可用作弊手段以及補足管理和制度漏洞的方法;趙彥[3]等人就使用通行卡偷逃通行費高發(fā)的現(xiàn)象，及低效的人工稽核現(xiàn)狀，提出了識別率較高的通行卡逃費行為預(yù)測模型;羅巍[4]運用案例分析法，就湖北省高速偷逃通行費現(xiàn)象的治理構(gòu)建了數(shù)據(jù)模型，并提出了合理化建議;陳爾希[6]針對廣東省高速偷逃通行費現(xiàn)象，通過稽查分類和SMOTE算法，獲得稽查分類的數(shù)據(jù)模型。而當(dāng)前對ETC發(fā)行機構(gòu)違規(guī)發(fā)行問題的稽核研究較少，由于車載標(biāo)簽的發(fā)行作為ETC稽核業(yè)務(wù)鏈的開端，提高數(shù)據(jù)的準(zhǔn)確性至關(guān)重要。結(jié)合啟發(fā)式算法的特點，在針對編制大量車載標(biāo)簽的稽核工作計劃時，其在工作計劃的調(diào)優(yōu)中扮演重要角色。

變鄰域搜索算法最早由Hansen等提出，屬于單點元啟發(fā)式算法，后期延伸出VNS算法的許多擴展版本，包括變鄰域深度搜索算法、簡化變鄰域搜索算法和并行變鄰域搜索算法等。其通過在搜索過程中系統(tǒng)地改變鄰域結(jié)構(gòu)集來拓展搜索范圍，達(dá)到動態(tài)改變算法鄰域結(jié)構(gòu)的目的，增強算法的全局搜索性能。在算法研究鄰域，模擬退火搜索算法和禁忌搜索等元啟發(fā)式算法已融入到了變鄰域搜索算法的研究當(dāng)中。

模擬退火算法最早由Metropolis等于1953年提出，Kirkpatrick等于1983年將其引入了組合優(yōu)化領(lǐng)域，成功地利用它來解決大規(guī)模的組合優(yōu)化問題。該算法起源于對熱力學(xué)中退火過程的模擬，在某一給定初始溫度下，通過緩慢降低溫度參數(shù)，使其能夠在多項式時間內(nèi)得出一個近似最優(yōu)解，是一種理論上的全局最優(yōu)解。

2 問題建模

2.1 問題描述

本文以ETC車載標(biāo)簽發(fā)行稽核工作計劃問題為研究對象，首先對問題進(jìn)行闡述和界定。由于稽核工作目前強依賴于人力投入，在總稽核能力有限的情況下，短期內(nèi)無法完成所有已發(fā)行車載標(biāo)簽的稽核工作。本研究選取已產(chǎn)生通行交易的車載標(biāo)簽編制稽核工作計劃，依據(jù)車載標(biāo)簽的車型差異、發(fā)行日期、發(fā)行渠道差異約束，結(jié)合相應(yīng)稽核業(yè)務(wù)規(guī)程和稽核能力約束，以完成對待稽核車載標(biāo)簽的排序，并將排序結(jié)果劃分為若干個聚類分組及使用若干個稽核單元進(jìn)行稽核，最后實現(xiàn)稽核單元執(zhí)行序列的初始化。構(gòu)建了以最小化車型差異所引起的重點稽核內(nèi)容變化為主要目標(biāo)，以最小化標(biāo)簽稽核平均等待時間為次要目標(biāo)，以最小化發(fā)行渠道差異所引起的稽核策略更替的ETC車載標(biāo)簽為發(fā)行數(shù)據(jù)稽核工作計劃的數(shù)學(xué)模型，為下一步研究奠定基礎(chǔ)。

2.2 模型建立

針對問題中提出的三個優(yōu)化目標(biāo)，本文采取并行處理策略，依據(jù)其重要性的不同，依次給予模型中的三個優(yōu)化目標(biāo)以適當(dāng)權(quán)重進(jìn)行優(yōu)化。（1）將ETC車載標(biāo)簽按車型、發(fā)行日期、發(fā)行渠道進(jìn)行排序，并將排序結(jié)果進(jìn)行聚類分組并順序置入若干個稽核單元內(nèi)，便可將此稽核單元序列定義為一個初始可行解。（2）在利用變鄰域模擬退火搜索算法不斷優(yōu)化稽核單元內(nèi)車型差異所引起的重點稽核內(nèi)容變化懲罰值的基礎(chǔ)上，綜合考慮標(biāo)簽稽核平均等待時間懲罰值和稽核單元內(nèi)發(fā)行渠道差異所引起的稽核策略更替懲罰值。在算法經(jīng)若干次迭代后，最終可獲得該模型的合理有效解。

基于對ETC車載標(biāo)簽發(fā)行稽核工作計劃問題的分析，現(xiàn)做出如下假設(shè)：

（1）所有篩選出的ETC車載標(biāo)簽均需要進(jìn)行發(fā)行信息稽核;

（2）ETC車載標(biāo)簽只考慮車型、發(fā)行日期、發(fā)行渠道不同的情況;

（3）單個ETC車載標(biāo)簽稽核工作量小于單元稽核能力;

（4）除人力資源因素外，其余稽核所需資源均可滿足。

2.3 符號定義

2.3.1 索引和集合

i為稽核單元序號，I為稽核單元集合，I={1，2，…，n}，n為稽核單元總數(shù)，i∈I;

j為標(biāo)簽序號，J為標(biāo)簽集合，J={1，2，…，m}，m為標(biāo)簽總數(shù)，j∈J;

f為車型規(guī)格，F(xiàn)為車型規(guī)格集合，F(xiàn)={1，2，…，h}，h為車型規(guī)格總數(shù)，f∈F;

d為發(fā)行日期，D為發(fā)行日期集合，D={1，2，…，l}，l為發(fā)行日期總數(shù)，d∈D;

g為發(fā)行渠道類型，G為發(fā)行渠道類型集合，G={1，2，…，s}，s為發(fā)行渠道類型總數(shù)，g∈G。

2.3.2 模型參數(shù)

fj為標(biāo)簽j的車型規(guī)格，j∈J;

dj為標(biāo)簽j的發(fā)行日期，j∈J;

gj為標(biāo)簽j的發(fā)行渠道類型，j∈J;

wj為標(biāo)簽j的稽核時長;

Amin為單元稽核時長下限，Amax為單元稽核時長上限。

2.3.3 決策變量

xij∈{0，1}，當(dāng)稽核單元i被用于標(biāo)簽j時則取1，否則取0;

zif∈{0，1}，當(dāng)稽核單元i用包含車型f時則取1，否則取0;

yig∈{0，1}，當(dāng)稽核單元i用包含發(fā)行渠道g時則取1，否則取0;

pii′∈{0，1}，當(dāng)稽核單元i先于稽核單元i′生產(chǎn)時則取1，否則取0;

qii′∈{0，1}，當(dāng)稽核單元i與稽核單元i′相鄰時則取1，否則取0;

rjj′∈{0，1}，同一稽核單元內(nèi)，當(dāng)標(biāo)簽j與標(biāo)簽j′相鄰時則取1，否則取0;

eii′∈{0，1}，當(dāng)稽核單元i中標(biāo)簽的平均發(fā)行日期晚于稽核單元i′中標(biāo)簽的平均發(fā)行日期時則取1，否則取0。

2.4 問題模型

針對ETC標(biāo)簽發(fā)行稽核工作計劃問題，建立如下模型：

其中，式（1）的目標(biāo)函數(shù)表示同一稽核單元內(nèi)，最小化車型差異所引起的重點稽核內(nèi)容變化的懲罰值;式（2）的目標(biāo)函數(shù)表示最小化標(biāo)簽稽核平均等待時間的懲罰值;式（3）的目標(biāo)函數(shù)表示同一稽核單元內(nèi)，最小化發(fā)行渠道差異所引起的稽核策略更替的懲罰值;式（4）的約束表示稽核單元i內(nèi)至少包含一個標(biāo)簽;式（5）的約束表示每個標(biāo)簽僅且包含于某一稽核單元中;式（6）的約束表示非最后一個稽核單元i后僅且存在一個稽核單元i′;式（7）的約束表示稽核單元間因標(biāo)簽稽核平均等待時間產(chǎn)生懲罰的對應(yīng)關(guān)系;式（8）的約束表示稽核單元i內(nèi)所有標(biāo)簽的總稽核時長在稽核單元總時長上下限范圍內(nèi)。

3 變鄰域模擬退火搜索算法

3.1 算法策略

變鄰域搜索算法通過在算法演進(jìn)過程中搜索不同的鄰域結(jié)構(gòu)，實現(xiàn)對解空間更全面的搜索，使算法不至于陷入局部搜索中。而模擬退火算法作為一種全局搜索算法，其將模擬退火接受（Metropolis）準(zhǔn)則作為解的接受準(zhǔn)則，擴大算法迭代伊始解的接受范圍，使算法具備了很強的全局搜索性能。因此，本文將以變鄰域搜索算法作為ETC車載標(biāo)簽發(fā)行稽核工作計劃模型求解算法設(shè)計框架，重點針對算法的鄰域結(jié)構(gòu)集以及局部搜索策略進(jìn)行了設(shè)計。使用交換算子的形式搭建鄰域結(jié)構(gòu)集，并使用or-opt算法作為局部搜索策略。同時，將Metropolis準(zhǔn)則嵌入其中，使算法具備更強的全局搜索性能，更大概率收斂于全局最優(yōu)解。

3.2 算法設(shè)計

本文針對ETC車載標(biāo)簽發(fā)行數(shù)據(jù)稽核工作計劃問題提出了三個優(yōu)化目標(biāo)，初始化策略分為以下3個步驟：首先，依據(jù)標(biāo)簽的車型、發(fā)行日期和發(fā)行渠道對標(biāo)簽優(yōu)先級排序;接著，根據(jù)單元稽核能力約束，將排序結(jié)果聚類分組;初始化稽核單元信息，初始化終止。依次輸出初始化稽核單元的工作計劃序列，并作為原初始可行解x。

在構(gòu)造鄰域結(jié)構(gòu)中，采取交換算子方式，依算法迭代的演進(jìn)依次循環(huán)選取算子組合C1和C2，通過交換算子組合中節(jié)點的位置，構(gòu)建相應(yīng)鄰域結(jié)構(gòu)N（x），并把它當(dāng)作當(dāng)前代需要執(zhí)行局部搜索的鄰域結(jié)構(gòu)。

在執(zhí)行局部搜索時，選用or-opt算法對所搭建的鄰域結(jié)構(gòu)N（x）執(zhí)行局部搜索，包括依次使用

or-opt-1，or-opt-2和or-opt-3三種交換方法。通過使用Min-max數(shù)據(jù)標(biāo)準(zhǔn)化方法對目標(biāo)函數(shù)值進(jìn)行處理，并依次賦予三個目標(biāo)函數(shù)值以對應(yīng)的權(quán)值，以獲取解的綜合目標(biāo)函數(shù)Z值，并將Z值最小的解作為該鄰域的最優(yōu)解。

更新當(dāng)前解時，采用極大值標(biāo)準(zhǔn)化方法對當(dāng)前解和當(dāng)前局部最優(yōu)解的三個目標(biāo)函數(shù)值進(jìn)行歸一化處理，使當(dāng)前解的綜合目標(biāo)函數(shù)f（x）轉(zhuǎn)換成f′（x），當(dāng)前局部最優(yōu)解的綜合目標(biāo)函數(shù)f（x′）轉(zhuǎn)換成f′（x′），令Δf表示兩個綜合目標(biāo)函數(shù)值的增量，這里Δf=f′（x′）-f′（x）。若Δf<0，則無條件接受當(dāng)前局部最優(yōu)解x′;若Δf>0，則通過概率pxx′=exp（-Δf/Tn）來判斷是否接受當(dāng)前局部最優(yōu)解x′;若pxx′>ξ，其中ξ=U（0，1），則接受當(dāng)前局部最優(yōu)解x′，并更新當(dāng)前解為x′，否則，沿用x作為當(dāng)前解。

若算法當(dāng)前演進(jìn)代數(shù)小于所設(shè)定的終止代數(shù)Gen時，則轉(zhuǎn)鄰域結(jié)構(gòu)N（x）繼續(xù)執(zhí)行局部搜索;否則，算法停止，輸出代數(shù)為Gen的可行解x作為最終解輸出。具體如圖1所示：

4 數(shù)據(jù)實驗

4.1 實驗設(shè)計

本次研究選取廣西ETC發(fā)行服務(wù)機構(gòu)的車載標(biāo)簽發(fā)行數(shù)據(jù)，抽取其中某日發(fā)生首次通行交易的標(biāo)簽信息。參數(shù)設(shè)定：最大迭代數(shù)Gen=150;同一稽核單元車型差異懲罰權(quán)值α=0.5;標(biāo)簽稽核平均等待時間懲罰權(quán)值β=0.3;同一稽核單元發(fā)行渠道差異懲罰權(quán)值ε=0.2;初始溫度T=1，降溫系數(shù)r=0.95。組成4組算例，其中標(biāo)簽J={500，1000，5000，10000}，具體信息如表1所示。

4.2 實驗結(jié)果及分析

針對表1中的4組算例，同時引入NS和VNS算法，將其與VNS-SA算法進(jìn)行對比實驗。現(xiàn)采用求解出3種算法的末代綜合目標(biāo)函數(shù)值與初始代綜合目標(biāo)函數(shù)值的比值，實現(xiàn)就算法收斂結(jié)果的分析，實驗結(jié)果見表2。

經(jīng)對比分析，在算例標(biāo)簽規(guī)模較小時，VNS-SA算法、VNS算法的收斂結(jié)果差別較小，但明顯好于NS算法。在算例標(biāo)簽規(guī)模≥5000時，3種算法的搜索性能由強至弱依次為VNS-SA算法>VNS算法>NS算法。同時，也證實了VNS-SA算法具備更好的全局搜索性能，較無Metropolis準(zhǔn)則的VNS算法具備更好的收斂結(jié)果，優(yōu)化效果更為顯著。

現(xiàn)將表2中第4組算例在算法迭代過程中的曲線變化情況進(jìn)行展示，其3個目標(biāo)的函數(shù)懲罰值變化曲線如圖2所示。

VNS-SA算法迭代的綜合目標(biāo)函數(shù)懲罰值變化曲線如圖3所示，該曲線整體趨勢呈現(xiàn)為震蕩下行走勢，并最終趨于穩(wěn)定。由于算法中Metropolis準(zhǔn)則的嵌入，導(dǎo)致Gen=30代之前，曲線波動劇烈，偶爾會出現(xiàn)短暫上行的現(xiàn)象。但隨著算法的迭代演進(jìn)，劣解逐漸難以被接受，算法也趨于穩(wěn)定。

VNS-SA算法實驗結(jié)果如表3所示，算法在Gen=60代后漸趨于穩(wěn)定，并于Gen=120代后收斂至穩(wěn)定狀態(tài)。因此，算法設(shè)定演進(jìn)至Gen=150代時停止運行是合理的。

5 結(jié)語

本文針對ETC發(fā)行數(shù)據(jù)稽核工作計劃問題進(jìn)行研究，通過構(gòu)建以最小化車型差異為主要目標(biāo)，以最小化稽核平均等待時間和最小化發(fā)行渠道差異為次要目標(biāo)的問題模型，

采用了VNS-SA算法對模型進(jìn)行迭代求解。通過引入對比實驗進(jìn)行分析，VNS-SA算法最終的收斂結(jié)果較VNS算法提高了13%，較NS算法提高了20%。因此，VNS-SA算法具備更好的全局搜索能力，且最終具備良好的收斂結(jié)果，優(yōu)化效果也較為顯著。在后續(xù)的研究中，可考慮增加卡簽匹配性稽核等約束條件，及增加協(xié)同稽核等約束能力進(jìn)行研究，以進(jìn)一步完善問題模型。同時，也可考慮發(fā)掘適用于該模型的算法，加快模型的求解效率。

參考文獻(xiàn)：

[1]Hansen，P.，Mladenovi，N.，Pérez，J.A.M.Variableneighbourhoodsearch：methodsandapplications[J].AnnalsofOperationsResearch，2010，175（1）：367-407.

[2]李 銳，徐 俊.逐步完善聯(lián)網(wǎng)高速公路收費稽查工作[J].中國交通信息產(chǎn)業(yè)，2006（4）：50-53.

[3]趙 彥，吳淑玲，林志恒，常天海.高速公路通行卡逃費行為預(yù)測模型研究[J].中國科技論文，2015，10（19）：2245-2251.

[4]羅 巍.基于數(shù)據(jù)挖掘的高速公路聯(lián)網(wǎng)收費稽查系統(tǒng)應(yīng)用研究[J].企業(yè)改革與管理，2018（4）：74，85.

[5]陳平迪.廣東省高速公路車輛偷逃費用的預(yù)測與稽查分析[J].當(dāng)代經(jīng)濟，2018，488（20）：132-134.

[6]陳爾希.基于通行大數(shù)據(jù)的車輛逃費稽查系統(tǒng)的研究與開發(fā)[D].南京：東南大學(xué)，2018.

[7]汪定偉.智能優(yōu)化方法[M].北京：高等教育出版社，2007.

[8]董紅宇，黃 敏，王興偉，等.變鄰域搜索算法綜述[J].控制工程，2009（S2）：1-5.

[9]雷英杰.MATLAB遺傳算法工具箱及應(yīng)用[M].西安：西安電子科技大學(xué)出版社，2014.