Abstract: Vehicle Routing Problem with Simultaneous Delivery and Pickup（VRPSDP） is a very complex NP complete problem.To solve this problem，this paper designs an Improved Simulated Annealing Genetic Algorithm（ISAGA），the use of non-zero natural number coding mechanism and the weak feasible solution to strong feasible solution decoding mechanism.With 3PM crossover operator and to choose the combination of annealing to form 3PM greedy crossover operator，the introduction of insert，swap and 2-opt mutation operator are successively used，while simulated annealing algorithm and genetic algorithm clever combination of genetic algorithm in the pre-made play a powerful global search function；the latter using simulated annealing algorithm to deal with the pre-genetic algorithm overall than the solution，make full use of simulated annealing algorithm the latter the power of local search.After the internationally recognized test numerical example，ISAGA algorithm Min example，Salhi and Nagy examples are found in the algorithm than the existing best solution known better solution.

Key words: Vehicle Routing Problem with Simultaneous Delivery and Pickup（VRPSDP）, genetic algorithms, simulated annealing, greed 3PM cross-operator, annealing choice

摘要： 配送和回收一体化的车辆路径问题（VRPSDP）是一种非常复杂的NP难题。针对这一问题，设计了一种改进的模拟退火遗传算法ISAGA，采用非零自然数编码机制和弱可行解到强可行解的解码机制，将3PM交叉算子和退火选择相结合，形成贪心3PM交叉算子，引进insert 、swap和2-opt分别对解进行迭代优化，并将模拟退火算法和遗传算法巧妙地结合，使得遗传算法在前期发挥着全局搜索的强大功能；后期用模拟退火算法来处理遗传算法前期的全局较优解，充分利用模拟退火算法后期局部搜索的强大功能。经过国际公认的测试算例验证，ISAGA算法在Min算例、Salhi和Nagy算例中均找到了比现有算法已知最好解更优的解。

关键词: 配送和回收一体化的车辆路径问题, 遗传算法, 模拟退火算法, 贪心3PM交叉算子, 退火选择