基于VNS-SA算法的廣西ETC發(fā)行數(shù)據(jù)稽核問題研究

王永超 肖秋迪

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

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

0 引言

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

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

1 研究綜述

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

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

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

2 問題建模

2.1 問題描述

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

2.2 模型建立

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

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

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

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

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

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

2.3 符號(hào)定義

2.3.1 索引和集合

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

j為標(biāo)簽序號(hà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的稽核時(shí)長(zhǎng);

Amin為單元稽核時(shí)長(zhǎng)下限，Amax為單元稽核時(shí)長(zhǎng)上限。

2.3.3 決策變量

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

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

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

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

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

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

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

2.4 問題模型

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

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

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

3.1 算法策略

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

3.2 算法設(shè)計(jì)

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

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

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

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

更新當(dāng)前解時(shí)，采用極大值標(biāo)準(zhǔn)化方法對(duì)當(dāng)前解和當(dāng)前局部最優(yōu)解的三個(gè)目標(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表示兩個(gè)綜合目標(biāo)函數(shù)值的增量，這里Δf=f′（x′）-f′（x）。若Δf<0，則無(wú)條件接受當(dāng)前局部最優(yōu)解x′;若Δf>0，則通過概率pxx′=exp（-Δf/Tn）來(lái)判斷是否接受當(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時(shí)，則轉(zhuǎn)鄰域結(jié)構(gòu)N（x）繼續(xù)執(zhí)行局部搜索;否則，算法停止，輸出代數(shù)為Gen的可行解x作為最終解輸出。具體如圖1所示：

4 數(shù)據(jù)實(shí)驗(yàn)

4.1 實(shí)驗(yàn)設(shè)計(jì)

本次研究選取廣西ETC發(fā)行服務(wù)機(jī)構(gòu)的車載標(biāo)簽發(fā)行數(shù)據(jù)，抽取其中某日發(fā)生首次通行交易的標(biāo)簽信息。參數(shù)設(shè)定：最大迭代數(shù)Gen=150;同一稽核單元車型差異懲罰權(quán)值α=0.5;標(biāo)簽稽核平均等待時(shí)間懲罰權(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 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

5 結(jié)語(yǔ)

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

采用了VNS-SA算法對(duì)模型進(jìn)行迭代求解。通過引入對(duì)比實(shí)驗(yàn)進(jìn)行分析，VNS-SA算法最終的收斂結(jié)果較VNS算法提高了13%，較NS算法提高了20%。因此，VNS-SA算法具備更好的全局搜索能力，且最終具備良好的收斂結(jié)果，優(yōu)化效果也較為顯著。在后續(xù)的研究中，可考慮增加卡簽匹配性稽核等約束條件，及增加協(xié)同稽核等約束能力進(jìn)行研究，以進(jìn)一步完善問題模型。同時(shí)，也可考慮發(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)高速公路收費(fèi)稽查工作[J].中國(guó)交通信息產(chǎn)業(yè)，2006（4）：50-53.

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

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

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

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

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

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

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