改进模拟退火算法求解煤场配煤优化问题

屈国强

（河南理工大学　经济管理学院，河南　焦作　454000）

改进模拟退火算法求解煤场配煤优化问题

屈国强

（河南理工大学经济管理学院，河南焦作454000）

从混煤与单煤特性参数之间呈线性关系出发，不考虑优质煤种的使用限制，建立了煤场配煤优化问题的数学模型。在此基础上，通过把此问题归结为多维背包问题，表明其求解性质是NP-难的。为充分利用邻域信息，在模拟退火算法中嵌入邻域搜索，促使算法加快收敛。数据试验表明改进算法是有效的。

煤场；配煤；模拟退火算法

1　引言

我国煤炭产需呈逆向分布，形成“西煤东调”和“北煤南运”，大部分煤炭需要经过长途运输才能到达消费地。同时，由于赋存各异，不同煤矿的煤质也不相同，单一煤种往往不能满足用户的要求。这就需要通过配煤，将煤场库存的、不同的煤炭按一定比例进行掺配，即满足用户要求，又可扬长避短、物尽其用。

文献［1］指出水分、灰分、挥发分、硫分、发热量是评价煤质的主要指标，是计算配比的基础。关于配煤与单煤这几个主要指标之间是否具有线性可加性，目前有三种观点。第一种认为主要指标之间具有线性可加性。文献［2］从工业分析的角度，实验表明水分、灰分、挥发分、硫分、发热量分析基具有线性可加性。文献［3］作为动力配煤的指导原则，指出灰分、挥发分、发热量、硫分收到基4个指标可以线性加权计算。文献［4］对于国家标准《动力配煤规范》进行了解析，认为煤炭的常规指标灰分、挥发分、硫分、发热量具有较好的线性可加性。以此为基础，文献［3］建立了以发热量等为约束的线性规划模型，采用LINGO软件求解。文献［5］在遗传算法中嵌入模拟退火求解。文献［6］用加权系数法将煤质主要指标作为目标函数，转换为单目标函数后用粒子群算法求解。

第二种观点认为主要指标之间呈现非线性关系。文献［7］利用RBF神经网络建立配煤煤质预测模型，采用基于自适应罚函数的正交遗传算法优化。文献［8］采用Elman神经网络预测配煤煤质后引入模拟退化算法求解。文献［9］用BP人工神经网络实现煤质信息的非线性映射，采用均匀设计建立适应度函数，利用遗传算法寻优。

第三种观点认为主要指标之间呈现线性与非线性加权关系尚不明确。文献［10］认为在煤质参数随机波动的不确定条件下，采用确定性动力配煤模型很难保证实际配煤的产品质量。因而采用区间规划与机会约束规划相结合，建立一个不确定性机会约束的非线性优化的配煤优化模型，然后转化为2个确定性子模型求解。文献［11］回避混煤与组成单煤特性参数之间的关系，采用带精英策略的非支配排序遗传算法求解。文献［12］将灰分误差最小等作为约束条件，运用加权平均将约束条件转化为单目标函数，采用协同量子粒子群算法寻优。

此外，文献［13］指出根据煤炭混合性质及行业惯例，一般选取3种煤掺配。文献［14］指出已有算法只能对掺配比例而不能对掺配煤种进行优化。文献［15］指出实际应用时要求稳定、准确和实时，当问题规模较大时，启发式算法或智能优化算法成为必然选择。文献［16］指出对于混煤煤质分析数据一般采用算数加权平均计算或试验获得，在缺乏混煤试验数据的情况下成为当然的选择。

2　问题描述及其模型

2.1问题描述

某煤场有m种单煤，其中单煤i（i=1，2，…，m）低位发热量、硫排放、收到基水分、收到基灰分和收到基挥发份分别是Qnet，i、Sar，i、Mar，i、Aar，i、和Var，i，重量和价格分别是Wi和Pi。现接到1份订单，这份订单要求的低位发热量、硫排放、收到基水分、收到基灰分和收到基挥发份分别是Qnet'、Sar'、Mar'、Aar'和Var'，重量是W'。由于配煤工艺限制，只能从m种单煤中最多选择b种单煤掺配，确定这b种单煤的掺配比例xi，使得配煤满足订单要求，且成本最小。

一般情况下，煤场库存各种单煤的数量都是较大的。为使问题简化，这里假设库存各种单煤的重量Wi远远超过订单要求的重量W'。

2.2数学模型

目标函数（1）表示最小化配煤的成本。约束条件（2）表示掺配的单煤种类限制，最多选择3种单煤进行参配，其中[xi]表示大于或等于xi的最小整数；约束条件（3）表示比例约束，构成订单的各种掺配煤的比例之和等于1；约束条件（4）、（5）和（6）分别表示混煤的硫排放、收到基水分、收到基灰分不能超过订单的要求；约束条件（7）和（8）分别表示混煤的收到基挥发份和低位发热量不能低于订单的要求；约束条件（9）表示库存各种单煤的数量远远超过订单要求的数量；约束条件（10）表示决策变量xi取值范围，其中xi=1表示订单全部由单煤i组成，xi=0表示单煤i不参与掺配。

在上述模型中，决策变量xi共有m个。其中，最多有m-1个决策变量取0，最少有m-b个决策变量取0；最多有b个、最少有0个决策变量取值大于零且小于1；最多有1个决策变量取值等于1。因此，这是一个混合整数线性规划模型。

假设已经选定了b种煤进行掺配，则上述模型退化为一个线性规划模型，较易求解。因此，上述模型求解的难点在于如何在m个决策变量中选出符合约束要求的b个非零的决策变量。

2.3背包问题与所求问题计算性质n

2.3.1背包问题。假定有n个物体和一个背包，物体i有质量wi，价值为pi，而背包的载荷能力为M。若将物体i的一部分xi（1≤i≤n，0≤xi≤1）装入背包中，则有价值在约束条件下，使目标函数极大，此处0≤xi≤1，pi＞0，1≤i≤n。这个问题称为背包问题（knapsack problem，KP）［17］。

2.3.2问题计算性质

性质：煤场配煤优化问题的计算性质是NP-难的。

证明：在煤场配煤优化问题中，可以把每种单煤映射为一个物体，单煤的硫分、水分、灰分、挥发份和发热量分别映射为这个物体属性的5个维度。同时，把订单映射为一个背包，订单的硫分、水分、灰分、挥发份和发热量分别映射为装入背包后物品5个维度累积的约束，订单的重量映射为这个背包的载荷能力。这样，煤场配煤优化问题就可以映射为5维约束的背包问题。

多维背包问题是典型的组合优化问题，计算性质是NP-难的，煤场配煤优化问题的计算性质必然也是NP-难的。

3　算法实现步骤

模拟退火（Simulated Annealing，SA）算法是基于Mente Carlo迭代求解的一种全局概率型搜索算法，是对邻域搜索算法的扩展。与一般邻域搜索算法不同，SA算法以一定的概率选择邻域中目标值相对较小的状态，能够在多项式时间内给出一个近似最优解［18］。当待解决的问题复杂性较高而且规模较大时，特别是对问题的邻域知识了解甚少的情况下，采用SA算法最合适。

（1）初始解生成方法。为了增强初始解的随机性及克服初值依赖性，在所有掺配煤种中，随机选取3种煤生成初始解。这个初始解可能是可行解，也可能是非可行解。但是，随着迭代的进行，非可行解将逐渐被淘汰，搜索的区域将逐渐集中到可行解分布的区域。

（2）邻域策略。采用交换的策略产生邻域解。例如，在一次邻域搜索过程中，当前解掺配煤种是（2，5，8），未参与配煤的煤种是（1，3，4，6，7，9，10）。取出煤种2，分别放入煤种1、3、4、6、7、9和10，构成了掺配煤种（2，5，8）的7个邻域解，类似的邻域解共有21个。对于不满足约束，即不满足订单要求的非可行解，不再搜索其邻域，使搜索空间减小，加快搜索进程。

（3）新解产生机制。新解的产生分两步进行：

第一步：为加快收敛速度，找到局部最优解，搜索当前解的7个邻域，若目标函数有改进，则替换为新的当前解；否则不替换。

第二步：为增强新解的随机性，避免陷入局部最优，在当前解的基础上，随机取出一种掺配煤种，再随机放入一种未掺配煤种。若目标函数有改进，则替换为新的当前解；否则采用Metropolis准则确定是否接受这个新解。即若min｛1，exp（-Δprice/t）｝＞random［0，1］，则接受；否则拒绝。其中，Δprice是当前配煤方案和新产生的配煤方案的成本差，t是当前温度。

（4）降温方法

①初始温度。初始温度的确定应折中考虑优化质量和优化效率。为此，采用t0=-（Pricemax-Pricemin）/log10pr计算初始温度。其中，Pricemax和Pricemin分别是掺配煤种的最高和最低价格，pr是初始接受概率。

②降温函数。采用的降温函数是Tk+1=Tk·r，其中，r是降温系数。

③每一温度迭代步长。采用固定的迭代步长l，迭代步长等于掺配煤种数。

（5）终止准则。在相同的温度内，得到的当前解连续若干步迭代没有改进，或温度下降到终止温度，迭代终止。本文确定的没有改进的迭代步长等于掺配煤种数。

上述算法涉及到的参数包括初始温度t0、初始接受概率pr、降温系数r、迭代步长l、在相同温度内得到的当前解没有改进的连续迭代步数d、终止温度tmin。

4　计算试验与分析

采用MATLAB2013a在IntelCore/i5-3470/CPU3.0GHz/ RAM4.0GB上编程试验。

4.1计算数据

截止目前，煤场配煤优化问题尚没有一个统一的比较算例，本文采用文献［19］中10种原煤的数据进行计算说明。订单要求：Qnet'≥23.0MJ/kg，Var'≥25% ，Sar'≤1.0%，Mar'≤10%，Aar'≤30%。

采用穷举法计算，得知：（1）解空间大小为720个，实际上不可行解有40个，可行解有34个。其中，一种煤直接销售的可行解有2个，2种和3种煤掺配的可行解分别有17个和15个。（2）最优解仅有一个，由煤种3、7、9按13.75%、22.67%和63.57%掺配，成本287.491 0，Qnet'=24.4MJ/kg，Var'=25.0%，Sar'=1.0%，Mar'=2.5%，Aar'=19.7%。（3）平均耗时5.99s。

4.2计算结果与分析

目前，SA算法参数的确定没有一个统一的方法，参数的选择仍然依赖于一些启发式准则和待求解问题的性质。结合实际问题数据，经过多次计算和试验，设定参数如下：t0=65、pr=0.1、r=0.9、l=10、tmin=0.1，d=10。

为简便起见，将上述算法命名为SA1。作为对比，将SA1中去掉邻域搜索部分的算法命名为SA2。

在相同条件下，采用SA1和SA2分别进行10轮试验，每轮试验进行200次，每次试验均找到了最优解。实验结果见表1。可以看到，SA1比SA2平均耗时降低56.35%，标准差降低69.10%，表明SA1比SA2计算速度快且稳定。

究其原因，SA2在产生新解的时候，没有利用任何当前解邻域的信息，进行的是“盲跳”；SA1则充分利用了当前解交换邻域的信息，对当前解的交换邻域进行了系统的搜索，找到局部最优解，促使SA算法从一个目标函数更小的区域“起跳”，“下山”速度加快了。因此，SA1计算速度更快且稳定性提高了。

表1　SA1和SA2计算耗时（单位：s）

5　结束语

优化配煤即可以满足客户需求、提高经济效益，又可以促进配煤理论的发展，具有一定的实践价值和理论意义。本文把煤场配煤优化问题归结为多维背包问题，表明其求解性质是NP-难的。为充分利用邻域信息，在SA算法中嵌入邻域搜索，促使SA算法加快收敛。下一步将重点研究面向多订单的煤场配煤优化问题及其高效算法。

［1］戴财胜.动力配煤的理论与应用研究［D］.北京:中国矿业大学（北京校区），2000.

［2］陈亚飞，陈怀珍，崔风海.煤炭行业标准《动力配煤导则》［J］.煤质技术，2006，（5）:17-19.

［3］姜英.国家标准《动力配煤规范》的制定与实施［J］.煤质技术，2012，（1）:1-3.

［4］郭德铭.平顶山煤业集团配煤优化方案研究［D］.北京:北京交通大学，2009.

［5］Xi J G，Ming C，Jia W W.Coal blending optimization of coal preparation production process based on improved GA［J］. Procedia Earth and Planetary science，2009，（1）:654-660.

［6］刘永江，高正平，韩义，等.基于粒子群算法的火电厂优化配煤研究［J］.锅炉技术，2012，43（5）:18-24.

［7］夏季，陆攀，华志刚，等.电站锅炉全局优化智能配煤模型的建立及系统开发［J］.动力工程学报，2010，30（7）:512-517.

［8］刘艳军.电厂动力配煤煤质预测模型与优化模型研究［D］.长沙:中南大学，2011.

［9］刘玉娇，张海英，关海盈.基于多种算法的多目标配煤优化方法［J］.热力发电，2014，43（9）:108-112.

［10］张晓萱，黄国和，席北斗，等.电厂优化的不确定性机会约束非线性规划方法［J］.中国机电工程学报，2009，29（5）:11-15.

［11］夏季，华志刚，彭鹏，等.基于非支配排序遗传算法的无约束多目标优化配煤模型［J］.中国机电工程学报，2011，31（2）:85-90.

［12］董虎胜，陆萍，钟宝江.基于协同量子粒子群的自动配煤系统研究［J］.制造业自动化，2014，36（1）:74-77.

［13］刘丽敏.肥城煤炭配送中心配煤模型研究［D］.青岛:山东科技大学，2011.

［14］孙云峰，王国华.一种新型煤炭物流节点-“煤炭超市”的生产计划建模［J］.物流技术，2007，26（11）:94-96.

［15］周俊虎，沈彬彬，陈寅彪，等.基于遗传算法的动力配煤的Boltzmann优化模型的研究［J］.动力工程，2003，23（4）:547-551.

［16］阮伟，周俊虎，汤龙华，等.优化配煤理论的研究以及配煤专家系统多目的开发［J］.动力工程，1999，19（6）:434-437.

［17］宋文，吴晟，杜亚军.算法设计与分析［M］.重庆:重庆大学出版社，2001.

［18］汪定伟，王俊伟，王洪峰，等.智能优化方法［M］.北京:高等教育出版社，2007.

［19］殷春根，周俊虎，骆仲泱，等.人工神经网络方法在优化动力配煤中的应用研究［J］.煤炭学报，1997，22（4）:343-348.

Solution of Coal Yard Scheduling Optimization Problem Using Improved Simulated Annealing Algorithm

Qu Guoqiang
（School of Economics&Management，Henan Polytechnic University，Jiaozuo 454000，China）

In this paper，we established the mathematical model for the optimization of the coal yard scheduling problem without considering the limitation for the use of the high-quality coal varieties.Then on such basis，we classified the problem as a multi-dimensional packing problem and demonstrated that it was a NP-hard problem.Next，we incorporated the neighborhood search algorithm into the simulated annealing algorithm to accelerate its convergence.A numerical example at the end showed that the algorithm was effective.

coal yard；coal scheduling；simulated annealing algorithm

TQ520.62；F224

A

1005-152X（2016）06-0090-04

10.3969/j.issn.1005-152X.2016.06.020

2016-04-12

国家自然科学基金“科学采矿视域中我国煤炭成本缺失与完全补偿的理论与实证研究”（51304066）；河南省政府决策研究招标一般课题“新常态视阈下河南先进制造业发展模式和路径选择研究”（2015B117）；河南省教育厅科学技术研究重点项目软科学计划项目“煤炭供应链构建及其计划与调度优化研究”（14B630009）；河南理工大学博士基金项目“面向订单的煤炭供应链计划与调度智能优化研究”（SZB2013-34）

屈国强（1970-），男，河南义马人，博士，讲师，硕士生导师，主要研究方向：煤炭物流与供应链、生产计划与调度、智能优化算法等。