大规模单车场VRP问题中扫描法的改进

Improvement of sweep algorithm to deal with large-scale SVRP

为了降低问题规模,提高扫描法应用在单车场VRP问题中初始解的有效性,这里借鉴多车场VRP等问题中的分区思想,以车场为中心,根据需求点覆盖区域的特点,对单车场VRP提出了新的环形分区思想,并给出了几种具体方法。在此基础上,对扫描法进行改进,分区分别扫描并且集中车辆使用率低的区域重新扫描,合理地降低了大规模单车场VRP问题的复杂程度,为第二阶段的优化提供了有效的初始解。算例表明运用该算法比传统扫描法得到的路径更优且使用车辆数更少。

To improve the effectiveness of sweep algorithm’s initial solution in large？scale single？depot vehicle routing prob？lem（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.