求解大规模CVRP的有效方法及电子设备

摘要

本发明涉及车辆路由技术领域，具体涉及一种求解大规模CVRP的有效方法及电子设备，包括步骤S1设置最大迭代次数MaxIter、最大无进展迭代数MaxIterNoImp；S2生成初始解sol；进而i←0，noimpr←0；sol′←sol；S3使用路径切割方法SR对sol′中的路径进行切割，得到路径集合RtSt；S4使用层次分解策略HD对RtSt分解，获得包含所有客户的虚拟客户VC，分割VC得到满足车辆载重约束的解sol″；S5对sol″实施VNS邻域搜索；若sol″对应总行车距离少于sol，则进行替换，sol←sol″，noimp←0；否则置noimp←noimp+1；S9执行i←i+1；当i≤MaxIter且noimp≤MaxIterNoImp时，则转S2进行后续迭代过程，否则则结束，返回sol，本发明所设计的算法在较多算例上更新了问题的最优解，尤其在大规模测试集Li上，表现出色。