基于多旅行商问题模型的热轧计划问题的算法研究

摘要

受全球供需趋紧和市场竞争日益激烈的影响，钢铁工业正面临一系列严重的挑战，在能源供应紧张和激烈的市场竞争下，要求最大限度地降低生产成本，这要求企业的生产计划编制方法更加先进和科学。 钢铁企业在热轧生产调度中，编制热轧轧制计划的目标是在满足热轧轧制规范约束条件下，依照用户订单的交货期的需求，以及订单生产的紧急程度，对待生产的板坯按照轧机的产能，编制出板坯的轧制序列，使相邻的板坯之间满足工艺需求的若干约束条件，以满足轧机的实际生产的需要。在自动化水平不断提高的今天，只靠计划人员手工编制轧制计划，已不能满足生产需要。为了充分发挥轧机的能力、合理利用资源，必须借助计算机技术，用优化的方法和科学的手段来编制热轧生产计划。钢铁企业在实际编制热轧生产调度时，一般都是从预选池的Ⅳ个任务当中依次编制出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问题来解决，然后分别建立了数学模型，然后针对．上述轧制批计划的编制与优化问题的特点，和一般的多旅行商问题作了对比分析，建立了轧制计划编制和优化问题的数学模型，然后分别设计了针对基于多旅行商问题模型的轧制计划编制和优化问题的遗传算法、蚁群算法和遗传模拟退火混合算法等智能优化算法，编制了仿真测试程序，对两组钢铁企业的实际编制轧制计划所需的板坯数据进行了仿真测试，对上述算法的结果进行了分析对比，结果表明，这几种算法都是可行的，但改进的蚁群算法效果最好，能在较短的时间内求得更好的解。

目录

文摘

英文文摘

声明

第一章引言

1.1问题的来源及研究目的

1.2问题的背景、特点与意义

1.3本论文的研究路线

1.4本文主要的研究工作

第二章多旅行商问题的分析与建模

2.1 MTSP问题概述

2.2第一类MTSP问题的数学模型

2.2.1问题描述

2.2.2分析

2.2.3变量和参数定义

2.2.4数学模型表示

2.3第二类MTSP问题的数学模型

2.3.1问题描述

2.3.2分析

2.3.3变量和参数定义

2.3.4数学模型表示

2.4第三类MTSP问题的数学模型

2.4.1问题描述

2.4.2分析

2.4.3变量和参数定义

2.4.4数学模型表示

2.5第四类MTSP问题的数学模型

2.5.1问题描述

2.5.2分析

2.5.3变量和参数定义

2.5.4数学模型表示

2.6小结

第三章轧制批计划编制的优化问题

3.1问题描述

3.1.1工艺背景

3.1.2评价指标

3.1.3轧制规范

3.1.4优化目标

3.2数学模型

3.2.1分析

3.2.2变量和参数定义

3.2.3数学模型表示

3.3轧制单元之间均衡的数学模型

3.4问题的求解算法

3.4.1精确算法

3.4.2近似算法

3.4.3智能优化算法

3.5小结

第四章基于MTSP的轧制计划问题的算法设计

4.1遗传算法设计

4.1.1遗传算法基本原理

4.1.2算法设计

4.1.3遗传算法步骤及流程图

4.2蚁群算法设计

4.2.1蚁群算法基本原理

4.2.2蚁群算法基本计算公式

4.2.3蚁群算法的改进

4.2.4蚁群算法步骤及流程图

4.3混合算法设计

4.3.1混合算法的提出

4.3.2混合遗传模拟退火算法基本思想

4.3.3混合模拟退火算法步骤及流程图

4.4小结

第五章计算实例的结果对比与分析

5.1仿真程序

5.2仿真结果

5.2.1实例Ⅰ

5.2.2实例Ⅱ

5.3小结

第六章结论和展望

参考文献

致谢

参加科研情况

发表论文情况