|
|
论文:2013,Vol:31,Issue(1):40-43 |
|
|
引用本文： |
|
|
马云红, 井哲, 周德云. 一种任务分配问题的快速剪枝优化算法[J]. 西北工业大学 |
|
|
Ma Yunhong, Jing Zhe, Zhou Deyun. A Faster Pruning Optimization Algorithm for Task Assignment[J]. Northwestern polytechnical university |
|
|
|
|
|
|
|
| 一种任务分配问题的快速剪枝优化算法 |
|
| 马云红, 井哲, 周德云 |
|
| 西北工业大学 电子信息学院, 陕西 西安 710072 |
| 摘要: |
| 任务分配问题是运筹学中的一类规划问题,求解这类问题的比较经典的算法是匈牙利算法,但匈牙利算法在求解大规模任务分配时运算效率不高。文章提出了一种新的求解任务分配问题的方法——剪枝优化算法。算法通过逐步剔除已确定的部分分配方案对应代价矩阵元素,逐次降低分配问题的规模,从而实现快速求解全局任务分配问题。对于n个主体执行n个任务的分配问题,进行(n-1)次操作就可以获得最优解。论文进行了相应的仿真,将文章提出的算法和匈牙利算法做了比较。仿真结果表明,该算法与传统匈牙利算法计算结果一致,但计算耗时远远小于匈牙利算法,即该算法大大提高了任务分配问题的求解速度。 |
| 关键词:
算法
任务分配
运筹学
剪枝优化算法
无人机
|
|
| A Faster Pruning Optimization Algorithm for Task Assignment |
|
| Ma Yunhong, Jing Zhe, Zhou Deyun |
|
| Department of Electronics Engineering,Northwestern Polytechnical University,Xi'an 710072,China |
| Abstract: |
| To our knowledge, the Hungary algorithm is not satisfactory for solving a large scale task assignmentproblem in the fields of operation research because it requires several changes in cost matrix and seeks, selects anddeletes 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 n 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 showpreliminarily 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 assignmentproblem. |
| Key words:
algorithms
task assignment;operation research
pruning optimization
unmanned aerial vehicles(UAV)
|
|
| 收稿日期: 2012-05-15
修回日期:
|
| DOI: |
| 基金项目: 西北工业大学E之星基金资助 |
| 通讯作者:
Email： |
| 作者简介: 马云红(1972-)，女，西北工业大学副教授，主要从事优化算法、飞行器任务规划和智能控制的研究。
|
|
| 相关功能 |
|
|
|
|
| 作者相关文章 |
|
| 马云红 在本刊中的所有文章 |
| 井哲 在本刊中的所有文章 |
| 周德云 在本刊中的所有文章 |
|
|
|
|
|
|
|
|
参考文献: |
|
|
[1] Winston Wayne L.Operation Research Application and Algorithms.Beijing,Tsinghua University Press,2011
[2] Wei Kangy,Andrew Sparks.Task Assignment in the Cooperative Control of Multiple UAVs.AIAA-2003-5583
[3] Corey Schumacher,Phillip R Chandler.Path Elongation for UAV Task Assignment.AIAA-2003-5585 |
|
|
|
相关文献: |
|
|
1．王刚, 胡峪, 宋笔锋.利用螺旋桨动力配平的飞翼布局无人机[J]. 西北工业大学, 2014,32(2): 181-187 |
|
|
2．谭雁英, 胡淼, 祝小平, 周洲.基于人机合作策略下SAS算法的多无人机路径再规划[J]. 西北工业大学, 2014,32(5): 688-692 |
|
|
3．刘洋, 章卫国, 李广文, 史静平.一种三维环境中的无人机多路径规划方法[J]. 西北工业大学, 2014,32(3): 412-416 |
|
|
4．何建华, 王安龙, 陈松, 张越, 刘琨, 赵焕义.基于改进MOSFLA的多机协同任务分配[J]. 西北工业大学, 2014,32(4): 630-636 |
|
|
5．邢小军, 席奥, 闫建国.多无人机协同编队最优鲁棒控制方法研究[J]. 西北工业大学, 2013,31(5): 722-726 |
|
|
6．谭雁英, 许鳌, 祝小平, 周洲.小型无人机掠海飞行高度滤波系统优化设计[J]. 西北工业大学, 2013,31(4): 511-516 |
|
|
7．屈耀红, 肖自兵, 袁冬莉.基于风场信息的无人机在线航迹规划方法[J]. 西北工业大学, 2012,30(4): 576-581 |
|
|
|
|
|
|
