求解任务分配问题的一种离散微粒群算法

A discrete particle swarm optimization algorithm for task assignment problem

以交通运输领域中的装卸货任务分配问题为例对任务分配问题进行数学描述,提出一种用于求解该类问题的离散微粒群算法(DPSO)。在分析基本微粒群算法的收敛性能和任务分配问题解分布情况的基础上,采用惯性权值非线性下降策略更新微粒速度,以提高算法的收敛性,并且引入一个反正切函数对基本微粒群算法的位置公式进行进一步处理,以保证解的可行性。提出的DPSO用于求解某企业铁路货运站的装卸任务,在相同实验条件下,求解同一任务分配问题,提出的改进DPSO寻优率为76%,明显高于寻优率仅为40%和4%的其他2种DPSO算法;不同规模问题的求解试验中,综合比较寻优结果和计算时间,所提DPSO算法优于枚举法和遗传算法,且计算简便,可推广用于其他任务分配问题与组合优化问题。

Mathematical description of task assignment problem was given by describing the pickup and delivery task assignment problem in transportation, and a discrete particle swarm optimization algorithm （DPSO） for solving the above problem was proposed. Based on the analysis of convergence performance of standard PSO and distribution of solutions of the task assignment problem, the strategy of nonlinearly decreasing inertia weight was adopted in the velocity update formula to improve the convergence of the algorithm, and an arctangent function was introduced to further adjust the position formula to ensure the feasibility of solutions. The proposed DPSO was applied to the pickup and delivery task assignment in a railway freight station. Solving the same task assignment problem in the same experimental condition, the successful rate of the proposed DPSO is 76%, and is higher than those of the other two DPSO, which are only 40% and 4%. In the experiment of solving different scale problems, by comparing the optimization results and computing time, the proposed DPSO is superior to the enumeration method and genetic algorithm. The proposed algorithm is simple and feasible, and can be applied to solving other task assignment problems and combinational optimization problems.