Abstract: Considering both of  dispatching costs of vehicles and travelling costs of routes，a mixed integer mathematical formulation of the VRPSPD was established to make the total delivery costs，the number of vehicles and the travel costs minimize simultaneously. An adaptive parallel genetic algorithm was proposed for solving the VRPSPD. Inspired by the C-W saving algorithm，three heuristic methods with two kinds of demands for initializing population were presented to reduce the search scopes and optimize the initial solutions. A bi-group parallel strategy with diversity population and high quality population was proposed to realize the synchronous search of depth and breadth. The adaptive genetic operations of crossover and mutation were applied to improve the stagnation of the search in high quality population. And based on a kind of special mutation a post-optimization was carried out for the global best individuals to further improve the global optimal performance. The feasibility and effectiveness of the proposed algorithm were verified by two instances based on standard dataset.

Key words: vehicle routing problem with simultaneous pickup and delivery(VRPSPD), adaptive parallel genetic algorithm, bi-group parallel strategy, post-optimization

摘要： 为了同时实现总配送成本最低、车辆行驶距离最短、车辆数最小等目标，综合考虑车辆指派成本及运输路径成本，建立了装卸一体化车辆路径问题的混合整数规划模型。针对该问题搜索空间的离散性和求解算法的局部收敛性，提出了一种自适应并行遗传算法。算法以C-W节约法为基础,设计了三种基于双重需求的启发式种群初始化方法，缩小搜索空间并优化初始解；引入多样性种群和高质量种群的双种群并行策略，实现深度与广度的同步搜索；设计自适应交叉变异操作，改善高质量种群个体搜索停滞，并针对全局最优个体采用特殊变异的后优化操作以进一步提高全局优化性能。采用标准数据集作为算例进行寻优测试，验证了所提算法的可行性和有效性。

关键词: 装卸一体化车辆路径问题, 自适应并行遗传算法, 双种群并行策略, 后优化