Computer Engineering and Applications ›› 2014, Vol. 50 ›› Issue (6): 226-229.

Previous Articles     Next Articles

Study on Vehicle Scheduling Problem with Time Windows based on Improved Particle Swarm Optimization

WANG Fei   

  1. School of Computer Science, Gansu Institute of Political Science and Law, Lanzhou 730070, China
  • Online:2014-03-15 Published:2015-05-12


王  飞   

  1. 甘肃政法学院 计算机科学学院,兰州 730070

Abstract: Vehicle Scheduling Problem with Time Windows(VSPTW) is a typical Non-deterministic Polynomial hard(NP-hard) optimization problem. To overcome the shortcomings such as premature convergence and fall into local optimal, an Improved Particle Swarm Optimization(IPSO) algorithm is put forward. In the algorithm, the adaptive mutation based on t distribution on the basis of the inertia weight decreasing is used to make the algorithm jump out of local convergence. The algorithm is applied to VSPTW. The mathematical model is established and the detailed implementation process of the algorithm is introduced. The simulation results show that the algorithm is valid and feasible to solve VSPTW.

Key words: Vehicle Scheduling Problem with Time Windows(VSPTW), NP problem, Particle Swarm Optimization(PSO), [t] distribution

摘要: 带时间窗车辆调度问题是一类典型的NP难解问题。为了克服标准粒子群算法存在早熟收敛和易陷入局部解等问题,提出了一种改进的粒子群优化算法。该算法在惯性权重递减的基础上通过群体极值进行[t]分布变异,使算法跳出局部收敛,将该算法应用于带时间窗的车辆调度问题优化。算例证明了改进粒子群算法应用于求解带时间窗的车辆调度问题的可行性和有效性。

关键词: 带时间窗车辆调度问题, NP问题, 粒子群优化算法, [t]分布