摘 要： 为了降低问题规模，提高扫描法应用在单车场VRP问题中初始解的有效性，这里借鉴多车场VRP等问题中的分区思想，以车场为中心，根据需求点覆盖区域的特点，对单车场VRP提出了新的环形分区思想，并给出了几种具体方法。在此基础上，对扫描法进行改进，分区分别扫描并且集中车辆使用率低的区域重新扫描，合理地降低了大规模单车场VRP问题的复杂程度，为第二阶段的优化提供了有效的初始解。算例表明运用该算法比传统扫描法得到的路径更优且使用车辆数更少。
关键词： 电子技术论文发表,车辆路径问题,扫描法,改进算法,单车场VRP,大规模单车场VRP
Improvement of sweep algorithm to deal with large?scale SVRP
WANG Shi?yao， WANG Wen?fa， FU Wen?jun， LI Xiao?ying
(School of Mathematics and Computer Science， Yan’an University， Yan’an 716000， China)
Abstract： To improve the effectiveness of sweep algorithm’s initial solution in large?scale single?depot vehicle routing problem (LSVRP) and reduce the scale of the problem， the partition thought of multiple?depot VRP (MDVRP) is employed in this paper. Centering on the yard， a new thought of an annular field partition is put forward according to the characteristics of the covered area at the demand points， and several concrete methods is given. Based on this， the sweep method was improved， that is， partition scan and rescan for the areas with low vehicle?usage rate. This method reduced the complexity of the LSVRP reasonably and provided the effective initial solution for the optimization in the second stage. Experiments show that the algorithm is better than traditional sweep algorithm in path selection and uses less number of vehicles.
Keywords： VRP; sweeping algorithm; improved algorithm; single?depot VRP; LSVRP
车辆路径问题(Vehicle Routing Problem，VRP)随着物流业的发展越来越值得研究。Gillett和Miller于1974年提出扫描法[1]，将其应用在求解VRP问题中简单易行，当节点规模较大时，运用传统扫描法得到的节点分组不利于第二阶段的路径优化 [2?4]。本文借鉴多车场VRP(Multiple depots VRP，MDVRP)等问题中的分区方法的研究成果[5?11]，提出一种针对大规模单车场VRP问题的环形分区思想，在此基础上改进了扫描法。最后运用 Matlab编程并带入算例，结果表明本文提出的环形扫描法比传统扫描法的路程和车辆使用情况更优。
1 单车场VRP的描述及模型
1.1 问题的提出
某采油厂下设一个车场，包含足够的车辆且型号相同，每个井点都有各自的日产油量，井点、车场在平面图上的坐标和实际行驶距离已知，日常运作为车辆从车场出发，沿规定去各个井点泵油，当车辆剩余载重量无法满足下一井点时返回车场。要求每个井点的产量一日内仅由一辆车一次完成。安排怎样的车辆调度方案，可满足问题条件且总路程最小。此问题即带容量约束的单车场集货VRP问题，总路程为目标函数。
1.2 模型的建立
N：井点个数;
[qi，i∈1，2，…，N]：井点日产油量;
[Q]：车辆的额定容量;
[dij，i，j∈1，2，…，N+1]：井点间的实际行驶距离;
[xijm=1，车辆m从节点i行驶到节点j0，否则， i，j=1，2，…，N+1]
[minZ=mMiN+1jN+1xijm] (1)
[j=1N+1m=1Mxijm=1，i∈1，2，…，N+1] (2) [i=1N+1m=1Mxijm=1，j∈1，2，…，N+1] (3)
[i=1N+1qij=1N+1xijm≤Q，m∈1，2，…，M] (4)
式(1)表示的是一日配送的总路径，为目标函数。式(2)、式(3)保证每个用户只能被一辆车服务一次。式(4)表示车辆的容量约束。
2 扫描法
2.1 传统扫描法
求解过程从车场所在点向任意方向引一条射线沿顺时针或逆时针方向旋转，将扫到的点按顺序加入到路径当中，直到加入某点时货物量超出车载量，则剔除此点得到一个分组并确定一条路线，继续旋转构造新的路径直到所有点都被分组并安排到路线中，结果通常被用作一组可行的初始解，再结合其他算法进行优化。
2.2 改进的环形扫描法基本思想
环形扫描法是在传统扫描法的基础上，一种改进的构造启发式算法，主要分两步：分区和扫描。首先对井点覆盖的区域找出合适的中心点和半径向量，将其划分为一些环形区域，在此基础上，以传统扫描法为原理分区扫描，最后优化初始解。
2.3 改进的环形扫描法实现过程
2.3.1 分区个数
划分合适的区域个数以及选择合适的环形宽度至关重要。假设划分环形区域之后扫描得到的分组接近正方形时最为理想，计算车容量约束下此正方形的边长即“理想环宽”。井点区域覆盖的面积为S，则平均每个井点占面积[s=SN]。平均井点产量为[qi]，平均每趟车包含x个井点，即[x=Qqi]。则理想分组下正方形边长[e=sx=SQNqi]，即“理想环宽”。
大多数情况下并不能根据理想环宽e刚好划分为整数个区域，可以根据井点、车场坐标和e共同决定划分几个区域，并适当调整实际每个环的宽度，实际环宽应大于等于e或不小于e太多。
2.3.2 几种环形分区方法举例(以分两区为例)
(1) 当整个区域接近圆形时，根据理想环宽设计合适的半径向量(a，b)划分圆环形区域。圆心为P半径为a的圆及其内部为第一区域，内圆为a外圆为b的环为第二区域，如图1所示。
当井点覆盖的区域横纵坐标范围差距较大时，运用这种方法不能达到理想的分区效果，如图2所示。此时如果将横纵坐标调整比例伸缩为圆形，虽然可以使用方法(1)但会影响到目标函数值。
图1 环形分区(一)
图2 环形分区(二)
(2) 当整个区域横纵坐标范围差距较大且大致呈“矩形”时，划分“回”字环形区域，以车场所在点作为坐标原点，合适的方向建立坐标轴，将x、y值分别考虑，见图3。设半径向量为[xa，ya，xb，yb]，则区域划分为：
一区：
[(x，y)x∈-xa，xa，y∈-ya，ya]
二区：
[(x，y)x∈-xb，-xa?xa，xb?y∈-yb，-ya?ya，yb]
图3 回形分区法
2.3.3 分组并形成子路径
以车场为中心，分别在每个区域中选择相同的起始方向，分别运用传统扫描法，以扫描到的顺序为每组井点的初始解。因为所有区域的最后一个分组几乎都没有完全利用车载量，因此将所有区域的最后一个分组合并为一个区域，并以车场为圆心半径升序扫描分组。
2.3.4 优化子路径
运用Matlab编程使用节约算法或WinQSB的Cheapest insertion heuristic功能，对2.3.2节得到的每组结果加入车场点，以路程为目标进行优化。
3 算法仿真对比
以陕北地区某单车场采油厂的泵油作业为例，包含200个井点，车型相同载重量均为20 t。车场为坐标原点，井点的位置和产油量如表1所示。
表1 各井点位置与产量信息
运用传统扫描法和改进的环形扫描法对算例进行测试。根据计算理想环宽，本例最多可分三区。前三组传统扫描法选择不同的扫描起始点;根据井点分布，后三组改进的环形扫描法都采用“回”字分区：第四组分两区，分区向量为：
[(0.5rx，0.5ry)，(rx，ry)=6，13.5，12，27]
式中[rx]，[ry]为所有井点x，y方向上到车场的最远距离，即[rx=maxxi=13，ry=maxyi=27，i=1，2，…，N];第5组也分两区，分区向量为：
[(lx，ly)，(rx，ry)=5.7，11，12，27]
式中[lx]，[ly]为所有井点x，y方向上到车场的距离均值，即：
[lx=avexi=5.7， ly=aveyi=11， i=1，2，…，N]
第六组分三区，分区向量为：
[(13rx，13ry)，(23rx，23ry)，(rx，ry)=4，9，(8，18)，12，27]
六组算例结果如表2所示。算例结果表明，针对本文测试的数据，三组传统扫描法的平均总路程为1 161.5，采用本文思想的环形分区扫描法的结果中，第一组分区法的总路程最优为1 097.7，使用车辆数也最少，与传统扫描法相比平均节约路程(1 161.5-
[1 018.4)1 161.5]=12.3%。其他两组改进扫描法的结果在车辆和总路程上也较传统扫描法有所改进。
表2 改进扫描法与传统扫描法结果对比
4 结 论
对于大规模单车场VRP问题，本文提出的改进扫描得到的分组更集中便于管理;并且提高了二阶段优化路径目标的效果，使用车辆减少，平均每辆车服务的节点数增加，平均载重率提高，总路程明显减少;同时，以环形或回型划分区域之后，扫描宽度减小，更加便于扫描法的人工计算。算例表明，合适的分区个数和分区方法是环形扫描法的关键。第四、五、六组算例表明在分区的个数和分区界限选取上还有很大的研究空间。 参考文献
[1] GILLET B E， MILLER L R. A heuristic algorithm for the vehicle dispatch problem [J]. Operations Research， 1974， 22： 340?349.
[2] WREN A. Computers in transport planning and operation [M]. London： Ian Allan， 1971.
[3] WREN A， HOLLIDAY A. Computer scheduling of vehicles from one or more depots to a number of delivery points [J]. Operational Research， 1972， 23： 333?344.
[4] RENAUD J， BOCTOR F F. A sweep?based algorithm for the fleet size and mix vehicle routing problem [J]. European Journal of Operational Research， 2002， 140： 618?628.
[5] 曹二保，赖明勇，聂凯，等.大规模物流配送车辆调度问题研究[J].湖南大学学报：自然科学版，2007(12)：94?97.
