最优分组周游路线问题建模与双层遗传算法求解

摘要

最优分组周游路线问题是一类物流智能调度问题,是众多的计算难度极大的组合爆炸问题之一.自从运输问题最早由Hitchcock在1941年提出[2,4]后,人们对这一类问题给予了极大的关注并进行了大量的研究,提出了有效解决问题的优化算法--单纯形法的变形[2].但由于问题规模的扩大,纯数学方法在允许的时间和空间上都很难找到问题的最优解,于是人们开始转向寻找问题的近似最优解,遗传算法以其在求解最优化问题中的独特的自组织性、自适应性很快进入人们的视野.经典的遗传算法对于求解多目标的NP完全性问题非常有效,但对于有多个限制条件的多目标最优化问题缺显得有点力不从心,很难得到稳定度较高、收敛较快的解.本文提出的双层遗传算法模型给这一类问题提供了一个很好的解决方法,虽然建模条件限制了描述的问题的通用性,有待推广,但它能有效利用问题的领域知识,提高了求解效率,保证了解的可行性和最优性,算法思想极具推广潜力,可在其它物流智能调度问题求解算法设计中借鉴.