A Hybrid Algorithm Based on Dynamic Programming Method and Discrete Particle Swarm Optimzation Algorithm for Fleet Planning

摘要

Solving fleet planning problem is very important for shipping enterprises. Some fleet planning models may result in non-integer vessel number of the fleet which does not agree with the fact. And there'll be error if shift the result into integer. And some multi-stage decision model of planning fleet is established on the basis of dynamic programming in view of system theory. The possible combinations of planning fleet are taken into account. But if the scale of fleet is large, solving "the curse of dimensionality" existed in general dynamic programming is time-consuming, even it is impossible to accomplish the computation;Particle swarm optimization is a kind of swarm intelligence method. The particle swarm optimization is an algorithm for searching the multidimensional complex space efficiently through cooperation and competition among the individual in a population of particles. Particle swarm optimization algorithm is easy to be implemented, possesses excellent performance an has a high convergence speed, but it is easy to fall into local optimization. In a word, due to the complexity of fleet planning problem, any method will be restricted. So aiming at the shortcoming of dynamic programming and particle swarm optimization, by reference to discrete differential dynamic programming, in this paper, we present a hybrid algorithm based on dynamic programming method and discrete particle swarm optimization algorithm. First, apply discrete particle swarm optimization algorithm to fleet planning and get the approximate optimal solution. Then regard this solution as primary optimal planning. Last based on "large vessel matching large line" principle, dynamic programming on the basis of using priority list to limit the combination states is applied to search the optimal solution. A new method based on the practical experience is developed in this paper is strict in strategy theory and requires short calculation time.