王永超 肖秋迪

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

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

0 引言

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

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

1 研究綜述

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

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

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

2 問題建模

2.1 問題描述

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

2.2 模型建立

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

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

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

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

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

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

2.3 符號定義

2.3.1 索引和集合

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

j為標簽序號，J為標簽集合，J={1，2，…，m}，m為標簽總數(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為標簽j的車型規(guī)格，j∈J;

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

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

wj為標簽j的稽核時長;

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

2.3.3 決策變量

xij∈{0，1}，當稽核單元i被用于標簽j時則取1，否則取0;

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

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

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

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

rjj′∈{0，1}，同一稽核單元內，當標簽j與標簽j′相鄰時則取1，否則取0;

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

2.4 問題模型

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

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

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

3.1 算法策略

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

3.2 算法設計

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

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

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

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

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

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

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

4.1 實驗設計

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

4.2 實驗結果及分析

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

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

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

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

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

5 結語

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

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

參考文獻：

[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]趙 彥，吳淑玲，林志恒，常天海.高速公路通行卡逃費行為預測模型研究[J].中國科技論文，2015，10（19）：2245-2251.

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

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

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

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

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

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