Model and PSO-Based Solution of Two-Dimensional Unbalanced Assignment Problem
-
摘要: 为解决运输中任务数与车辆数不等情况下的换装问题,建立了二维不平衡指派问题的优化模型,并用粒子群算法(PSO)求解此问题.对几种不同情况下的不平衡指派问题进行了数值模拟,并与全枚举法的计算结果进行了比较.结果表明,PSO收敛到最优解的概率和收敛速度均优于全枚举法,所建立的模型及其求解方法能获得决策者满意的换装方案.Abstract: To solve the unequal transfer problem when the number of tasks differs from the number of vehicles,a model for two-dimensional unbalanced assignment problems was established,and the particle swarm optimization(PSO) was adopted to obtain its solution.Numerical simulation was conducted under different unequal assignments,and the simulation result was compared with the result based on the completed enumeration.The research result shows that PSO is superior to the completed enumeration in the probability of getting the optimal solution and the convergence speed,so the established model and PSO can be used for getting a satisfactory transfer plan.
-
Key words:
- assignment problem /
- particle swarm optimization /
- random /
- coding
-
滕传琳.管理运筹学[M].北京:中国铁道出版社,1986:126-131.[2] 李苏北.一类最优指派问题的动态规划解法[J].运筹与管理,2000,9(1):69-73.LI Subei.Dynamic programming method of a sort of optimal assignment problem[J].Operations Research and Management Science,2000,9(1):69-73.[3] 李引珍,郭耀煌.一类带时间约束指派问题的分枝定界算法[J].系统工程理论与实践,2005(6):39-43.LI Yinzhen,GUO Yaohuang.A branch and bound algorithm for an assignment problem withtime constralnts[J].Systems Engineering--Theory & Practice,2005(6):39-43.[4] 苏祥定,孙桐,马霖.不平衡指派问题的差额法求解及其应用[J].计算机工程,2005,31(22):178-180.SU Xiangding,SUN Tong,MA Lin.Application of difference method in unequally assignment problem[J].Computer Engineering,2005,31(22):178-180.[5] 岳中亮.m维瓶颈指派问题的动态规划模型[J].湛江海洋大学学报,2005,25(6):73-76.YUE Zhongliang.Dynamic programming model for problem of m-dimensional bottleneck assignment[J].Journal of Zhanjiang Ocean University,2005,25(6):73-76.[6] KUMAR A.A modified method for solving the unbalanced assignment problems[J].Applied Mathematics and Computation,2006,176(1):76-82.[7] COHEN R,KATZIR L,RAZ D.An efficient approximation for the generalized assignment problem[J].Information Processing Letters,2006,100(4):162-166.[8] DEMIREL N C,TOKSAPd M D.Optimization of the quadratic assignment problem using an ant colony algorithm[J].Applied Mathematics and Computation,2006,183 (1):427-435.[9] 赵冬梅,陶章华.不定期多目标动态规划问题的非劣矩阵解法[J].西南交通大学学报,2003,38(6):675-679.ZHAO Dongmei,TAO Zhanghua.Method of noninferior matrix of multi-objective dynamic programming with indefinite phases[J].Journal of Southwest Jiaotong University,2003,38(6):675-679.[10] 李致中,史峰,孙焰,等.铁道运输管理的数学模型计算法[M].武汉:华中理工大学出版社,1995:135.[11] 曾建潮,介婧,崔志华.微粒群算法[M].北京:科学出版社,2004:13-15.
点击查看大图
计量
- 文章访问数: 1668
- HTML全文浏览量: 85
- PDF下载量: 496
- 被引次数: 0