求解两级定位-路径问题的粒子群算法

为求解配送网络中的两级定位-路径问题，提出一种在粒子更新过程中融入路径重连启发式搜索策略的粒子群算法。其中，根据两级定位-路径问题中解的属性，提出以中转站、路径、边为对象的三个路径重连搜索模块；同时基于搜索模块的不同组合，提出四种路径重连策略。应用不同规模算例测试结果表明，该粒子群算法能有效求解两级定位-路径问题，且路径重连策略一的求解效率较高，策略二求解的稳定性较好，策略三求解时各方面均无突出表现，策略四求解时解的质量较高。

Particle swarm optimization for two-echelon location-routing problem

In order to solve two-echelon location-routing problem of distribution network, particle swarm optimization with path relinking integrated into particle update process was proposed. Three path relinking search modules with regarding transfer station, path and edge as the object were put forward according to the attributes of the solution of two-echelon location-routing problem. At the same time, on the basis of the different combinations of these search modules, four kinds of path relinking strategy were put forward. The test results on different scale examples show that the particle swarm optimization can solve two-echelon location-routing problem effectively, the first path relinking strategy has higher efficiency. The second one has higher stability, the third one has no obvious performance in every aspect, and the fourth one has higher quality solution. Key words: two-echelon location - routing problem; particle swarm optimization; path relinking; distribution