摘要
带容量约束的车辆路径问题是一个NP-hard问题。针对此问题将蒙特卡洛模拟方法与流行的节省算法结合。提出Flag-MCS-CWS算法,该方法通过对CWS算法得到的节省序列进行蒙特卡洛模拟,适用于不同节点数、不同车辆载重量的车辆路径问题。在标准数据集测试,相比当前最优解有平均0.75%的改进,为车辆路径问题提供了更加有效的解决方案。
Flag-MCS-CWS algorithm combined MCS with CWS was proposed for the capacitated vehicle routing problem, which is an NP-hard problem. The saving list of CWS algorithm was simulated by monte carlo algorithm, which avoids gaining the local optimum and globally solve the problem. The algorithm is appropriate for VRP prob- lem with different node number and different vehicle capacity. As can be seen from results, the new algorithm can improve the optimal solution on standard test set averagely by 0.75% and the new algorithm provided feasible solu- tions for capacitated vehicle routing problems.
出处
《科学技术与工程》
北大核心
2012年第26期6849-6852,共4页
Science Technology and Engineering
基金
西北农林科技大学2010年科技创新项目(2010信息014号)
留学回国人员科研启动费项目(2009信息01号)资助
