基于VNS-SA算法的廣西ETC發行數據稽核問題研究

王永超 肖秋迪

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

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

0 引言

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

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

1 研究綜述

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

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

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

2 問題建模

2.1 問題描述

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

2.2 模型建立

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

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

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

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

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

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

2.3 符號定義

2.3.1 索引和集合

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

j為標簽序號，J為標簽集合，J={1，2，…，m}，m為標簽總數，j∈J;

f為車型規格，F為車型規格集合，F={1，2，…，h}，h為車型規格總數，f∈F;

d為發行日期，D為發行日期集合，D={1，2，…，l}，l為發行日期總數，d∈D;

g為發行渠道類型，G為發行渠道類型集合，G={1，2，…，s}，s為發行渠道類型總數，g∈G。

2.3.2 模型參數

fj為標簽j的車型規格，j∈J;

dj為標簽j的發行日期，j∈J;

gj為標簽j的發行渠道類型，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用包含發行渠道g時則取1，否則取0;

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

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

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

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

2.4 問題模型

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

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

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

3.1 算法策略

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

3.2 算法設計

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

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

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

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

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

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

4 數據實驗

4.1 實驗設計

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

4.2 實驗結果及分析

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

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

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

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

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

5 結語

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

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

參考文獻：

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

[2]李 銳，徐 俊.逐步完善聯網高速公路收費稽查工作[J].中國交通信息產業，2006（4）：50-53.

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

[4]羅 巍.基于數據挖掘的高速公路聯網收費稽查系統應用研究[J].企業改革與管理，2018（4）：74，85.

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

[6]陳爾希.基于通行大數據的車輛逃費稽查系統的研究與開發[D].南京：東南大學，2018.

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

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

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