（系统工程专业论文）钢铁企业铁水运输实时调度问题的列生成算法研究.pdf

东北大学硕士学位论文 摘要 摘要 运输在钢铁企业的生产过程占据着非常重要的地位，而铁水运输则是连接炼铁 和炼钢工艺的桥梁，有效的铁水运输实时调度对提高钢铁企业的生产效率至关重 要。因此，优化铁水运输调度具有重要的实际意义。同时由于铁水运输调度兼具 大规模和复杂约束特性。使得研究其最优化算法又具有重要的理论意义。本文从 铁水运输调度的实际背景提炼出铁水分配问题和机车调度问题分别进行研究。针 对铁水分配问题和机车调度问题，分别开发求解其最优解的列生成算法。主要研 究工作如下： 1 ) 归纳了求解组合最优问题各类策略，综述了列生成算法的发展历史、算法 思想、求解线性规划、整数规划的步骤、列生成算法的优点与难点、以及适合用 列生成算法求解的问题。 2 ) 建立了铁水分配问题的混合整数规划模型，转化为一个等价的网络模型， 基于网络模型构建了其集划分模型。由于铁水分配的列生成算法子问题是n p 一难 的，提出基于状态空间松弛的技术求解子问题。提出了基于网络模型的弧分支策 略。构建了两个启发式算法得到问题的初始解。 3 ) 分析了机车调度的实际特性，提出运输模式的概念，基于运输模式建立了 机车调度问题的混合整数规划模型应用d a n t z i g w o l f e 分解得到集划分模型。提 出了两个贪婪启发式算法求解问题的初始可行解，并在仞始限制主问题中引入人 工变量的策略以启动列生成算法。针对价格子问题，提出一种改进的l a b e l 算法， 并在算法中通过分析解的性质进行l a b e l s 消除。针对该问题的分支一价格算法，提 出了指派分支策略。 在p e n t i u m i v 系列主频2 4 g 的计算机上，使用c + + 语言实现了铁水分配问题和 机车调度问题的基于列生成的分支价格一算法，并进行实验仿真。实验结果表明提 出的算法能够有效的求解工业规模的铁水分配问题和机车调度问题。 关键词：铁水分配，机车调度，列生成，分支一价格，动态规划，状念空问松弛，运输 模式，l a b e 算法 墨! ! 垄堂堑主主堡垒查 垒! ! ! 翌竺 a b s t r a c t t r a n s p o r t a t i o np l a y sa ni m p o r t a n tr o l e i nt h ep r o d u c t i o no fi r o na n ds t e e l e n t e r p r i s e s a st h eb r i d g el i n k i n gi r o n m a k i n ga n ds t e e l m a k i n go p e r a t i o n s ，e f f i c i e n t m o l t e ni r o nt r a n s p o r t a t i o nr e a l - t i m es c h e d u l ei sc r u c i a lf o ri n c r e a s i n gp r o d u c t i v i t yo fi r o na n d s t e e lp l a n t t h e r e f o r e ，t oo p t i m i z em o l t e ni r o nt r a n s p o r t a t i o ns c h e d u l ei so fr a t h e rp r a c t i c a l s i g n i f i c a n c e o nt h eo t h e rh a n d ，h a v i n gt h ec h a r a c t e r so fl a r g e s c a l ea n dc o m p l e x c o n s l r a i n t s ，t h er e s e a r c ha b o u to p t i m i z a t i o na l g o r i t h mi sa l s oo ft h e o r e t i c a lm e a n i n g ，m o l t e n i r o na s s i g n m e n tp r o b l e ma n de n g i n es c h e d u l i n gp r o b l e ma r i s i n gf o r mp r a t i c i a lb a c k g r o u n do f m o l t e ni r o nt r a n s p o r t a t i o ns c h e d u l ea r es t u d i e dr e s p e c t i v e l ya n dc o h m mg e n e r a t i o n a l g o r i t h m sa r ed e v e l o p e dt oo b t a i no p t i m a ls o l u t i o n so ft h e m t h ea u t h o r sm a i nw o r kc a n b es u m n l a r i z e da sf o l l o w s ： 】) t h ep a p e rs u m m a r i z e sc u r r e n ts o l v i n gs t r a t e g i e sf o rc o m b i n a t o r i a lp r o b l e m s ， r e v i e w st h ed e v e l o p i n gh i s t o r ya n dt h ec o n c e p to fc o l u m ng e n e r a t i o na l g o r i t h m ， i n t r o d u c e st h es o l v i n gp r o c e d u r e sf o rl i n e a rp r o g r a m m i n ga n di n t e g e rp r o g r a m m i n g ， a n dp r e s e n t st h ea d v a n t a g e s ，t h ed i 佑c u r i e sa n ds u i t e dp r o b l e m so fc o l u m ng e n e r a t i o n a l g o r i t h m 。 2 ) t h ep a p e rd e v e l o p st h em i x e di n t e g e rp r o g r a m r u i n gm o d e lf o rm o l t e ni r o n a s s i g n m e n tp r o b l e ma n dt r a n s f o r m si ti n t oa ne q u i v a l e n tn e t w o r km o d e l s ，b a s e do nw h i c h c o n s t r u c t st h es e tp a r t i t i o nm o d e l b e c a u s et h es u b - p r o b l e mo fc o l u m ng e n e r a t i o na l g o r i t h m f o rm o l t e ni r o na s s i g n m e n tp r o b l e mi sn p - h a r d ，s t a t e - s p a c er e l a x a t i o nb a s e dt e c h n o l o g yi s p r o p o s e df o rs o l v i n g b a s e do nt h en e t w o r km o d e l ，a r c b r a n c h i n gs t r a t e g yi sp u tf o r w a r d t h e i n i t i a lf e a s i b l es o l u t i o ni so b t a i n e db yc o n s t r u c t i n gt w oh e u r i s t i ca l g o r i t h m s 3 ) t h ep a p e ra n a l y z e s t h e p r a c t i c a lf e a t u r e so fe n g i n es c h e d u l i n gp r o b l e m ， p r o p o s e st h ec o n c e p to ft r a n s p o r t a t i o np a t t e r n ，b a s e do nw h i c hd e v e l o p st h em i xi n t e g e r p r o g r a m m i n gm o d e lf o re n g i n es c h e d u l i n gp r o b l e m ，o b t a i n st h es e tp a r t i t i o nm o d e lb y a p p l y i n gd a n t z i g w o l f ed e c o m p o s i t i o n t w og r e e d yh e u r i s t i ca l g o r i t h m sa r ep r o p o s e d t oc r e a t et h ei n i t i a lf e a s i b l es o l u t i o n ，a n da r t i f i c i a lv a r i a b l e sa r ea d d e dt ot h ei n i t i a l r e s t r i c t e dm a s t e rp r o b l e mt oa c t i v a t et h ec o l u m ng e n e r a t i o na l g o r i t h m t os o l v ep r i c i n g l i l 查! ! 叁兰堡主兰垒笙圭 垒! ! ! 翌! ! s u b p r o b l e m ，am o d i f i e dl a b e la l g o r i t h mi sp u tf o r w a r dt oc o m p l e t el a b e l se l i m i n a t i o n u p o nt h ea n a l y s i sa b o u tt h es o l u t i o n sp r o p e r t i e s t od e v e l o pt h eb r a n c h - a n d p r i c e a l g o r i t h m ，a s s i g n m e n t - b r a n c h i n gs t r a t e g yi sa d o p t e d o nt h ep e n t i u mi v2 4 gh zc o m p u t e r , t h ec o l u m ng e n e r a t i o n - b a s e d b r a n c h - a n d - p r i c ea l g o r i t h m s a r ei m p l e m e n t e db yc + + l a n g u a g ea n dt h es i m u l a t i o n e x p e r i m e n t sa r ec o n d u c t e d ，c o m p u t a t i o nr e s u l ti n d i c a t e st h ep r o p o s e da l g o r i t h mc a n e f f e e t i v l ys o l v et h ei n d u s t r i a l - s i z e dm o l t e ni r o na s s i g n m e n ta n de n g i n es c h e d u l i n g p r o b l e m s k e y w o r d s ：m o l t e ni r o na s s i g n m e n tp r o b l e m ，e i l g m es c h e d u l i n gp r o b l e m ，c o l u m n g e n e r a t i o n ，b r a n c h a n d - p r i c e ，s t a t e - s p a c er e l a x a t i o n ，t r a n s p o r t a t i o np a t t e m ，l a b e la l g o r i t h m i v 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取 得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或 撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确 的说明并表示谢意。 学位论文作者签名：江蒜拶 日期：m r 2 o 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学 位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的 复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学 位论文的全部或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名：否则视为不同意。) 学位论文作者签名： 签字日期： 导师签名： 签字日期： 东北大学硕士学位论文 第一章绪论 第一章绪论 本文首先介绍钢铁企业铁水运输实时调度问题的| 束源、研究目的、选题背景以 及研究意义。接着对钢铁企业的铁水运输实时调度问题的研究现状进行了综述， 指出现有研究文献中存在的问题和没有涉及的方面以及进一步研究的方向。最后， 对本文的研究技术路线和主要工作进行了总结。 1 1 问题的研究目的及意义 1 1 1 问题的来源及研究目的 本论文的研究课题来源于国家自然科学基金项目课题( 6 0 2 7 4 0 4 9 ，7 0 1 7 1 0 3 0 ) , d 国家自然科学基金杰出青年基会项目。 本论文的目的是研究钢铁企业内的铁水物流运输实时调度优化问题。通过对钢 铁企业铁水物流性质的定性定量分析，建立了铁水运输实时调度问题的数学模型， 提出有效的最优化算法，为优化钢铁企业的铁水运输实时调度提供科学的、定量 的决策支持。本文从铁水运输实时调度的实际背景中提炼出铁水分配问题和机车 调度问题，分别进行研究，构建了两个问题的列生成算法。针对具体问题的列生 成算法中涉及的子问题求解、分支策略、列池管理、初始解的启发式算法等方面 进行了深入的研究。 1 1 2 问题的背景、特点及意义 钢铁企业是国民经济的支柱产业它为其他很多行业如：建筑、机械、家电、 汽车等提供原材料。随着全球经济一体化，钢铁企业将面临着更多的挑战。企业 之间的竞争实际上是企业产品之间的竞争，而企业产品的竞争力，在很大程度上 取决于企业生产运作管理的绩效：如何保证质量，降低成本和把握时间。从这个 意义上来既，生产运作管理是企业竞争力的真l f 源泉。 调度是生产运作管理的核心内容和关键技术。调度的目的就是在满足一定的技 术和资源约束的条件下，合理的安排操作顺序和分配资源，最优化一个给定的目 标。在过去的几十年中，许多学者对调度问题进行了大量的研究工作，调度理论 i 东北把孝硕士学位论丈 第一章绪论 第一章绪论 本文首先介绍钢铁企业铁水运输实时调度问题的米源、研究目的、选题背景以 及研究意义。接着对钢铁企业的铁水运输实时调度问题的研究现状进行了综述 指出现有研究文献中存在的问题和没有涉及的方面以及进步研究的方向。最后， 对本文的研究技术路线和主要工作进行了总结。 1 1 问题的研究目的及意义 1 1 i 问题的来源及研究目的 本论文的研究课题柬源于国家自然科学基金项目课题( 6 0 2 7 4 0 4 9 ，7 0 1 7 1 0 3 0 ) 和 国家自然科学基余杰出青年基会项目。 本论文的目的是研究钢铁企业内的铁水物流运输实时调度优化问题。通过对钢 铁企业铁水物流性质的定性定量分析，建立了铁水运输实时调度问题的数学模型， 提出有效的最优化算法。为优化钢铁企业的铁水运输实时调度提供科学的、定量 的决策支持。本文从铁水运输实时调度的实际背景中提炼出铁水分配问题和机车 调度问题，分别进行研究，构建了两个问题的列生成算法。针对具体问题的列生 成算法中涉及的子问胚求解、分支策略、列池管理、仞始解的启发式算法等方丽 进行了深入的研究。 1 1 2 问题的背景、特点及意义 钢铁企业是国民经济的支柱产业它为其他很多行业如：建筑、机械、家电、 汽车等提供原利料。随着全球经济一体化，铜铁企业将面临着更多的挑饯。企业 之间的竞争实际上是企业产品之间的竞争，而企业产品的竞争力，在很大程度上 取决于企业生产运作管理的绩效：如何保证质量，降低成本和把握时间。从这个 意义上来醴，生产运作管理是企业竞争力的真一源泉。 调度是生产运作管理的核心内容和关键技术。调度的目的就是在满足一定的技 术和资源约束的条件下合理的安排操作顺序和分配资源最优化一个给定的目 标。在过去的几十年中，许多学者对调度问题进行了大量的研究工作，调度理论 标。在过去的几十年中。许多学者对调度问题进行了大量的研究工作，调度理论 东北大学硕士学住论文第一章绪论 已经逐渐发展成熟，并且已经应用到各行各业，如机器制造、运输、航空航天等 领域。在过去十年中，钢铁生产已经成为调度研究一个新热点。虽然调度理论在 各个领域都取得了很多研究成果，但是由于各个行业之间的差距，一般意义上的 研究已经不能够满足对具体问题的应用。钢铁生产出于具有半离散，半连续，多 阶段，多过程生产形式，兼有离散和连续生产特性，这就导致了钢铁调度相对于 其他调度更加复杂。当前，钢铁企业内的炼钢一连铸、热轧、板坯倒跺等方面调度 问题已经有了大量的研究成果【t , 2 , 3 , 4 1 。但是，钢铁企业内连接炼钢和炼铁的一个关 键环节一铁水运输的研究还相当的少。因此，本文是以大型钢铁企业的铁水运输 为背景，采用运筹学的手段，对铁水运输中的相关调度问题做出分析和研究。 运输在钢铁企业中占据着举足轻重的位置，它贯穿于钢铁企业的各个生产环 节。图1 1 为钢铁企业的基本生产工艺流程图，从图中可以看出，任何相邻的两道 处理工艺间都有运输的存在。铁水运输又是其中的一个关键环节，因为它是连接 炼铁和炼钢的桥梁。钢铁企业内的铁水运输主要有如下特征： 1 ) 高温操作、温度要求高。从高炉中冶炼出来的铁水一般温度在1 4 5 0 。c 1 5 0 0 c ， 这些铁水必须快速的运往炼铁车间进行冶炼，因为运输的过程必将有热量损 失，当热量损失过多，温度降低到铁水熔点以下的时候，就会在鱼雷车( t p c i 内结瘤，导致t p c 损坏。 2 ) 安全生产要求。高炉出铁口以1 2 5 t m i n 的出铁速度向空t p c 出兑铁水，这个 过程称为t p c 的受铁过程。由于高炉连续生产的特性，为确保高炉的出铁安 全，要求t p c 的受铁过程必须保持顺畅，否则，当出铁口的t p c 数量不够时， 铁水只能停留在高炉内，这将影响高炉的炼铁计划，降低铁水质量。 3 ) 生产流程复杂。铁水运输是由高炉、t p c 、机车、脱硫、脱磷装置、扒渣装置、 装档、转炉、电弧炉、倒渣、装档等一系列设备按照从前到后的工艺路线组合 而成。 4 ) 生产实时性要求。高炉出铁和转炉炼钢对t p c 和机车都有实时性要求，t p c 和机车的作业安排必须适应高炉的实时出铁速度和转炉对铁水的实h 寸需求。 5 ) 运输资源有限。钢铁企业的铁水运输路线、运输设备都属j 二基础设旌，一般都 是有限的，随着生产规模的扩大，必须合理的利用有限的运输资源，完成所有 的运输需求。 6 ) 操作费用高。掘相关资料1 5 】显示，宝钢的机车一般作业率为8 7 5 ，说明机车 塞! ! 垄堂塑主兰堡堡圭 苎= 主丝一 在一天内8 7 5 的时间都在运行，而机车属于高能耗动力工具，因此操作费用 相当的商。 图1 i 钢铁企业基本生产l ：艺流稗幽 f i g 1 1t h e p r i m a r yp r o d u c t i o np r o c e s s i n i r o na n ds t e e l i n d u s t r y 铁水运输调度的特征说明了铁水运输调度优化问题是一个很复杂的问题。同 时，优化铁水运输调度方案能够充分发掘设备潜力，提高运输能力，降低运输费 用，节约资源能源，保持高效有序的连续生产，从而实现降低产品成本，提高产 品质量、缩短产品生产周期，它是钢铁企业亟待解决的一个重要的优化问题。因 此，研究铁水运输调度优化问题既满足钢铁企业的实际生产需求同时也具有理论 研究意义。铁水运输调度优化问题涉及到铁水分配，机车调度，t p c 配对等多个 问题。为了实现全局优化调度，又必须从长一些的调度周期去考虑问题。凶此， 铁水运输过程涉及的调度问题既具有复杂性，又具有大规模特性，这就增大了问 题求解难度。设计大规模复杂约束调度问题的最优化算法也是本文的主要研究之 一，具有重要的理论意义。 1 查! ! 查兰壁主堂堡笙墨 1 2 铁水运输调度问题的研究现状 第一章绪论 铁水运输调度优化问题既具有理论研究意义又是钢铁实际生产的需要，因此， 对于这一课题的研究也引起了许多学者的兴趣。出于铁水运输调度问题是一个复 杂的调度问题，因此，当前有关它的研究大多都是基于信息集成和系统仿真的手 段。当前宝钢铁水运输系统采用d g p s 卫星复合定位定航，无线数据车载通讯等 技术实现了信息系统集成管理。但是，实际的运输调度部署包括配车计划、机车 运行作业计划、t p c 运行作业计划等，还是由工作人员的手工操作。因此，实际 调度决策的优化程度就依赖于工作人员的实际经验和主观性。另外，当处于任务 峰期，到达的任务非常多，依靠工作人员的经验很难做出一个最优的决策，但是 又不可以贻误调度指令的发出，所以只得按照一般的启发式规则如先来先服务 ( f i f s ) 等进行调度。 文献【6 】分析了宝钢铁水运输系统的特点，针对其系统为混杂系统、不同于般 铁路运输、以及包含人的因素在内的特点建立了对应的仿真系统。通过一系列的 关键技术的解决和使用，仿真系统实现了对现系统和待建系统的系统特性分析， 其结论一方面可以作为辅助决策的依据，另一方面，也为现场进行铁水物流系统 的优化提供了参数和方案。文献【7 】利用p e t r i 网，针对仿真系统的各个实体，包括 高炉出铁口、高炉出铁线、脱硫间、倒罐站、前、后扒渣l 、日j 、倒渣问、电炉、锭 模、铸铁机、炉窑、t p c 、机车和铁路，建立了模型。对多种方案进行仿真试验， 通过不同方案下仿真结果的比较，得出了铁水运输调度方式的优化方案。 上述铁水调度系统的建立都是基于系统仿真，系统仿真模拟实际生产过程，对 系统进行实验研究，能够及时通过仿真结果反馈的信息调整其中的阔度方案。但 是，仿真系统中的调度方案都是采用启发式调度规则，只是从定性的方面提出一 个相对比较好的方案，但是调度方案的改进余地究竟有多少，它也无从知道。r 本神户钢厂开发的铁水运输调度系统建立了t p c 和机车的编组优化组合的模糊规 划数学模型，采用分支定界算法计算出t p c 和机车最优搭配忙】。由模糊线性规划 确定的数学模型，采用分支定界算法能够快速的计算出一个小时内的作业进度安 排。该系统成功投入使用，一方面大幅度降低了调度员的工作负荷；另一方面， 提高铁水输送效率，减少热量损失，实现铁水热装热送，t p c 的往返次数由原柬 的每天2 6 9 次提高到每天2 9 2 次，t p c 的台数也减少了一台：最后，由于强化了 4 东北大学硕士学位论文 第一章绪论 实绩管理工作，也查明了影响运输效率的瓶颈工序，为以后瓶颈工序设备的改进， 进一步提高物流作业效率打下良好的基础。 综上所述，虽然关于铁水运输调度问题已经有了一定的研究成果，但是，大多 数有关这方面的问题还主要集中在一般的方案、策略研究，采用系统仿真的研究 方法较多，采用定量计算特别是从数学建模求解的角度去研究这类问题的成果相 当的少。仿真用于调度虽然可以更好的描述复杂的问题模型，但是不能找到最优 的调度方案。文献1 7j 建立铁水运输问题的模糊线性规划模型，但是其提出的分支定 界算法只能求解小规模的问题，系统还只能优化一个小时内的作业调度，缺乏对 问题性质的充分挖掘，没有实现全局优化。因此，无论铁水运输调度问题的性质， 数学模型，还是求解算法都存在深入研究的必要。本文采用分级策略研究铁水运 输调度问题，首先确定铁水的去向，也就是处理铁水如何分配，接着考虑如何安 排机车牵引t p c ，最后确定机车和t p c 的配对以及它们的运行路线。对前两级问 题分别进行了深入的分析研究。建立了数学模型。另外，由于铁水分配和机车调 度问题的复杂性，一般的优化算法难以求得问题的最优解，本文针对具体问题性 质和数学模型，丌发了求解问题最优解的列生成算法。 1 3 本文的技术路线和所做的工作 1 3 1 研究的技术路线 本文的研究技术路线见图1 2 。 1 3 2 本文的主要工作 本文主要探讨研究了钢铁企业内部的铁水运输调度的优化问题。对铁水运调问 题，采用分级处理策略将其分解为铁水分配问题和机车调度问题，列这两个问题 分别建立了混合整数规划模型和丌发了最优化算法一基于列生成的分支一价格算 法。具体工作如下： 1 ) 对列生成算法的理论基础进行了深入的研究，综述了列生成算法基本思想，算 法流程以及分析了列生成算法适合求解的问题，为解决具体的铁水运输调度问 题提供算法可行性支持。 2 ) 研究了铁水分配问题的工业背景，归纳了铁水分配问题的性质，将其归结为一 5 东北大学硕士学位论文第一章绪论 类带有时间窗约束的并行机调度问题。 3 ) 建立铁水分配问题的一般整数规划数学模型。 4 ) 将铁水分配问题转化为一个等价的网络模型，在网络模型的基础上建立铁水分 配问题的集划分模型，针对集划分模型，开发了基于列生成算法求解其线性规 划松弛的分支一价格算法。对列生成算法价格子问题提出基于状态空间松弛的 动态规划算法。基于网络模型，提出了分支价格算法的弧分支策略。构建了 两个启发式算法求解铁水分配问题的初始可行解。 5 ) 研究问题机车调度问题的实际操作背景，结合机车运输的实际容量约束，提出 了运输模式的橛念。 6 ) 分析机车调度问题同一般p d p t w 的异同。在运用运输模式概念的基础上，结 合一般p d p t w 问题的数学模型，建立机车调度问题的一般整数规划模型。应 用d a n t z i g w o l f e 分解得到机车调度问题的集划分模型。 7 ) 针对机车调度问题的集划分模型，提出了列生成算法。采用两个贪婪启发式算 法求解问题的初始可行解，用以构建初始限制主问题，并在初始限制主问题中 引入人工变量的策略以启动列生成算法。基于运输模式的概念，采用改进的 l a b e l 算法求解列生成子问题。提出基于指派的分支策略。 查! ! 垄堂堡圭堂竺丝圭茎二兰竺笙 主体问题 核心算法一 问题研究 一 模型建立c - 二= 子问题求解= 二一 分支策略 算法实现 铁水运输吏时调度列生成算法研究 i l 铁水分配问题的机牛涮度问艇的 列生成算法研究列生成尊法研究 铁水分配问题的 机- 午渊度门题描述 特性分析提出运输模式概念 混合整数规划模型、 基于运输模式的整数规划 网络流模型、集划分模型模型、集划分模型 i j 状态空间松弛技术改进的l a b e l 算法 纂十网络流模犁的 弧分支策略 指派分支策略 分支价格算法的没汁 分支价格算法的设十 图1 2 本文研究的技术路线 f i g i 21 1 h et e c h n o l o g yp r o c e s so fr e s e a r c h - 7 东北大学硕士学位论文第二章组合最优化及列生成算法研究 第二章组合最优化及列生成算法研究 组合最优化问题是运筹学的一个分支，在近二十年来随着管理科学、计算机 技术的发展越来越受到人们的重视。列生成算法最早在6 0 年代被d a n t z i g 等人提 出用以解决大型线性规划问题。近十年来，随着计算机科学和线性规划工具以及 列生成技术的发展，列生成算法已经被成功的应用解决多类组合最优化问题。本 章研究了组合最优化问题的一些定义、定理、性质，求解方法以及综述列生成算 法的发展历史、基本思想和算法流程等。 2 1 组合最优化的基本理论 本节根据一些组含最优化研究文献和算法理论一般综述文献引，将给出组合 最优化问题的定义、算法的定义，最优算法的定义以及算法的时问复杂性的定义， n p - 完全、n p 难的介绍，最后归纳求解组合最优化问题的各类算法。 2 1 1 基本定义 定义1 ：组合最优化问题，r 是一个极小化，或者是一个极大化问题，它由下述三部 分组成： 1 ) 实例集合： 2 ) 对于每一个实例j ，有一个有穷的可行解集合s 圆： 3 ) 目标函数，= 它对每一个实例，和每一个可行解口e s 御，赋以一个有理数玎，盯) 。 如果耀极小化问题( 极大化问题) ，则实例i 的最优解为这样一个可行解s 御， 它使得对于所有d e s 御，都有_ ，( j ，盯、) u ，回( ，【1 ，盯、) 醐j a ，) 。 定义2 ：算法是指一步步求解问题的通用程序，它是解决问题的程序步骤的一个清 晰描述。这罩讨论的仅仅是确定型算法，即算法从前一步到后一步的运行是由当 时状态唯一确定的，如果存在一个算法，它对问题椭每一个实例，存在有限步 后，一定可得到该实例的关于椭提问的答案，那么就称垓算法解问题风 定义3 ：对于一个优化问题历如果给定任意一个实例j ，算法a 总能找到一个可 行解o - e s ( i ) ，那么就称a 为嘲近似算法：如果进一步这个可行解的目标值总等于 最优解值，则称a 为最优算法。 r 东北大学硕士学位论交第二章组合最优化及列生成算法研究 定义4 ：算法的时间复杂性是关于实例输入长度的函数，用来表示算法的时j 日j 需求， 对于每一个可能的输入长度，它是该算法解此输入长度的最坏情况下的所用的时 间作为时间复杂性的度量。 2 1 2n p 完全、n p 难问题 定义5 ：如果n p 类中的所有问题都可以多项式时间归约到n p 类的某个问题7 , 则 称旋n p 完全问题。 定义6 ：如果某优化问题刀韵判定问题是n p 完全的，则称问题刀是n p 一难的，如果 判定问题是强n p 完全的，则称提强n p 一难的。 定理1 ：如果存在一个n p 难问题田可以多项式时删归约到问题而，则而也是n p - 难的。 2 1 3n p - 难问题的求解方法 如何有效的求解n p 一难问题一直是学术界的热点研究课题之一。本文归纳出以 下四类策略用以求解n p 一难问题，得到最优解或者近似解。 1 ) 降低搜索空间的策略。一般来说，分支定界和动态规划都是有效的改进搜索空 蒯的算法。分支定界是将原问题看成“决策树”的根节点，由根节点逐层向下 产生新节点( 分支) ，每个节点表示一个部分解并且根据问题性质赋予下界值； 根据各个节点的下界值，采用一定的搜索策略对决策树进行搜索，通过定界的 方式识别那些不可能扩充为最优解的部分解，从而将这些部分解所在的分支节 点剪除( 剪支) 。分支的过程在于枚举问题的可行解，剪支的过程就用以降低搜 索空间。动态规划方法通过将问题的过程分成几个相互联系的阶段在决策过 程中将当前阶段和未来各阶段分丌，同时也将当前阶段的效益和未来阶段的效 益结合起来考虑，对于每阶段决策的选取是从全局考虑，同时也是浚阶段状态 的函数，而初始状态是己知的，所以最优策略所经过的各阶段状态可依掘逐次 变换得到。动态规划方法最突出的贡献在于能够给出求解原问题的一个伪多项 式时间算法。其他的改进搜索空渊的算法还包括割平面、b e n d e r s 分解、约束 传播等。本文的后面几章都将用到分支定界和动态规划算法。 2 1 特定问题的有效指数算法。时f 刚复杂性分析是最坏情况的分析，指数时间算法 是指在最坏情况下浚算法所用的时问很大。计算复杂性理论给出了一个衡量算 9 东北失学硕士学位论文第二章组合最优化及列生成算法研究 法好坏的标准是，个算法如果是多项式时间算法就被认为是一个有效的好算 法。但是在实际应用中存在这样一些算法，虽然具有指数时间复杂性，但是却 经常地甚至绝大部分情况下可以较快地得到最优解，这类算法很有实际意义。 例如求解线性规划问题的单纯形算法，对于k l e e & m i n t y 给出的极端例子，需 要遍历所有极点后才得到最优解，也就是它是一个指数算法，时| 日j 复杂度为 c ? 为约束数、”为变量数) 。然而很多实际问题的线性规划模型一般都在 在进行3 m 次左右的单纯形迭代就可以得到问题的最优解，因此，单纯形算法 也被广泛应用于各个行业领域。所以，单纯形算法被认为是是求解线形规划问 题的一个有效算法，即使它不是多项式时间算法。因此，对于n p 难问题，找 到对应大多数实例都可以快速得到最优解的指数时间算法也是非常有实际意 义的。后文提及的列生成算法以及在第四章中求解子问题的l a b e l 标签算法就 是这类算法。 3 ) 通过松弛技术降低原问题的求解难度。对一些n p 一难问题，通过松弛一些约束 条件变成一个相对简单的新问题，新问题是原问题的一种特殊情形，并且存在 成熟的有效算法：然后，不断调整新问题与原问题之间的差异直到他们的最优 解一致或者近似。拉格朗同松弛将约束松弛到目标函数中，通过迭代进行乘 子更新，从而达到调整约束的目的。状态空间松弛通过状念空间映射将问题的 原状态空问映射到另外一个状态空问，问题在新的状念空间中存在多项式时闯 算法。但是由于原空间到新的状态空问是一个多对的映射，所以新的状态空 间中求得的最优解通过逆映射到原状态空间得到的解可能不可行。算法通过不 断的调整问题在新的状态空间中的参数，使其最终求得的最优解逆映射到原状 念空间可行。本文的第三章将使用状态空间松弛技术求解列生成予问题。 4 ) 采用启发式算法得到问题的近似解。对于很多实际问题，由于其n p 一难特性， 在有限的时间内很难求得最优解，而实际需求又要求决策者必须在一定的时间 内快速的做出决策，因此，人们就放松了对最优性的要求，希望快速的得到一 个相对好的解，这个相对好的程度一般都是通过它对最优解的近似程度来度量 的。启发式算法主要包括传统的启发式和智能搜索算法两类。传统启发式主要 采用种贪婪的思想，对特定的问题性质和目标函数，设计多项式的规则求得 原问题的一个可行解。而人工智能搜索算法又称超启发式则是突破传统启发式 贪婪思想所陷入局部最优的不足，通过模拟人的思维的进行迭代局域搜索，逐 1 0 东北大学硕士学位论文 第二章纽合最优化及列生成算法研究 步求精来提高解的质量。人工智能搜索算法从8 0 年代发展到现在，已经取得 的非常好的研究成果，其中主要包括：遗传算法、禁忌搜索、模拟退火、蚁群 算法、神经元网络等。 2 2 列生成算法研究 本节主要介绍了列生成算法的发展历史、基本思想、在求解线形规划和整数规 划问题中的具体流程，以及算法优势，综述了列生成算法在各类组合最优化问题 中的应用。 2 2 1 列生成算法的发展 6 0 年代，d a n t z i g w o l f e 首先对线性规划模型提出一种分解思想，即 d a n t z i g - w o l f e ( d w ) 分解io 对线形规划模型进行d w 分解之后，使得新模型的 变量数”成指数增大。由于计算机内存的限制，经典的单纯形算法对这种大规模 线性规划问题已经无能为力。一个非退化线性规划的最优解中，基变量的个数等 于约束数研，而一个退化的线性规划的最优解中，基变量的个数小于约束数m ， 这也就晚明在最优解中基变量的个数不超过埘，对应的列的令数也不超过m 。 基于这样一个事实，于是他们提出这样一个观点，即d w 分解后的模型中的所有 列并不需要完全明确写出，只是通过个子问题生成对目标函数有改进的新列去 替代原可行基中的退基列，当证明当前子问题不能产生出改进目标函数的新列的 时候，算法便终止了。 g i l m o r e & g o m o r y 对一维切割问题( c s ) 建立了一个混合整数舰封j ( m i p ) 模型 雌孔，而他们的m 1 p 模型中本身就包含了“无穷”多列，因为他们的m i p 模型中 每- y , j 表示一个切割模式，而实际的可行切割模式是非常非常多的，采用枚举的 方式得出所有的切割模式显然是困难且不可行的。因此，他们也采用了列生成算 法，即新的切割模式只是在需要的时候也就是对目标函数有改进的时候才去产生 算法也是在不能产生新的切割模式去改进目标函数的时候终止的。 在a r a b e y r e 。4 】和h o t f m a n ”j 等人的研究文献中，他们建立了机组人员调度问题 的集划分模型，并且也使用列生成算法求解。由于机组人员调度问题模型约束的 复杂性，找不到一个有效的算法去生成改进的列。于是，他们使用一个辅助模型 ( a m ) 产生非常多的列，这些列仅仅是原问题( m p ) 所有可行列的一个子集，山a m l i 东北大学硕士学位论文第二章组合最优化及列生成算法研究 产生的列集构成原问题的一个限制主问题( r m p ) 。算法此时先将a m 产生的列存到 一个列池中，然后从列池中选取对目标函数有改进的列换入可行基，将检验数为 正的列从列池中删除，当列池为空的时候算法终止。需要晓明的是a m 功能仅仅 是生成很多可行列，当这些可行列生成之后，r m p 如何选取这些列就与a m 无关 了【i6 j 。显然，r m p 的最优解不一定是m p 的最优解，因为a m 生成列集的仅仅是 所有可行列的一个子集，而原问题的最优列可能不包含在其中，所以这类列生成 得到的也就是m p 的一个次优解。虽然这类列生成算法不能得到m p 的最优解，但 是这类算法却有着较好的应用前景，因为很多实际问题，可行列约束非常的复杂， 几乎不可能用明确的数学规划描述出来，但是却可以采用一个a m 去生成包含非 常多的不违背实际约束的列集，虽然这个列集不能包含所有的列，但是总可以找 到这个列集中的一个组合得到问题较好的解。辅助模型a m 的设计是这类列生成 算法的核心，如何使用的a m 生成非常多的不同列，如何使得a m 得出的列尽可 能的包含最优列，对求得的解的质量都是至关重要的。 车辆调度问题( v r p ) 一直是运筹学界研究的热点，由于v r p 及其扩展问题的 n p 难特性，传统的研究手段一直基于人工智能等近似算法。一般的分支定界以 及动态规划算法也只能求解小舰模的v r p 问题。9 0 年代至今，列生成算法以及成 功的应用于求解v r p 及其扩展问题的最优解1 9 , 2 0 , 2 ”，并且列生成算法已经 发展成求解大规模混合整数规划问题的一个有效最优化算法。 w i l h e l m 在关于列生成算法的综述文献i l6 】指出，切割问题、车辆路线问题、装 配系统设计问题( a s d ) 分别是列生成发展史上三个罩程碑。 2 2 2 列生成算法的基本思想 列生成算法处理的是大规模线性规划或者整数规划的线性规划松弛模型，这类 模型可以由如下两种方式得到：( 1 ) 原模型进行d w 分解，如一般线性舰划问题、 广义分配问题等，( 2 ) 问题模型的本身，如机组人员调度问题等。无论是上述的哪 种方式得到的模型，它们都有一个特性，就是包含指数多的列( 变量) ，也就是，随 着问题规模的增大，列( 变量) 的数目将成指数增长。处理这类大规模线性规划模型， 直接采用单纯形算法求解存在着以下两个障碍：( 1 ) 列的数目成指数增长，而计算 机内存的有限性导致没有足够的空问存储所有的列，( 2 ) 找不到一个有效的算法能 够生成所有的列，如切割问题中的枚举所以的切割模式是不可能的。6 u 文已经提 1 2 东北大学硕士学位论文第二章组合最优化及列生成算法研究 到，在线性规划中，最优解中基变量的个数不可能超过约束数，因此，对于大量 的非基变量所对应的列，没有必要明确的求出和保存。列生成算法的出发点就是 基于最优解中基变量的个数不可能超过约束数这样一个事实去逾越莳面提到的两 个障碍。如果将原模型称为m p ，那么从m p 包含的列的集合中取出一些子集就可 以构成的一个限制主问题( r m p ) 。列生成的基本思想是，首先采用一些启发式得到 一个r m p ，由单纯形算法求得r m p 的晟优解和对偶最优解1 - ( 影子价格) ：再计算 检验数仃，= c 。一硝。，对于最小化问题，如果能证明对所有列的检验数部有仃。0 ， 由线性规划的对偶理论可以知道此时已经获得原问题的最优解，算法终止，如果 存在仃。 0 的列，那么，算法就通过求解新的优化问题称为子问题( s p ) 找出仃。 0 的列，并将其加入到r m p ，对r m p 重新使用单纯形算法求解；上述过程循环进 行直到满足终止条件。列生成算法流程如下图所示： 、一 幽2 14 1 1 生成算法流挂幽 f i g 2 1 f l o wc h a gf o r mo f c o l u m ng e n e r a t i o n 2 2 3 列生成算法求解线性规划 上一小节已经介绍了列生成算法的基本思想，本小节将对线性规划模型的列生 成算法的具体流程展开讨论。首先，参照相关研究文献1 9 , 1 0