RSB-CWS算法解决CVRP问题

摘要

RSB-CWS algorithm combined MCS with CWS was proposed for the capacitated vehicle routing problem, it employ MCS algorithm to simulate the edges between customers of CWS algorithm, during the simulation, a quasi-geometric distribution is used to do the edge sampling. Apply CWS algorithm on the new edge sequences and get equal or better solutions. Compared to other CVRP algorithms, RSB-CWS algorithm is more efficent and getting better solutions, at the same time, RSB-CWS algorithm can also solve larger CVRP problem easily.%RSB-CWS算法结合了蒙特卡洛模拟和CWS节省算法,利用蒙特卡洛模拟对CWS算法节省列表中顾客对间的边进行模拟,模拟过程中采用基于类几何分布的直接抽样方法进行路径采样.对模拟得到的边序列应用CWS算法,所得解的质量能达到或者优于当前最优解与其他CVRP问题算法相比具有高效、高质量的特点,且可以解决规模较大的CVRP问题.