大规模单车场VRP问题中扫描法的改进-精选文档.docx

大规模单车场VRP问题中扫描法的改进摘要：为了降低问题规模，提高扫描法应用在单车场VRP问题中初始解的有效性，这里借鉴多车场VRP等问题中的分 区思想，以车场为中心，根据需求点覆盖区域的特点，对单车场VRP提出了新的环形分区思想，并给出了几种具体方法。在此基础上，对扫描法进行改进，分区分别扫描并且集中车辆使用率低的区域重新扫 描，合理地降低了大规模单车场VRP问题的复杂程度，为第二阶段的优化提供了有效的初始解。扫 算例表明运用该算法比传统描 法得到的路径更优且使用车辆数更少。Improvement of sweep algorithm to deal with large?scale SVRPWANGShi?yao , WANGWen?fa, FU Wen?jun, LI Xiao?yingSchool of Mathematics and Computer Science , Yan, anUniversity , Yan，an 716000 , China ):To improve the effectiveness of sweep algorithm ' s initial solution in large?scale single?depot vehicle routing problem ( LSV R P) and reduce the scale of the problem , the partition thought of multiple?depot VRPMDVR)P 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 thedemand 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于1 974年提出扫描法1,将其应用在求解VRP问题中简单易行，当节点规模较大时，运用传统扫描法得到的节点分组不利于第二阶段的路径优化 2?4 o 本文借鉴多车场 VRP( Multiple depots VRP, MDVRP等问题中的分区方法的研究成果：5?11,提出一种针对大规模单车场VRP问题的 环形分区思想，在此基础上改进了扫描法。最后 运用Mat lab编程 并带入算 例，结果表明本文提出的环形扫描法比传统扫描法的路程和车辆使用情况更优。1单车场VRP的描述及模型1. 1问题的提出某采油厂下设一个车场，包含足够的车辆且型号相同，每个 井点都有 各自 的日产油量，井点、车场在平面图上的坐标和实际行驶距离已知，日常运作为车辆 从车场出发，沿规定去各个井点泵油，当车辆剩余载重量无法满足下一井点时返回 车场。要求每 个井点的产量一日内仅由一辆车一次完成。安排怎样的车辆调度 方 案，可满足问题条件且总路程最小。此问题即带容量约束的单车场集货VRP问 题，总路程为目标函数。1. 2模型的建立N：井点个数；qi , i 1, 2, , N：井点日产油量;Q:车辆的额定容量；dij , i , j 1, 2, - N+1：井点间的实际行驶距离;xijm=l,车辆m从节点i行驶到节点jO ,否则，i , M , 2,N+1minZ=mMiN+ljN+lxijm，j 二 IN+Im 二 IMxijm 二 1 , i 1, 2,，N+1 (2)i=lN+lm=lMxijm=l , j 1, 2,，N+1(3)_i 二 IN+lqi j=lN+l xi jm <Q me 1, 2, 一，M (4)式(1)表示的是一日配送的总路径，为目标函数。式、式(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值分别考虑，见图3o设半径向量为xa , ya, xb, yb,则区域划分为：一区：_ （x, y）xe -xa , xa, ye -ya , ya.二区：_ （x, y）xe -xb , -xa?xa , xb?ye -yb , -ya?ya , yb.图3回形分区法2. 3. 3分组并形成子路径以车场为中心，分别在每个区域中选择相同的起始方向，分别运用传统扫描法，以扫描到的顺序为每组井点的初始解。因为所有区域的最后一个分组几乎都没有完全利用车载量，因此将所有区域的最后一个分组合并为一个区域，并以车场为圆心半径升序扫描分组。2. 3. 4优化子路径Win QSB 的 Chea pest节得到的每组结果加入车运用Mat lab编程使用节约算法或 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=l , 2 ,N；第 5 组也分两 区，分区向量为:.(lx , ly ) , rx , ry )=5. 7, 11, 12, 27：式中lx , ly为所有井点X, y方向上到车场的距离均值，即：lx=avexi=5 , 7 ly=aveyi=lli=l , 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问题，本文提出的改进扫描得到的分 组更集中便于管理； 并且提高了二阶段优化路径目标的效果，使用车辆减少，平均每辆 车服务的节点数增加，平均载重率提高，总路程明显减少；同时，以环形或回型划 分区域之后，扫描宽度减小，更加便于扫描法的人工计算。算例表明，合适的分 区个数和分区方法是环形扫描法的关键。第四、五、六组算例表明在分区的个数 和分区界限选取上还有很大的研究空间。