物料配送和废旧产品回收的VRPSDP问题的并行模拟退火算法

A parallel-simulated annealing algorithm for solving VRPSDP oriented to material delivery and used products pickup

为了求解面向制造领域物料配送和废旧产品回收的同时送取货的车辆路径优化问题（VRPSDP），提出一种主从式并行模拟退火算法代替传统的串行模拟退火算法．算法首先使用剩余承载力和径向附加费（RCRS）算法求得初始解，然后在并行模拟退火算法框架下使用4种邻域搜索方法对初始解进行优化．最后，选取国际上通用的Montane和Galvao测试数据集（18个顾客数为100～400的测试问题）对算法性能进行测试，与文献中其他5种算法的比较显示，提出的并行模拟退火算法总体性能较优．

To solve the vehicle routing problem with simultaneous delivery and pickup （VRPSDP） ori- ented to material delivery and used products pickup in the field of manufacture, a master-and-slave par- allel simulated annealing （par-SA） algorithm is presented to replace the traditional sequential SA. Residual capacity and radial surcharge （RCRS） heuristic is implemented for generating an initial solu- tion, and four kinds of local search moves within the structure of par-SA is developed to optimize the initial solution. Computational results are reported for 18 test problems with 100-400 customers from Montane and Galvao＇ s benchmark. Compared with the results of 5 other algorithms in the literature, it is shown that the overall performance of par-SA is competitive with the others.