对共享单车的改进措施(大规模单车场VRP问题中扫描法的改进)
随着物流业的发展，车辆路径问题越来越值得研究。吉列和米勒在1974年提出了扫描法，这种方法很容易应用于解决VRP问题。4].本文借鉴了VRP多车场分区方法等问题的研究成果[5？[11]针对对大型单体停车场的VRP问题，提出了圆形分区的思想，并在此基础上对扫描方法进行了改进。最后，用Matlab编程，并给出了一个实例。结果表明，本文提出的圆形扫描方法在距离和车辆使用方面都优于传统扫描方法。1 VRP在单个院子里的描述和模型
1.1问题被提出。一个油库建在一个石油生产厂下面，里面有足够的相同型号的车辆。每个井点都有自己的每日石油产量。井点和停车场在平面图上的坐标和实际行驶距离是已知的。日常操作是车辆从车辆段出发，按规定到每个井点加油，当车辆剩余载重量不能满足下一个井点时返回车辆段，要求每个井点每天仅用一辆车完成一次输出。什么样的车辆调度方案能够满足问题条件并使总距离最小。该问题是一个具有容量约束的VRP问题，总距离是目标函数。
1.2型号n的建立：井点；号
[qi，i1，2，…，n]:井点；的日产油量[Q]:车辆的额定容量；
[dij，I，j1，2，…，n 1]:井点；之间的实际行驶距离[xijm=1，车辆m从节点I行驶到节点j0，否则，I，j=1，2，N 1]
[MinZ=MMin 1Jn 1ijm](1)[j=1N 1m=1MXijm=1，i1，2，…，N 1] (2)
[i=1N 1m=1Mxijm=1，j1，2，…，N 1] (3)[i=1N 1qij=1N 1xijmQ，m1，2，…，M] (4)
公式(1)表示一天配送的总路线，它是目标函数。等式(2)和(3)确保每个用户只能由一辆汽车服务一次。等式(4)表示车辆的容量限制。2扫描方法
2.1在传统的扫描法求解过程中，从车场向任意方向引入一条光线，顺时针或逆时针旋转，扫描点依次加入到路径中，直到增加某一点时货物量超过车辆量，然后剔除该点，得到一个分组，确定一条路径，新路径不断旋转，直到所有点都分组排列在路径中，其结果通常作为一组可行的初始解，然后结合其他算法进行优化。
2.2改进的圆形扫描法的基本思想圆形扫描法是在传统扫描法的基础上改进的启发式算法，主要分为两个步骤：分割和扫描。首先，在对，的井点所覆盖的区域中找到合适的中心点和半径向量，并将其分成一些环形区域。在此基础上，根据传统扫描方法的原理对区域进行扫描，最终优化初始解。
2.3改进的循环扫描方法的实现过程2.3.1分区数量
划分适当数量的区域并选择适当的环宽非常重要。假设环区域划分后的扫描组在接近正方形时最理想，车辆通行能力约束下的正方形边长计算为“理想环宽”。如果井点的面积是南，那么每个井点的平均面积是[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) (2)当整个区域的水平和垂直坐标范围相差较大，大致为“矩形”时，将“惠”的圆形区域进行划分，以停车场的位置为坐标原点，建立合适方向的坐标轴，分别考虑值和Y值，如图3所示。假设半径矢量为[xa，ya，xb，yb]，则该区域分为：
第一个区域：[(x，y)x-xa，xa，y-ya，ya]
二区：[(x，y)x-XB，-xa？xa，xb？你好，是吗？ya，yb]
图3。2.3.3用循环划分的方法分组形成子路径
以车场为中心，在每个区域选择相同的起始方向，分别使用传统的扫描方式，以扫描顺序作为每组井点的初始解。由于最后一组所有区域几乎没有充分利用车辆的通行能力，最后一组所有区域合并为一个区域，以车场半径为圆心，按升序扫描各组。2.3.4优化子路径
Matlab编程是用来保存算法或WinQSB的最便宜的插入启发式函数。将对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]；第五组也分成两个区域，划分向量是[(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问题，通过本文提出的改进扫描得到的分组更加集中，易于管理；提高了两阶段优化路径目标的效果，增加了每辆车服务的节点数量，提高了平均负载率，总距离明显减小；同时，区域被环或环分割后，扫描宽度减小，更便于手工计算扫描方式。实例表明，合理的分区数和分区方法是循环扫描法的关键。第四组、第五组和第六组示例表明，在分区数量和分区边界选择方面仍有很大的研究空间。
黑曼巴 