基于多目標(biāo)規(guī)劃的礦車調(diào)度優(yōu)化模型

馮陽陽

（西安外事學(xué)院工學(xué)院 陜西 西安 710077）

鋼鐵工業(yè)是國家工業(yè)的基礎(chǔ)之一，鐵礦是鋼鐵工業(yè)的主要原料基地。許多現(xiàn)代化鐵礦是采用露天開采形式，其生產(chǎn)主要是由各種大型采礦設(shè)備間的配合來完成的。隨著露天礦產(chǎn)量規(guī)模的不斷擴(kuò)大及設(shè)備大型化、機(jī)械化、自動化程度的不斷提高，采運(yùn)成本占礦山生產(chǎn)成本的比例也越來越高，優(yōu)化車隊(duì)運(yùn)行、準(zhǔn)確執(zhí)行生產(chǎn)計劃，以提高礦山產(chǎn)量，節(jié)約費(fèi)用，取得較高經(jīng)濟(jì)效益顯得尤為重要?？梢哉f，在采運(yùn)過程中運(yùn)輸組織方案的優(yōu)劣，會直接影響到鋼鐵工業(yè)的經(jīng)濟(jì)效益。也就是說，提高這些大型采礦和運(yùn)輸設(shè)備的利用率是增加露天礦經(jīng)濟(jì)效益的首要任務(wù)。因此，如何通過合理的調(diào)度組織來提高這些露天卡車的工作效率就成為提高露天礦業(yè)經(jīng)濟(jì)利潤的重中之重。通常來說，交通對于經(jīng)濟(jì)的作用主要是良好的交通狀況帶來了機(jī)動化程度的增長從而節(jié)約了運(yùn)輸時間、降低了運(yùn)費(fèi)、降低了產(chǎn)品的成本、促進(jìn)了物資的流通、帶動了地區(qū)間的交流等。

露天礦是在基建和生產(chǎn)過程中逐漸形成的?；〞r期的任務(wù)是建立供電供水系統(tǒng)及建立運(yùn)輸干線，修建選礦廠、排土場及機(jī)修廠等主要構(gòu)筑物和設(shè)施，以及完成投產(chǎn)時所必需的采準(zhǔn)和剝離工程量。在生產(chǎn)過程中，為了完成計劃的年礦石生產(chǎn)任務(wù)，必須按時完成一定的開拓、采準(zhǔn)、剝離的工程量。露天礦在開采過程中，必須將境界內(nèi)的礦、巖劃分成一定厚度的水平分層，以便由上向下逐層進(jìn)行開采，這些階梯塊的工作面叫做臺階。每個臺階大多使用獨(dú)立的穿孔和采掘設(shè)備。由于露天開采在采出礦石的同時，必須剝離一定數(shù)量的巖石。而且，剝離巖石量的多少直接影響采出礦石的成本和單位投資額，并且隨著礦山開采深度變化往往剝離巖石的數(shù)量也是變化的。而這些礦石與巖石的搬卸運(yùn)輸就成了露天礦場經(jīng)濟(jì)利益中最為重要的一環(huán)。本文將利用優(yōu)化模型中整數(shù)優(yōu)化的思想[1]針對這一問題展開詳細(xì)討論。

1 礦車運(yùn)輸組織模型的模型分析

礦車運(yùn)輸組織本質(zhì)上屬于貨運(yùn)車輛運(yùn)行調(diào)度問題，而此問題正式貨運(yùn)企業(yè)運(yùn)輸生產(chǎn)管理活動中一個非常重要的組成部分。車輛運(yùn)行調(diào)度工作是以車輛的運(yùn)行為中心，不但是高質(zhì)量完成預(yù)定的貨運(yùn)任務(wù)的保證，而且通過車輛運(yùn)行作業(yè)計劃的實(shí)施也將企業(yè)內(nèi)部各生產(chǎn)環(huán)節(jié)（特別是車隊(duì)、車間裝卸部門等）連接成一個有機(jī)的整體[2]。交通運(yùn)輸組織是通過交通規(guī)劃的手段有計劃的引導(dǎo)交通的一系列運(yùn)動，即規(guī)劃者如何提示各種目標(biāo)。事實(shí)上，運(yùn)輸組織可以理解為有限的道路空間上綜合運(yùn)用交通規(guī)劃、交通限制和管理等手段，科學(xué)有效的地分時、分路、分車種、分流向使用道路，使交通狀況始終處于有序、高效運(yùn)行狀態(tài)。其用意在于分解車流矛盾。一般好的交通組織主要考慮在時間上削峰填谷，避免空間上過于稀疏或者過于擁擠，體現(xiàn)出矛盾分散、時空均分的原則。一般對于道路通行時空資源的分配優(yōu)化，重點(diǎn)是要解決通行能力、路權(quán)分配問題以及路網(wǎng)負(fù)荷均分問題。

貨車運(yùn)行調(diào)度工作主要內(nèi)容包括：檢查貨運(yùn)生產(chǎn)前的作業(yè)準(zhǔn)備情況；檢查車輛運(yùn)行作業(yè)計劃的執(zhí)行情況；根據(jù)車輛的技術(shù)狀況和所處狀態(tài)，科學(xué)合理的調(diào)配車輛，提高車輛運(yùn)用水平；根據(jù)主要物資的流量、流向及其變化規(guī)律，加強(qiáng)回程貨源的組織工作，提高車輛運(yùn)行水平；根據(jù)營運(yùn)區(qū)域內(nèi)的道路和交通情況，及時調(diào)整車輛的運(yùn)行線路；合理調(diào)配勞動力，加強(qiáng)勞動組織工作；運(yùn)用現(xiàn)代信息技術(shù)，對車輛和貨物進(jìn)行跟蹤和實(shí)時控制。

對于礦車運(yùn)輸調(diào)度優(yōu)化問題來說一般主要考慮兩方面的因素。首先，它要求單位路程總運(yùn)量最大；其次，要求動用的載貨車量數(shù)最少?？梢姷V車運(yùn)輸調(diào)度計劃編制這類問題的難點(diǎn)在于，如果礦車數(shù)量過少，那么礦產(chǎn)的運(yùn)輸效率將大幅度降低；相反，如果礦車數(shù)量太多，又會出現(xiàn)礦車現(xiàn)在浪費(fèi)投資的現(xiàn)象。不難看出，礦車運(yùn)輸調(diào)度優(yōu)化問題實(shí)際上可以看作是一個多目標(biāo)優(yōu)化問題[3-5]。從數(shù)學(xué)的角度來說，由于多目標(biāo)規(guī)劃其各個子目標(biāo)之間往往是相互矛盾的（例如：我們既想礦車數(shù)量少，又想總運(yùn)量最大），因此通常來說多目標(biāo)問題的最大的特點(diǎn)就是不易獲取其全局最優(yōu)解。除此之外，礦產(chǎn)車輛的運(yùn)輸調(diào)度過程中往往還存在著，待優(yōu)化變量規(guī)模大（即，礦產(chǎn)車輛的數(shù)量大、種類多）不易高效求解的問題。在現(xiàn)實(shí)中為了解決這類問題，人們往往采取貪心準(zhǔn)則的優(yōu)化策略，這樣做的好處是，貪心準(zhǔn)則的算法復(fù)雜度低，便于在實(shí)際中實(shí)現(xiàn)。但是貪心算法只能獲得局部最優(yōu)解而非全局最優(yōu)解，這就會對實(shí)際生產(chǎn)中礦車運(yùn)輸調(diào)度的效率帶來嚴(yán)重的影響。為了從本質(zhì)上解決目前礦車運(yùn)輸調(diào)度存在的問題，本文提出了一種基于多目標(biāo)規(guī)劃思想的礦車運(yùn)輸調(diào)度優(yōu)化模型。

在建立模型前，我們首先需要做幾個模型基本的假設(shè)：1）假設(shè)卡車在鏟點(diǎn)和卸點(diǎn)不存在等待排隊(duì)現(xiàn)象；2）各個裝卸點(diǎn)均達(dá)到規(guī)定產(chǎn)量；3）不考慮卡車存在偶然的交通事故。在這3條假設(shè)的基礎(chǔ)上，我們將在下一節(jié)中介紹本文所提出的數(shù)學(xué)模型。

2 礦車運(yùn)輸調(diào)度優(yōu)化模型的建立

在上一節(jié)中我們提到，礦車的運(yùn)輸組織及運(yùn)行調(diào)度主要考慮2個因素，即單位路程總運(yùn)量和運(yùn)輸作業(yè)中動用的載貨車輛數(shù)。也就是說，該優(yōu)化問題至少存在兩個優(yōu)化目標(biāo)，且兩個決策要求各有其合理性；同時在做最終決策時，無需強(qiáng)調(diào)絕對意義上的最優(yōu)性，因而我們需構(gòu)造一種更適用于實(shí)際決策過程的優(yōu)化模型。此外，我們優(yōu)化模型參與的參量主要包括礦車數(shù)量，礦產(chǎn)量以及單位單位路程上的礦石運(yùn)輸量。

下面首先針對第一個優(yōu)化目標(biāo)——單位路程總運(yùn)量最大，建立數(shù)學(xué)模型，見式（1）。

其中，f1（Xij，dij）=Xij/dij；f2（Gj，β）=Gj/β；f3（C，β）=Ci/β；β是卡車的運(yùn)載量；Xij是第i個鏟點(diǎn)到第j個卸點(diǎn)的運(yùn)載次數(shù)；dij是第i個鏟點(diǎn)到第j個卸點(diǎn)的距離；ωij是加權(quán)系數(shù)；Gj是第j個卸點(diǎn)的產(chǎn)量；Ci是第i個鏟點(diǎn)的產(chǎn)量；T為動用卡車的數(shù)量；K卡車數(shù)量的上限。

這里有必要對上述模型做簡要的說明。首先式（1）所給出的優(yōu)化模型中，其代價函數(shù)所描述的是要求所有卡車的總的運(yùn)輸量最小，也就單位路程總運(yùn)量最大。因?yàn)樵谛枰\(yùn)送礦石的總量不變的情況下，距離越近則意味著總運(yùn)量就越小。換句話說，本優(yōu)化目標(biāo)的含義是要求所有載貨車輛以最短的路徑進(jìn)行貨物運(yùn)輸工作。此外，對于模型中約束條件簡要解釋，第一個約束條件是要求第個卸點(diǎn)的總產(chǎn)量必須大于或等于此卸點(diǎn)產(chǎn)量的約束；第2個約束條件是要求第個鏟點(diǎn)運(yùn)送的礦石量小于該鏟點(diǎn)的產(chǎn)量；最后一個約束條件是要求卡車的數(shù)量不能超過所能采用的卡車數(shù)量極限。由此可以看出，優(yōu)化模型所給出的3個約束條件能夠使得本優(yōu)化模型更加符合實(shí)際生產(chǎn)情況和相應(yīng)要求。

針對目標(biāo)二——動用的載貨車輛數(shù)最少，建立的數(shù)學(xué)模型如下。

在模型（2）中所有的約束條件與模型（1）一致，即，是要保證在讓載貨車輛數(shù)最少的同時還能同時使得車輛數(shù)滿足基本的貨物運(yùn)輸要求。從數(shù)學(xué)角度上說，就是使得優(yōu)化得出的車輛數(shù)不會出現(xiàn)“奇異值”（例如：負(fù)值），因?yàn)楹茱@然如果沒有合理的約束條件式（2）所示的優(yōu)化模型的全局最優(yōu)解應(yīng)該為負(fù)無窮。上一節(jié)中我們提到，根據(jù)現(xiàn)有的運(yùn)籌學(xué)技術(shù)條件，聯(lián)立求解式（1）與式（2）所示的多目標(biāo)優(yōu)化模型并不容易，一般來說解決多目標(biāo)規(guī)劃一種常規(guī)思想就是將多目標(biāo)轉(zhuǎn)化成為單目標(biāo)，這個思想下最常見的做法就是將多個目標(biāo)進(jìn)行線性組合，使得組合后的目標(biāo)極大或者極小。本文采用一種較為新穎的基于“極大極小”的優(yōu)化思想的轉(zhuǎn)化策略將這個雙目標(biāo)問題轉(zhuǎn)化成為一個單目標(biāo)問題后再進(jìn)行求解[6]，轉(zhuǎn)化后模型如下所示。點(diǎn)法，梯度下降法和空間投影法等一些優(yōu)化領(lǐng)域里的成熟的算法進(jìn)行求解[7]。值得一提的是，由于式（3）所示的模型其求解簡單，所以式（3）所示的優(yōu)化模型還可以根據(jù)實(shí)際需要在約束條件中繼續(xù)增加更多實(shí)際中所需要的約束條件，例如：運(yùn)輸時間，運(yùn)輸費(fèi)用的限制等等。因此，我們說本文模型另一個優(yōu)勢是具有良好的推廣性。

3 模型結(jié)果分析

從式（3）不難看出，此時通過合理轉(zhuǎn)化，我們已經(jīng)將原有的多目標(biāo)優(yōu)化問題簡化成為了一個單目標(biāo)優(yōu)化問題，使得式（3）最小的條件此時顯然是使得式（1）與式（2）一起最小的必要條件。雖然，式（3）所示的優(yōu)化模型是一個非線性規(guī)劃模型，但是由于分子和分母都是線性函數(shù)，因此可以方便的使用內(nèi)

為了驗(yàn)證上一節(jié)給出的礦車運(yùn)輸調(diào)度優(yōu)化模型的可行性，在本節(jié)中我們將采用某礦場的實(shí)際數(shù)據(jù)進(jìn)行算法模擬。這里將分別采用本文提出的方法和傳統(tǒng)的貪心算法進(jìn)行比較，采用對比分析法驗(yàn)證本算法的優(yōu)越性。

某礦場的實(shí)際生產(chǎn)數(shù)據(jù)如表1所示。

表1 礦場數(shù)據(jù)分布Tab.1 Mine data distribution

通過將表1所示的礦場分布數(shù)據(jù)帶入上一節(jié)給出的礦車運(yùn)輸調(diào)度優(yōu)化模型，計算得出的單位運(yùn)量24.89萬噸，而同時執(zhí)行該計劃所需礦車僅為25量。相應(yīng)的，傳統(tǒng)貪心算法得到的單位運(yùn)量僅為21.543萬噸，所需礦車為29量。從實(shí)驗(yàn)結(jié)果對比很容易看出，本文提出的基于多目標(biāo)優(yōu)化的方法相較于傳統(tǒng)的優(yōu)化方法有明顯的優(yōu)勢。

4 結(jié) 論

交通組織是指通過交通規(guī)劃的手段有計劃的引導(dǎo)交通的一系列運(yùn)動，使得機(jī)動化程度的增長從而節(jié)約了運(yùn)輸時間、降低了運(yùn)費(fèi)、降低了產(chǎn)品的成本、促進(jìn)了物資的流通。礦車交通組織的合理優(yōu)化是提高礦區(qū)生產(chǎn)效率的核心問題，是能夠提高礦區(qū)經(jīng)濟(jì)效益的有效途徑。本文利用運(yùn)籌學(xué)中多目標(biāo)優(yōu)化的思想提出了一種礦車運(yùn)輸調(diào)度優(yōu)化模型，并且通過極大極小的方法將雙目標(biāo)問題轉(zhuǎn)化為一個單目標(biāo)問題，簡化了求解過程。通過對比分析可以看出，本文所設(shè)計的算法遠(yuǎn)遠(yuǎn)優(yōu)于傳統(tǒng)的貪心算法，因此適于應(yīng)用到實(shí)際的礦車生產(chǎn)調(diào)度工作中，體現(xiàn)其重要的實(shí)踐指導(dǎo)意義。

[1]《運(yùn)籌學(xué)》教材編寫組.運(yùn)籌學(xué)[M].北京：清華大學(xué)出版社，2005.

[2]戴彤焱，孫學(xué)琴.運(yùn)輸組織學(xué)[M].北京：機(jī)械工業(yè)出版社，2011.

[3]吳祈宗.運(yùn)籌學(xué)與最優(yōu)化方法[M].北京：機(jī)械工業(yè)出版社，2008.

[4]胡斌，王國平，李國強(qiáng).采用多目標(biāo)改進(jìn)差分進(jìn)化算法的環(huán)境經(jīng)濟(jì)發(fā)電調(diào)度[J].陜西電力，2013（1）：24－27.HU Bin，WANG Guo-ping，LI Guo-qiang.Probe into environmental economic dispatching adopting multiobjective improved differential evolution algorithm[J].Shaanxi Electric Power，2013（1）：24－27.

[5]寧姍.基于蟻群聚類的多目標(biāo)環(huán)形分類的方法研究[J].工業(yè)儀表與自動化裝置，2012（5）：70－73.NING Shan.Research on annular sort of multi-objects based on ant colony clustering[J].Industrial Instrumentation&Automation，2012（5）：70－73.

[6]姜啟源，謝金星，葉俊.數(shù)學(xué)模型[M].北京：高等教育出版社，2010.

[7]陳寶林.最優(yōu)化理論與方法[M].北京：清華大學(xué)出版社，2005.

[8]Giordano，F(xiàn).R.等著.葉其孝等譯.數(shù)學(xué)建模[M].3版.北京：機(jī)械工業(yè)出版社，2005.