基于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算法进行对比实验。现采用求解出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.