基于雙邊匹配優(yōu)化模型的電廠煤炭采購及船舶運(yùn)輸調(diào)度

孫有才， 孫 卓， 林國順， 趙馨璐

（大連海事大學(xué) 交通運(yùn)輸管理學(xué)院， 遼寧 大連116026）

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

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

0 引 言

基于某電力集團(tuán)的煤炭采購—海運(yùn)調(diào)度問題研究， 現(xiàn)今集團(tuán)的煤炭采購和船舶調(diào)度仍依靠調(diào)度人員經(jīng)驗(yàn)作業(yè)， 工作效率低下， 因此， 及時(shí)快速地制定出合理的采購計(jì)劃和船舶調(diào)度直接關(guān)系集團(tuán)的業(yè)務(wù)成本、 工作效率以及企業(yè)競爭力。 所以對集團(tuán)的煤炭采購—船舶調(diào)度問題進(jìn)行全面、 系統(tǒng)的分析研究是十分必要的。

雙邊匹配早期的研究集中在婚姻匹配方面[1]， Gale 和Shapley 對男女婚配這一典型匹配問題進(jìn)行深入分析和探討， 之后有關(guān)雙邊匹配的研究逐漸興起并得以發(fā)展。 學(xué)者們運(yùn)用相關(guān)理論研究了現(xiàn)實(shí)生活中存在的雙邊匹配問題， 研究領(lǐng)域也涉及很廣。 人力資源管理領(lǐng)域， Lin[2]提出了一種兩階段的模糊多目標(biāo)決策方法來解決人與組織工作的匹配問題， 建立了混合整數(shù)規(guī)劃模型來獲得人與組織的匹配結(jié)果。 Huang 等[3]提出了基于系統(tǒng)分析來處理人員—崗位的雙邊匹配問題， 通過構(gòu)建并求解雙目標(biāo)0-1 證書規(guī)劃模型來獲得到恰當(dāng)?shù)钠ヅ浣Y(jié)果。 電子商務(wù)領(lǐng)域， 樂琦和樊治平[4]從同一研究視角出發(fā)， 引入能夠反映功利性中介悲觀度的滿意度及支付的計(jì)算公式， 提出基于Hungarian 法求解優(yōu)化模型并獲得雙邊匹配方案。 Jung 和Jo[5]在考慮多個(gè)買家與多個(gè)賣家的情況， 以買方與賣方互為值域， 以雙方的屬性是否得到滿足為約束， 將其轉(zhuǎn)化為約束滿足問題進(jìn)行求解， 開發(fā)了求解器并在房產(chǎn)中介網(wǎng)站中進(jìn)行應(yīng)用。 蔣忠中等[6]以C2C 電子商務(wù)為實(shí)際背景， 研究了在商品屬性權(quán)重信息不完全的情況下買賣雙方的雙邊匹配問題， 以最大化匹配度和交易額為目標(biāo)， 建立了雙邊匹配多目標(biāo)決策模型。 金融經(jīng)濟(jì)領(lǐng)域， 張辰彥等[7]人分析了企業(yè)知識管理系統(tǒng)柔性與環(huán)境之間的戰(zhàn)略匹配問題， 企業(yè)知識管理系統(tǒng)柔性與環(huán)境的戰(zhàn)略匹配實(shí)質(zhì)上是動態(tài)調(diào)整知識管理戰(zhàn)略與環(huán)境變化相匹配。

雖然， 匹配問題在各個(gè)領(lǐng)域研究很多， 但對于煤炭采購及船舶調(diào)度的匹配問題現(xiàn)今研究較少。 為此， 本文以某集團(tuán)為實(shí)際背景， 針對集團(tuán)業(yè)務(wù)以最大化匹配度和最小化損失費(fèi)用為目標(biāo)， 建立了兩階段雙邊匹配多目標(biāo)決策模型， 來完成煤炭采購及船舶調(diào)度。

1 問題背景

1.1 電廠需求計(jì)劃—合同資源計(jì)劃匹配

每個(gè)月末， 各個(gè)電廠根據(jù)預(yù)測需求情況上報(bào)下一個(gè)月的用煤需求計(jì)劃送至調(diào)度部， 其中電廠需求計(jì)劃主要包括電廠名稱、所需煤種及數(shù)量、 建議裝港時(shí)間、 建議到廠時(shí)間。 同時(shí)每個(gè)月末貿(mào)易部會根據(jù)需求和現(xiàn)有合同計(jì)劃制定合同計(jì)劃進(jìn)而指導(dǎo)采購貿(mào)易部隨后將合同資源計(jì)劃提交至調(diào)度部門， 其中合同資源計(jì)劃主要包括供應(yīng)商名稱、 煤種名稱及數(shù)量、 合同開始時(shí)間、 合同截至?xí)r間。 調(diào)度部收到各電廠需求計(jì)劃和合同資源計(jì)劃后進(jìn)行匹配。 匹配原則包括： 煤種匹配、 時(shí)間匹配、 數(shù)量匹配。

1.2 運(yùn)輸船舶匹配調(diào)度

根據(jù)電廠需求和合同資源匹配結(jié)果進(jìn)行二次匹配船舶調(diào)度。 船舶調(diào)度需滿足匹配度最大和損失費(fèi)用最小， 損失費(fèi)用體現(xiàn)在船舶未滿載以及船舶未按合同時(shí)間到達(dá)所產(chǎn)生的費(fèi)用， 匹配原則包括： 合同數(shù)量和船舶載重量匹配； 時(shí)間匹配。

2 數(shù)學(xué)模型

需求合同匹配模型已知條件：K表示屬性集合，N表示電廠需求集合，M合同計(jì)劃集合表示在需求i和合同j在k屬性下的匹配度，wk表示在k屬性下的權(quán)重，xij表示決策變量。

電廠需求計(jì)劃—合同資源計(jì)劃優(yōu)化匹配模型如下：

其中： （1）z1表示目標(biāo)函數(shù)匹配度最大； （2） 表示需求最多匹配一條合同； （3） 表示合同最多匹配一條需求； （4） 屬性權(quán)重約束。 式（5） 和式（6） 為模型的決策變量約束， 其中： 0-1 為整數(shù)變量， 當(dāng)xij=1 時(shí)表示需求i匹配合同j， 否則xij=0；而wk為非負(fù)的屬性權(quán)重。

船舶匹配調(diào)度模型已知條件：T表示屬性集合，N表示匹配結(jié)果集合，H表示船舶集合表示在匹配結(jié)果i和船舶h在t屬性下的匹配度表示在匹配結(jié)果i和船舶h在t屬性下的損失費(fèi)用，wt表示在t屬性下的權(quán)重，yih表示是否匹配決策變量。

船舶匹配調(diào)度優(yōu)化匹配模型如下：

其中： （7）z2目標(biāo)函數(shù)表示匹配度最大； （8）z3目標(biāo)函數(shù)損失費(fèi)用最??； （9） 表示需求合同結(jié)果最多匹配一條合同；（10） 表示船舶最多匹配一條需求合同結(jié)果； （11） 屬性權(quán)重約束。 式（12） 和式（13） 為模型的決策變量約束， 其中， 0-1為整數(shù)變量， 當(dāng)yih=1 時(shí)表示需求合同結(jié)果i和船舶h匹配， 否則yih=0； 而wt為非負(fù)的屬性權(quán)重。

對于電廠需求計(jì)劃—合同資源計(jì)劃優(yōu)化匹配模型， 通過編程（采用VBA 編程語言） 計(jì)算匹配度從而為模型的下一步

求解做準(zhǔn)備。 對于船舶匹配調(diào)度優(yōu)化模型， 首先, 同樣通過編程（采用VBA 編程語言） 計(jì)算匹配度從而為模型的下一步求解做準(zhǔn)備。 其次， 求解各個(gè)單目標(biāo)下的最優(yōu)值， 可利用LINGO 軟件求解。 最后， 將模型的多目標(biāo)轉(zhuǎn)換為單目標(biāo)并求解。 多目標(biāo)決策模型的求解方法有多種[8]， 其中一種有效的方法是將多目標(biāo)轉(zhuǎn)換成單目標(biāo)進(jìn)行求解。 由于模型中兩個(gè)目標(biāo)函數(shù)的量綱不一致， 因而需要對其進(jìn)行標(biāo)準(zhǔn)化處理[9]， 模型中的兩個(gè)目標(biāo)具有同樣的重要性， 進(jìn)而構(gòu)造新的目標(biāo)函數(shù)替代模型中由（7） 和（8） 表示的兩個(gè)目標(biāo)函數(shù)， 此時(shí)， 便得到了相應(yīng)的單目標(biāo)的混合0-1 整數(shù)的二次規(guī)劃模型， 該單目標(biāo)模型亦可利用LINGO 軟件求解， 從而得到最優(yōu)的雙邊匹配對。

3 算例分析

以某電力集團(tuán)為例。 由于實(shí)際業(yè)務(wù)量大， 對電廠、 供應(yīng)商、 船舶數(shù)量等降低算例規(guī)模， 采用電廠數(shù)信息10 條記錄如表1所示、 供應(yīng)商信息15 條記錄如表2 所示、 船舶信息13 條記錄如表3 所示。

表1 電廠需求

表2 合同計(jì)劃

表3 船舶信息

需求—合同匹配： 共有3 個(gè)屬性， 分別是煤種（w1）、 數(shù)量（w2）、 時(shí)間（w3）各個(gè)屬性權(quán)重關(guān)系約束需滿足w1 ≥w3 ≥w2,w2≥0.1， 匹配求解結(jié)果如表4 所示。

船舶調(diào)度： 共有2 個(gè)屬性， 分別是數(shù)量（w4）、 時(shí)間（w5）各個(gè)屬性權(quán)重關(guān)系約束需滿足w5 ≥w4,w4 ≥0.2， 匹配求解結(jié)果如表4 所示。

4 結(jié) 論

本文以某電力集團(tuán)為例， 研究分析電力集團(tuán)所屬電廠燃料煤炭的需求計(jì)劃與合同資源計(jì)劃的匹配問題， 以及調(diào)度部門如何合理完成船舶的運(yùn)輸調(diào)度。 通過兩階段雙邊匹配優(yōu)化完成采購及船舶調(diào)度， 效果較好， 可達(dá)到提高集團(tuán)業(yè)務(wù)效率與降低成本目的。 下一階段的主要任務(wù)是把優(yōu)化模型使用動態(tài)語言在B/S 架構(gòu)下實(shí)現(xiàn)， 實(shí)現(xiàn)集團(tuán)業(yè)務(wù)的智能化和可視化。

表4 需求—合同匹配—船舶調(diào)度計(jì)劃

[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]. 管理科學(xué)， 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] 蔣忠中， 盛瑩， 樊治平,等. 屬性權(quán)重信息不完全的雙邊匹配多目標(biāo)決策模型的研究[J]. 運(yùn)籌與管理， 2008,17(4):138-142.

[7] 張辰彥， 吳冰， 劉仲英. 企業(yè)知識管理系統(tǒng)柔性與環(huán)境不確定性的匹配度計(jì)算模型[J]. 管理學(xué)報(bào)， 2007,4(4):393-395.

[8] 林銼云， 董加禮. 多目標(biāo)優(yōu)化的方法與理論[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.