论文部分内容阅读
受全球供需趋紧和市场竞争日益激烈的影响,钢铁工业正面临一系列严重的挑战,在能源供应紧张和激烈的市场竞争下,要求最大限度地降低生产成本,这要求企业的生产计划编制方法更加先进和科学。
钢铁企业在热轧生产调度中,编制热轧轧制计划的目标是在满足热轧轧制规范约束条件下,依照用户订单的交货期的需求,以及订单生产的紧急程度,对待生产的板坯按照轧机的产能,编制出板坯的轧制序列,使相邻的板坯之间满足工艺需求的若干约束条件,以满足轧机的实际生产的需要。在自动化水平不断提高的今天,只靠计划人员手工编制轧制计划,已不能满足生产需要。为了充分发挥轧机的能力、合理利用资源,必须借助计算机技术,用优化的方法和科学的手段来编制热轧生产计划。钢铁企业在实际编制热轧生产调度时,一般都是从预选池的Ⅳ个任务当中依次编制出M个轧制单元计划,这种策略为串行策略,但是这种串型策略类似于贪婪方法,先编制的计划可能很好,后编制的计划可能很差,即有可能陷入局部最优,一个合理的办法是从N个任务池当中同时编制出M个轧制单元计划,这种方法称并行方法。若把轧制计划中全部的板坯看成一个个节点(城市),一个轧制生产单元看成是经过一定数目的节点的一条旅行路径,则上述热轧计划编制与优化问题可归结为非对称多旅行商(MTSP)模型。
旅行商问题(TSP)是一个典型的组合优化问题,并且是一个NP难题。很多实际应用问题,如印制电路板的钻孔路线方案,连锁店的货物配送路线等,经过简化处理后,均可建模为旅行商问题,因而对旅行商问题求解方法的研究具有重要实际价值。然而,对于一类更具有实际应用价值的TSP扩展问题——多旅行商问题(Multiple TravelingSalesman Problem,简称MTSP)目前尚未引起人们的足够重视。所谓MTSP通常可以描述如下:M个旅行商从同一城市(或者不同的城市)出发,分别走一条旅行路线,使得每个城市有且仅有一个旅行商经过(出发城市除外),且总旅行路程最短。
另外,在车辆调度方面,机器人运筹学、经济学、管理学、通讯网络系统中也存在大量的多旅行商问题,因此,对MTSP问题的研究,找到一个优化的解决方法,对科学技术及工程技术各方面具有很大的意义。而多旅行商问题是NP难问题,传统的最优化方法和近似方法很难求解或者根本无法进行求解,所以只能借助于近年来兴起的智能优化算法来不断逼近其最优解,比较有效的智能优化算法有:遗传算法(Genetic Algorithms,简称GA)、蚁群算法(Ant Colony Algorithm,简称ACO)、禁忌搜索(Tabu Search,简称TS)、模拟退火(Simulated Annealing,SA)、捕食搜索(Predatory Search,PS)等等。
本文把多旅行商问题分为4种情况,对这四类不同情况分别进行了分析,主要通过把MTSP问题转化为TSP问题来解决,然后分别建立了数学模型,然后针对.上述轧制批计划的编制与优化问题的特点,和一般的多旅行商问题作了对比分析,建立了轧制计划编制和优化问题的数学模型,然后分别设计了针对基于多旅行商问题模型的轧制计划编制和优化问题的遗传算法、蚁群算法和遗传模拟退火混合算法等智能优化算法,编制了仿真测试程序,对两组钢铁企业的实际编制轧制计划所需的板坯数据进行了仿真测试,对上述算法的结果进行了分析对比,结果表明,这几种算法都是可行的,但改进的蚁群算法效果最好,能在较短的时间内求得更好的解。