基于双边匹配优化模型的电厂煤炭采购及船舶运输调度

孙有才， 孙 卓， 林国顺， 赵馨璐

（大连海事大学 交通运输管理学院， 辽宁 大连116026）

SUN You-cai, SUN Zhuo, LIN Guo-shun, ZHAO Xin-lu

(Transportation Management College, Dalian Maritime University, Dalian 116026, China)

0 引 言

基于某电力集团的煤炭采购—海运调度问题研究， 现今集团的煤炭采购和船舶调度仍依靠调度人员经验作业， 工作效率低下， 因此， 及时快速地制定出合理的采购计划和船舶调度直接关系集团的业务成本、 工作效率以及企业竞争力。 所以对集团的煤炭采购—船舶调度问题进行全面、 系统的分析研究是十分必要的。

双边匹配早期的研究集中在婚姻匹配方面[1]， Gale 和Shapley 对男女婚配这一典型匹配问题进行深入分析和探讨， 之后有关双边匹配的研究逐渐兴起并得以发展。 学者们运用相关理论研究了现实生活中存在的双边匹配问题， 研究领域也涉及很广。 人力资源管理领域， Lin[2]提出了一种两阶段的模糊多目标决策方法来解决人与组织工作的匹配问题， 建立了混合整数规划模型来获得人与组织的匹配结果。 Huang 等[3]提出了基于系统分析来处理人员—岗位的双边匹配问题， 通过构建并求解双目标0-1 证书规划模型来获得到恰当的匹配结果。 电子商务领域， 乐琦和樊治平[4]从同一研究视角出发， 引入能够反映功利性中介悲观度的满意度及支付的计算公式， 提出基于Hungarian 法求解优化模型并获得双边匹配方案。 Jung 和Jo[5]在考虑多个买家与多个卖家的情况， 以买方与卖方互为值域， 以双方的属性是否得到满足为约束， 将其转化为约束满足问题进行求解， 开发了求解器并在房产中介网站中进行应用。 蒋忠中等[6]以C2C 电子商务为实际背景， 研究了在商品属性权重信息不完全的情况下买卖双方的双边匹配问题， 以最大化匹配度和交易额为目标， 建立了双边匹配多目标决策模型。 金融经济领域， 张辰彦等[7]人分析了企业知识管理系统柔性与环境之间的战略匹配问题， 企业知识管理系统柔性与环境的战略匹配实质上是动态调整知识管理战略与环境变化相匹配。

虽然， 匹配问题在各个领域研究很多， 但对于煤炭采购及船舶调度的匹配问题现今研究较少。 为此， 本文以某集团为实际背景， 针对集团业务以最大化匹配度和最小化损失费用为目标， 建立了两阶段双边匹配多目标决策模型， 来完成煤炭采购及船舶调度。

1 问题背景

1.1 电厂需求计划—合同资源计划匹配

每个月末， 各个电厂根据预测需求情况上报下一个月的用煤需求计划送至调度部， 其中电厂需求计划主要包括电厂名称、所需煤种及数量、 建议装港时间、 建议到厂时间。 同时每个月末贸易部会根据需求和现有合同计划制定合同计划进而指导采购贸易部随后将合同资源计划提交至调度部门， 其中合同资源计划主要包括供应商名称、 煤种名称及数量、 合同开始时间、 合同截至时间。 调度部收到各电厂需求计划和合同资源计划后进行匹配。 匹配原则包括： 煤种匹配、 时间匹配、 数量匹配。

1.2 运输船舶匹配调度

根据电厂需求和合同资源匹配结果进行二次匹配船舶调度。 船舶调度需满足匹配度最大和损失费用最小， 损失费用体现在船舶未满载以及船舶未按合同时间到达所产生的费用， 匹配原则包括： 合同数量和船舶载重量匹配； 时间匹配。

2 数学模型

需求合同匹配模型已知条件：K表示属性集合，N表示电厂需求集合，M合同计划集合表示在需求i和合同j在k属性下的匹配度，wk表示在k属性下的权重，xij表示决策变量。

电厂需求计划—合同资源计划优化匹配模型如下：

其中： （1）z1表示目标函数匹配度最大； （2） 表示需求最多匹配一条合同； （3） 表示合同最多匹配一条需求； （4） 属性权重约束。 式（5） 和式（6） 为模型的决策变量约束， 其中： 0-1 为整数变量， 当xij=1 时表示需求i匹配合同j， 否则xij=0；而wk为非负的属性权重。

船舶匹配调度模型已知条件：T表示属性集合，N表示匹配结果集合，H表示船舶集合表示在匹配结果i和船舶h在t属性下的匹配度表示在匹配结果i和船舶h在t属性下的损失费用，wt表示在t属性下的权重，yih表示是否匹配决策变量。

船舶匹配调度优化匹配模型如下：

其中： （7）z2目标函数表示匹配度最大； （8）z3目标函数损失费用最小； （9） 表示需求合同结果最多匹配一条合同；（10） 表示船舶最多匹配一条需求合同结果； （11） 属性权重约束。 式（12） 和式（13） 为模型的决策变量约束， 其中， 0-1为整数变量， 当yih=1 时表示需求合同结果i和船舶h匹配， 否则yih=0； 而wt为非负的属性权重。

对于电厂需求计划—合同资源计划优化匹配模型， 通过编程（采用VBA 编程语言） 计算匹配度从而为模型的下一步

求解做准备。 对于船舶匹配调度优化模型， 首先, 同样通过编程（采用VBA 编程语言） 计算匹配度从而为模型的下一步求解做准备。 其次， 求解各个单目标下的最优值， 可利用LINGO 软件求解。 最后， 将模型的多目标转换为单目标并求解。 多目标决策模型的求解方法有多种[8]， 其中一种有效的方法是将多目标转换成单目标进行求解。 由于模型中两个目标函数的量纲不一致， 因而需要对其进行标准化处理[9]， 模型中的两个目标具有同样的重要性， 进而构造新的目标函数替代模型中由（7） 和（8） 表示的两个目标函数， 此时， 便得到了相应的单目标的混合0-1 整数的二次规划模型， 该单目标模型亦可利用LINGO 软件求解， 从而得到最优的双边匹配对。

3 算例分析

以某电力集团为例。 由于实际业务量大， 对电厂、 供应商、 船舶数量等降低算例规模， 采用电厂数信息10 条记录如表1所示、 供应商信息15 条记录如表2 所示、 船舶信息13 条记录如表3 所示。

表1 电厂需求

表2 合同计划

表3 船舶信息

需求—合同匹配： 共有3 个属性， 分别是煤种（w1）、 数量（w2）、 时间（w3）各个属性权重关系约束需满足w1 ≥w3 ≥w2,w2≥0.1， 匹配求解结果如表4 所示。

船舶调度： 共有2 个属性， 分别是数量（w4）、 时间（w5）各个属性权重关系约束需满足w5 ≥w4,w4 ≥0.2， 匹配求解结果如表4 所示。

4 结 论

本文以某电力集团为例， 研究分析电力集团所属电厂燃料煤炭的需求计划与合同资源计划的匹配问题， 以及调度部门如何合理完成船舶的运输调度。 通过两阶段双边匹配优化完成采购及船舶调度， 效果较好， 可达到提高集团业务效率与降低成本目的。 下一阶段的主要任务是把优化模型使用动态语言在B/S 架构下实现， 实现集团业务的智能化和可视化。

表4 需求—合同匹配—船舶调度计划

[1] Gale D, Sotomayor M. Some remarks on the stable matching Problem[J]. Discrete Applied Mathematics, 1985,11(3):223-232.

[2] Lin H T. A job Placement intervention using fuzzy approach for two-way choice[J]. Expert Systems with Applications,2009,36(2):2543-2553.

[3] Huang D K, Chiu H N, Yeh R H, Chang J H. A fuzzy multi-criteria decision making approach for solving a bi-objective personnel assignment Problem[J]. Computers & Industrial Engineering, 2009,56(1):l-10.

[4] 乐琦， 樊治平. 基于悲观度的双边匹配决策问题研究[J]. 管理科学， 2012,25(2):112-120.

[5] Jung J J, Jo G S. Brokerage between buyer and seller agents using constraint satisfaction problem models[J]. Decision Support Systems, 2000,28:293-304.

[6] 蒋忠中， 盛莹， 樊治平,等. 属性权重信息不完全的双边匹配多目标决策模型的研究[J]. 运筹与管理， 2008,17(4):138-142.

[7] 张辰彦， 吴冰， 刘仲英. 企业知识管理系统柔性与环境不确定性的匹配度计算模型[J]. 管理学报， 2007,4(4):393-395.

[8] 林锉云， 董加礼. 多目标优化的方法与理论[M]. 长春： 吉林教育出版社， 1992:55-167.

[9] Zhou G G, Min H, Gen M. Agenetic algorithm approach to the bicriterial allocation of customers to ware houses[J]. International Journal Production Economics, 2003,86(1):35-45.