混合粒子群优化算法求解多车辆拖动货物问题

Hybrid particle swarm optimization algorithm for multiple vehicle dragging goods problem

为确定码头上集装箱运输到目标位置的顺序和运输的车辆,提出了多车辆拖动货物问题,该问题需要考虑空间约束对车辆调度过程的影响。针对该问题,建立了整数规划数学模型,证明了该问题为NP完全难题,提出了四种解的编码方式,并利用模拟退火算法与粒子群优化算法结合的混合粒子群优化算法进行求解。将计算结果与模拟退火算法、粒子群优化算法进行了比较,结果表明,使用混合粒子群优化算法并采用先到先服务规则的两部分编码方法计算得到的解最好。

In order to determine sequences and vehicles of containers to their goal locations, multiple vehicle dragging goods problem was put forward. Influence of space constraint on vehicle scheduling process should be considered in this problem. Aiming at this problem, an integer programming model for the problem was established, and it was proved to be NP complete hard. To solve this problem, four kinds of coding methods were proposed. Hybrid particle swarm alogirthm was used to solve this problem by integrating simulated annealing algorithm with particle swarm algorithm. And the performance of the hybrid particle swarm algorithm was compared to the simulated annealing algorithm and the particle swarm algorithm. The computational results showed that the two chromosome representation using the first-come-first-served rule was more effective than other three representations in resolving the problem.