农村公路治超站选址与治超车路径优化研究

蒋劲羽，赵 旭，李铖钰，杨忠振

(1.大连海事大学 交通运输工程学院，辽宁 大连 116000；2.宁波大学 海运学院，浙江 宁波 315800)

0 引 言

目前，对农村公路的超载治理主要由超载检测站即治超站完成。设置在货车流量较大且超载现象严重的路段上的治超站，通过对过往的货车进行称重检测，发现超载行为的货车，对其进行相应的处罚。由于农村公路的路网连接复杂，货车在农村公路上具有丰富的走行路线，导致超载货车多会绕行躲避治超站。因此，固定治超的模式很难有效的截获超载货车，治超效率和治超效果较差。为了提高治超效率和治超效果，笔者提出了依托固定治超站实施移动治超的工作模式，即设置一定数量的治超站，治超车以治超站为基地在其周边农村公路上巡游，捕获超载车辆，从而实施移动治超。

国内外研究者对超载治理做了一定研究。S.BAGUI等[1]提出超载对路面造成的额外损害需要超载运输业者来补偿；E.MORENO-QUINTERO等[2]同时考虑运输业者的运输成本和超载管理者的运营成本，建立了管理者运营方案决策和运输业者运输方案选择的双层规划模型；李忠奎等[3]分析了企业利润与运输价格、运输成本、超载罚款等变量之间的互动关系及企业获得最大利润的条件，对中国治理超载超限运输提出了解决方案和具体的政策建议；陈荫三[4]提出了以货车实际总重和轴载限额为依据对货车实施计重收费的思路，采用区别对待、体现公平、分步推进、累积治理的收费原则，对超载运输治理的长效性进行了研究。以上均为宏观层面的对策和策略研究，未涉及具体的治超方案优化。笔者从设施选址-车辆路径优化出发，对治超站的选址和治超车路径进行了研究。

选址和路径联合优化模型(location routing problem，LRP)是一类反应设施选址和车辆路线决策间相互依赖关系的模型。传统的选址-路径模型和扩展的选址-路径模型(如：带时间窗、带容量限制等的选址-路径模型)被广泛地应用在多个领域，如配送中心的选址-车辆路径优化问题[5-7]、仓库的选址-车辆路径优化问题[8，9]、公路设施的选址和车辆路径优化问题[10]，以及其它设施的选址-车辆路径问题[11，12]。选址-路径问题作为非确定性多项式困难问题(NP-hard)，目前的求解方法主要有精确算法和启发式算法[13]。对于候选选址点集合规模大，需建设的设施数目不确定状况，TING Chingjung等[14]提出用多层嵌套的蚁群算法来求解大规模的设施选址-车辆路径问题，但由于使用了多个蚁群算法进行求解，计算的随机性增加，导致算法容易陷入局部最优，从而影响其寻优精度。

笔者改进了多层嵌套的蚁群算法。首先，在以治超站为基地实施农村公路移动治超的工作模式下，为使超载治理的成本达到最少，构建了可同时确定治超站数量、治超站选址及以治超站为基地的治超车巡游路径优化模型，设计了二级嵌套的蚁群算法，求解具有大规模候选点集合和最大可设置设施数不确定的选址-路径问题；然后，为验证模型和算法的可行性，利用贵阳市农村公路上的超载现状数据实施案例分析。结果表明，治超站被选在矿产资源丰富、施工场地密集的地区，周边矿运货车和渣土车的超载运输现象明显，且治超车的巡游路线包含多条货车流量大的省县干道；计算结果验证了模型和算法的可行性。研究成果可为管理者实施治超站的选址决策和治超车的路径决策提供参考。

1 选址-路径模型

1.1 问题描述

在路网内，把有超载运输现象的路段(即超载路段)离散为点，并将这些点组成治超需求点集合。为实施移动治超，每个治超站都需配备相同车型的治超车。治超车携带称重设备从治超站出发，行驶到治超需求点，对经过的货车进行超载检测。巡游过程中，治超车在各需求点的检测时间固定，每辆治超车能够巡游的最大时间固定，且每辆治超车都需返回治超站，形成闭合的巡游路径。治超车的巡游过程如图1。

图1 治超车巡游过程示意

研究的问题是在路网形态、治超需求点集合和候选治超站集合已知的情况下，以最少的成本使治超车能检测到所有的治超需求点为目的，优化治超站的选址和治超车的路径。

1.2 模型建立

1.2.1 变量及参数设置

1)集 合

J为治超站候选点集合；I为需求点集合；K为移动治超车集合。

2)已知参数

cj为治超站建设成本；ck为治超车购置成本；cl为治超车巡游成本；cp为人工成本；v为治超车的行驶速度；t为治超车在需求点的固定检测时间；tmax为治超车每次能够巡游的最长时间；lii′为任意两个点之间的距离；n为每辆治超车需配备的移动治超人员数量。

3)中间变量

D为治超车巡游路径上的需求点数量；pk是为治超车k配备的移动治超人员数量。

4)决策变量

zj为在候选治超站j设置治超站时为1，反之，为0；zk为选择治超车辆k进行检测工作时为1，反之，为0；xii′k为治超车辆k从i到i′时为1，反之，为0。

1.2.2 模 型

(1)

S.T.：zj∈(0,1),j∈J

zk∈(0,1),k∈K

xii′k∈(0,1),i∈I∪J,i′∈I∪J,k∈K

(2)

(3)

(4)

(5)

(6)

pk=n·zk,k∈K

(7)

式中：C为治超成本。

式(1)为目标函数，表示治超成本最低；式(2)可保证治超车的巡游路径是闭合的；式(3)可保证每个需求点都只能被一辆治超车访问；式(4)可保证治超车从治超站出发，最终返回到同一个治超站；式(5)表示只要存在治超车从某个候选治超站出发到任意需求点，则在该候选点设置治超站；式(6)可确保每辆治超车的巡游时间不大于其最大巡游时间；式(7)表示治超车配备的移动治超人员人数。

2 模型求解算法

选址-路径问题(LRP)属于NP-hard难题，通常需要用启发式算法求解[15]。而蚁群算法作为一种概率型启发式算法，经常与枚举法相结合来求解LRP问题。然而，当选址候选集规模巨大而最大可设置设施数不确定时，潜在选址集合数会发生组合性爆炸，用蚁群算法虽可快速求出某选址集合下的最优解，但用枚举法针对组合性爆炸的集合逐个求解选址组合和车辆巡游方案，再从最优方案集中筛选成本最小的方案是不现实的。

图2 二级嵌套蚁群算法流程

2.1 蚁群参数设计

蚂蚁从巢穴(初始点)出发寻找食物时，在路径上播撒信息素，信息素随时间的推移会逐渐挥发。在行进过程中，蚂蚁依据路径上的信息素浓度选择路线，信息素浓度越大的路径被选择的概率越大；反之，概率越小[16]。基于此原理，笔者设计了二级嵌套蚁群算法中的蚂蚁转移规则和信息素更新规则。

2.1.1 蚂蚁转移规则

蚁群算法中，蚂蚁的转移与节点间的信息素浓度和期望有关，对于节点i来说，蚂蚁选择节点j的概率按式(8)计算：

(8)

式中：τij为路线ij的信息素浓度；ηij为路线ij的期望；α、β分别为信息素浓度和期望的启发式因子；S为可行的节点集合。

选址优化中，假设a、b为任意2个选址候选点，路线ab的选择期望ηab的确定过程如下：

1)基于治超车的最大可能巡游时间，计算各候选点能覆盖的需求点集合，并定义为覆盖范围。

2)根据式(9)，用相似度表示候选点间重复覆盖范围的大小：

(9)

式中：Sab为当前候选点a与其他候选点b的相似度；Lab为当前候选点a与其他候选点b重复检测到的需求点个数；La为当前候选点a检测到的治超需求点个数。

3)把期望ηab定义为候选点之间相似度的倒数，如式(10)：

(10)

2.1.2 信息素更新规则

当蚂蚁完成一次搜索后，采用式(11)的信息素更新方法对节点间的信息素进行更新：

(11)

选址优化信息素增量Δτe1和路径优化中信息素增量Δτe2分别按式(12)、式(13)计算：

(12)

(13)

式中：E1、E2分别为选址优化、路径优化中的蚂蚁集合；e1、e2分别为选址优化、路径优化中的任意一只蚂蚁；Q1、Q2分别为选址优化、路径优化中的信息素总量；Ce1为第e1只蚂蚁所对应的治超站建设成本和针对第e1只蚂蚁所选择的治超站而优化得到的最小移动治超成本之和；Le2为第e2只蚂蚁的路径长度。

2.2 算法步骤

Step1：输入治超站候选点的总数M、治超需求点的总数N、每辆治超车最大可能的巡游时间tmax、各点之间的距离矩阵B。

Step3：采用一级蚁群算法优化选址。

1)设蚂蚁数为M，并将蚂蚁编号为1,2,3,…,M。候选点间的初始信息素设为1，选择期望按式(9)计算。每只蚂蚁随机选择一个候选点开始构造路径。

2)按式(8)计算每个候选点的选择概率。为避免陷入局部最优，用轮盘赌选择法增加选择候选点的随机性[17]。具体过程为：取随机数ε,ε∈(0,1)，按候选点编号顺序依次累加可行候选点的选择概率pab，当∑pab≥ε时，选择编号最大的候选点作为蚂蚁的下一节点。当蚂蚁路径上的候选点数量等于H时，转到3)。

3)m为一级蚁群中蚂蚁的编号，设m=1。

Step4：对蚂蚁m选择到的治超站进行路径优化。如果选择到的治超站的数量大于1，则将多治超站的车辆路径问题转化为单治超站的车辆路径问题，即用一个虚拟治超站代替所有选择的治超站[18]。

1)假设所有治超车都以虚拟治超站为起讫点，治超需求点i与虚拟治超站之间的距离用治超需求点i到最近的治超站的距离di表示。

2)设二级蚁群算法中的蚂蚁数为N，治超需求点间的初始信息素为1，治超需求点和虚拟治超站间的初始信息素也设为1。

3)蚂蚁从虚拟治超站出发，按式(8)和轮盘赌选择法选择下一节点。假设选择到的第1个节点为需求点i′，距离i′最近的一个治超站为o。

4)对于蚂蚁的巡游时间t及最大巡游时间tmax，要使得t≯tmax，需约束巡游时间：如果蚂蚁在节点i选择到的下一点为j，设蚂蚁从o点到j点的巡游时间为to→j。判断to→j+bjo/v与tmax的大小，其中bjo/v表示蚂蚁从j点到o点的时间，当to→j+bjo/v≤tmax时，则把j纳入到蚂蚁的行程中，蚂蚁继续按照4)选择下一点；当to→j+bjo/v>tmax时，则放弃j点，蚂蚁从当前节点返回到治超站o，同时设蚂蚁的巡游时间t=0，返回3)。

3 案例分析

笔者调查得到贵阳市农村公路有63条超载严重的路段，把这些路段离散成63个治超需求点，并设定为治超站选址候选点集合，其空间分布如图3。

图3 贵阳农村公路网与治超需求点的空间分布

设每辆治超车需配备3名工作人员，走行速度为40 km/h，在1个治超需求点停车检测需0.5 h，每辆治超车的最大可能巡游时间为5 h。每个治超站建设的固定成本为250万元，使用年限为10年，则每年每个治超站的折旧成本为25万元；每年每人的人工成本为4.8万元；治超车按每辆10万元购置，使用年限为10年，则每年每辆治超车的折旧成本为1万元；每公里每辆治超车的燃油成本为1元，按每辆治超车每年需移动治超120次的标准，则每年每辆治超车每公里的燃油成本为120元。

根据图3的农村路网数据(包括交叉点、路段等数据)，先使用最短路算法(Floyd算法)计算治超需求点的距离矩阵，再将治超需求点的距离矩阵和治超车数量等参数输入到蚁群算法中，优化治超站的选址和治超车的路径。

图4为当治超站从1个增加到8个时，最优路径的信息素增量随迭代次数的变化关系。

图4 路径优化中的信息素增量-迭代次数关系

由图4可知：不同治超站数量下的信息素增量均随迭代次数的增加而增加，但增速逐渐减小直至收敛，表明对应不同的治超站数量都有一个最少的治超成本。当设置4个治超站时，信息素增量的收敛值是8种情况中的最大值，表明此时的治超成本最小。

表1为设置1 ～ 8个治超站时所对应的选址组合、治超车数和每年的治超成本。

表1 建设不同数量的治超站时的治超指标

从表1可知，设置4个治超站时，选址点分别设在24、28、45和54号点。各治超车的巡游路径如图5(闭合黑折线表示1辆治超车的巡游路径)，这些巡游路径经过多条省县级农村公路。

图5 选址-路径方案

由图5可见，4个治超站共需购置12辆治超车，其中，45和54号治超站分别拥有3辆，24号治超站拥有2辆，28号治超站拥有4辆。24、28、45和54号治超站分别位于花溪区的孟关乡、息烽县青山乡、乌当区羊昌镇、清镇市卫城镇。这些治超站周边矿产资源丰富、施工现场密集，运矿卡车和渣土车等大型车多超载运输，治超站的设置对途经的运输车辆进行超载检测，可对周围路段上的运输车辆起到威慑作用。

以54号治超站为例，治超车巡游路径的沿线情况如图6。由图6可以看出，3辆治超车的巡游路径上有：犁倭镇、流长乡、王庄乡、卫城镇、站街镇、谷堡镇、麦格乡、百花湖乡、清镇市9个城镇和红枫湖等的3个风景区，以及多个煤矿开采地。主要覆盖的道路有S310、S106、S211、S210等4条连接城镇的省级公路，道路等级较高，货车流量大，以及X068、X198、X063、Y012、Y020等多条县乡级农村公路。这些路段周边矿产资源丰富，运矿卡车超载现象严重。

图6 巡游路径的沿线情况

表1中8个选址方案的治超车工作效率W和利用率U可分别用式(14)、式(15)来表示：

(14)

(15)

式中：N为需求点数；tk为治超车k的实际巡游时间；K为所有治超站配备的治超车集合；tmax为每辆治超车最大能够的巡游时间。

设置1～8个治超站时，最佳选址方案下的治超车工作效率和利用率的对比如图7。可以看出，治超车工作效率随治超站的增加而增加，且上升趋势逐渐平缓。治超站从1个增加到4个时，治超效率上升显著，说明该阶段治超效率随治超站的增加而明显提高。治超站从4个增加到8个时，治超效率变化不明显，此时虽然治超站数多，但治超车工作效率并未明显改变。与治超效率不同，治超车的利用率在治超站数量从1个增加到4个时，呈上升趋势，并在4个时达到最大值，为94.83%。但治超站数量从4个增加到8个时，治超车利用率明显下降。

图7 不同数量治超站治超车的工作效率和利用率

综上，当分别在24、28、45和54号点设置治超站时，按照图5的巡游方案，所有超载点都可被检测到，且治超成本最低，此时得到的治超站选址、治超车配备和巡游路径是最优的，由图7可知最优方案下的治超车的利用率最高。

4 结 语

针对以治超站为基地实施农村公路移动治超的工作模式，在治超站候选点集合规模巨大和最大设置数量不确定的情况下，以治超成本最小为目标，以治超车巡游时间不大于最大巡游时间和所有超载点都被检测到为约束条件，建立治超站选址-治超车路径优化模型，并设计二级嵌套蚁群搜索算法求解。

基于贵阳市农村公路实际数据的研究表明，在优化的治超站选址-治超车路径方案下，治超站被选在矿产资源丰富、施工场地密集的地区，周边矿运货车和渣土车的超载现象明显，治超站的设置不仅可对途经的货车进行超载检测，对周围路段上的货车也起到了威慑作用。治超车的巡游路线包含多条省县干道，货车流量大，保证治超车可以有效拦截货车，而且治超车的利用率为94.83%，达到最高，工作效率为1.107，治超车工作效率较好。结果表明：笔者提出的模型和算法能有效帮助决策者科学合理地进行治超站选址决策和治超车路径选择决策。

值得说明的是，笔者未考虑治超需求点的运输车流量随时间的分布情况，优化的结果中缺少治超车的出发时间。为使治超车在巡游时间内能更多的截获到运输车辆，在治超车路径优化的后续研究中，有必要考虑治超需求点处交通流在时间上的分布特征，根据不同时段的流量情况，优化治超车的出发时间和巡游路径。