摘要
任务分配问题是运筹学中的一类规划问题,求解这类问题的比较经典的算法是匈牙利算法,但匈牙利算法在求解大规模任务分配时运算效率不高。文章提出了一种新的求解任务分配问题的方法——剪枝优化算法。算法通过逐步剔除已确定的部分分配方案对应代价矩阵元素,逐次降低分配问题的规模,从而实现快速求解全局任务分配问题。对于n个主体执行n个任务的分配问题,进行(n-1)次操作就可以获得最优解。论文进行了相应的仿真,将文章提出的算法和匈牙利算法做了比较。仿真结果表明,该算法与传统匈牙利算法计算结果一致,但计算耗时远远小于匈牙利算法,即该算法大大提高了任务分配问题的求解速度。
To our knowledge, the Hungary algorithm is not satisfactory for solving a large scale task assignment problem in the fields of operation research because it requires several changes in cost matrix and seeks, selects and deletes the labels of a zero element. Hence, we propose what we believe to be a faster pruning optimization algo- rithm to solve the problem. We reduce the task assignment scale by pruning the elements relative to the partial opti- mal resolution in each operation; the pruning optimization algorithm can thus obtain the optimal solution with only （ n - 1 ） times of operation for a n to rt task assignment. We simulate the pruning optimization algorithm and com- pare it with the Hungary algorithm. The simulation results and their comparison given in Table 1 and Fig. 1 show preliminarily that our pruning optimization algorithm obtains the same calculation results as the Hungary algorithm, it takes far less calculation time than the Hungary algorithm, thus quickening the speed for solving a task assignment problem.
出处
《西北工业大学学报》
EI
CAS
CSCD
北大核心
2013年第1期40-43,共4页
Journal of Northwestern Polytechnical University
基金
西北工业大学E之星基金资助
关键词
算法
任务分配
运筹学
剪枝优化算法
无人机
algorithms, task assignment
operation research, pruning optimization, unmanned aerial vehicles（UAV）
