基于兩步遺傳算法的預(yù)拌混凝土智能調(diào)度模型

陳海林，王 力，陳煌彬，闕 依，吉 旭

(1.四川大學(xué)化學(xué)工程學(xué)院，四川 成都 610065；2.中建西部建設(shè)湖南有限公司，湖南 長(zhǎng)沙 410005)

近年來(lái)，我國(guó)預(yù)拌混凝土產(chǎn)量逐年增加[1]。但隨著市場(chǎng)競(jìng)爭(zhēng)的日益激烈、原材料及運(yùn)輸成本的不斷上升以及客戶需求的持續(xù)增長(zhǎng)，傳統(tǒng)的生產(chǎn)運(yùn)營(yíng)模式和調(diào)度模式已成為企業(yè)實(shí)現(xiàn)持續(xù)增長(zhǎng)的瓶頸，企業(yè)迫切需要轉(zhuǎn)變經(jīng)營(yíng)機(jī)制，降低生產(chǎn)運(yùn)營(yíng)成本，提高響應(yīng)速度和服務(wù)水平。目前預(yù)拌混凝土企業(yè)集團(tuán)化運(yùn)營(yíng)已成為發(fā)展趨勢(shì)，但集團(tuán)下多數(shù)攪拌站仍為獨(dú)立運(yùn)營(yíng)，生產(chǎn)和配送完全依靠人工經(jīng)驗(yàn)，站點(diǎn)間缺乏協(xié)同性[2]，造成企業(yè)運(yùn)能配置不合理、運(yùn)營(yíng)成本控制困難、市場(chǎng)響應(yīng)不及時(shí)等問(wèn)題。對(duì)此，Asbachaba[3]，戚峰[4]，王飛[5]等建立了帶時(shí)間窗的配送調(diào)度模型，在降低成本方面取得了一定效果，但沒(méi)有考慮不同攪拌站生產(chǎn)成本、運(yùn)輸距離及時(shí)間等因素，具有一定局限性。Zhang[6]，Maghrebi[7]等設(shè)計(jì)了混凝土生產(chǎn)及配送集成調(diào)度模型，提高了攪拌站的利潤(rùn)和運(yùn)行效率，但是只停留在單個(gè)攪拌站調(diào)度層面。Song[8]等對(duì)企業(yè)集團(tuán)的訂單分配模型進(jìn)行了研究，優(yōu)化了企業(yè)集體資源，但未進(jìn)一步研究單站生產(chǎn)車(chē)輛調(diào)度問(wèn)題。

因此，本文將以運(yùn)營(yíng)成本最低、配送時(shí)間最短、服務(wù)質(zhì)量最優(yōu)為目標(biāo)，提出了基于兩步遺傳算法的全局最優(yōu)調(diào)度模式以克服現(xiàn)有調(diào)度模型方法的不足。

1 數(shù)學(xué)模型建立

智能調(diào)度的目的是尋求生產(chǎn)運(yùn)營(yíng)成本最低、配送時(shí)間最短、服務(wù)質(zhì)量最優(yōu)的方案[14]，本文采用遺傳算法分別對(duì)企業(yè)訂單分配、廠站生產(chǎn)車(chē)輛調(diào)度進(jìn)行求解，相關(guān)參數(shù)設(shè)置如下：

i：區(qū)域攪拌站點(diǎn),i∈(1,n)；ai：各攪拌站生產(chǎn)及配送能力；j：一個(gè)訂單周期內(nèi)，需要混凝土的工程項(xiàng)目數(shù),j∈(1,m)；bj：一個(gè)訂單周期內(nèi)，各工程項(xiàng)目的混凝土需求量；di：攪拌站點(diǎn)i的單方混凝土原材料生產(chǎn)成本；cij：攪拌站點(diǎn)i為工程項(xiàng)目 配送的物流成本；tij：攪拌站點(diǎn)i為工程項(xiàng)目j配送的運(yùn)輸時(shí)間；eij：攪拌站點(diǎn)i為工程項(xiàng)目j配送的次數(shù)；eif：攪拌站點(diǎn)xij為工程項(xiàng)目f配送混凝土的方量。gij為0-1變量，當(dāng)工程項(xiàng)目f訂單分配給攪拌站t時(shí)，gij=1，否則gij=0；E:攪拌車(chē)載重；Kj：配送到工程項(xiàng)目f攪拌車(chē)車(chē)次數(shù)；k：配送到工程項(xiàng)目f的攪拌車(chē)編號(hào)，κ∈(1，Kj)；DT：工程項(xiàng)目j允許最大中斷時(shí)間；MT：攪拌機(jī)單車(chē)生產(chǎn)攪拌時(shí)間；TDv：攪拌站向工程項(xiàng)目派第ν輛車(chē)時(shí)，攪拌站剩余車(chē)輛數(shù)；Sjk：工程項(xiàng)目f等待攪拌車(chē)k的來(lái)料等待時(shí)間；Tjk：攪拌車(chē)k在工程項(xiàng)目的卸料等待時(shí)間；SDjk：攪拌車(chē)k為工程項(xiàng)目f配送的運(yùn)輸時(shí)間；STe：派往工程項(xiàng)目的第e輛攪拌車(chē)的時(shí)刻。

圖1 預(yù)拌混凝土調(diào)度模式Fig.1 ready-mixed concrete scheduling model

1.1 企業(yè)訂單分配模型

預(yù)拌混凝土企業(yè)由下屬的若干攪拌站組成，通常各攪拌站獨(dú)立運(yùn)營(yíng)，造成了資源和時(shí)間的浪費(fèi)，通過(guò)遺傳算法以運(yùn)營(yíng)成本最低、配送時(shí)間最短的整體最優(yōu)為目標(biāo)進(jìn)行求解。目標(biāo)函數(shù)為：

式(1.1)表示總運(yùn)營(yíng)成本最小，(1.2)表示總配送時(shí)間最短，(1.3)表示采用加權(quán)法表示的整體最優(yōu)分配函數(shù)。為保證(1.3)目標(biāo)函數(shù)的最小化，需要滿足以下約束條件。

其中，(1.4)表示各攪拌站向工程項(xiàng)目配送的混凝土數(shù)量總和不超過(guò)其生產(chǎn)能力；(1.5)表示每個(gè)工程項(xiàng)目的需求都能得到滿足；(1.6)表示攪拌站點(diǎn)i為工程項(xiàng)目j配送數(shù)量可為0；(1.7)、(1.8)表示每一個(gè)工程項(xiàng)目只由一個(gè)攪拌站配送，(1.9)表示權(quán)值取值范圍。

1.2 生產(chǎn)車(chē)輛調(diào)度模型

預(yù)拌混凝土是一種臨時(shí)過(guò)渡性產(chǎn)品，具有一定的時(shí)限性。一方面，生產(chǎn)配送過(guò)早將產(chǎn)生卸貨等待時(shí)間，造成質(zhì)量的下降和時(shí)間的浪費(fèi)。另一方面，生產(chǎn)配送過(guò)晚會(huì)產(chǎn)生工程項(xiàng)目來(lái)料等待時(shí)間，影響項(xiàng)目進(jìn)度。卸料及來(lái)料等待時(shí)間越小意味著客戶服務(wù)水平越高。本文通過(guò)遺傳算法確定最優(yōu)生產(chǎn)調(diào)度方案，目標(biāo)函數(shù)為：

式(2.1)表示來(lái)料等待時(shí)間最小，(2.2)表示卸料等待時(shí)間最小，(2.3)表示采用加權(quán)法表示的整體最優(yōu)生產(chǎn)調(diào)度函數(shù)，這些目標(biāo)函數(shù)需要滿足以下約束。

其中，表示工程項(xiàng)目的連續(xù)兩次澆筑時(shí)間間隔不超過(guò)允許的最大間隔時(shí)間；表示攪拌站連續(xù)兩次發(fā)車(chē)時(shí)間間隔不小于混凝土攪拌時(shí)間；表示發(fā)出生產(chǎn)指令時(shí)，站內(nèi)至少有一輛攪拌車(chē)；表示生產(chǎn)時(shí)間到開(kāi)始澆筑時(shí)間不超過(guò)產(chǎn)品初凝時(shí)間，表示權(quán)值取值范圍。

2 遺傳算法原理

遺傳算法是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過(guò)程，將搜索空間映射為遺傳空間，以概率化方式進(jìn)行空間搜索尋優(yōu)，根據(jù)適應(yīng)度自動(dòng)調(diào)整搜索方向，從而得到最優(yōu)解的計(jì)算模型。它具有高隱含并行性、強(qiáng)隨機(jī)全局搜索和優(yōu)化能力、強(qiáng)魯棒性等特點(diǎn)[9-10]。

圖2 遺傳算法運(yùn)算流程

Fig.2 The operation flow of genetic algorithm

遺傳算法將潛在解按一定變換規(guī)則進(jìn)行編碼，以向量形式表達(dá)，并生成一定數(shù)量的個(gè)體組成初始可行解，然后計(jì)算初始解集中各個(gè)體的適應(yīng)度，以此來(lái)表現(xiàn)各個(gè)體適應(yīng)環(huán)境的優(yōu)劣狀態(tài)，從而體現(xiàn)各解的優(yōu)劣。通過(guò)引入遺傳學(xué)機(jī)理中的選擇、交叉和變異的遺傳操作，將個(gè)體基因進(jìn)行改變，產(chǎn)生新一代的種群。新一代的種群代表的是更優(yōu)的個(gè)體，在這種隨機(jī)且?guī)б欢ㄒ?guī)律的變化過(guò)程中，搜索大范圍的可行解，進(jìn)而求得可能的最優(yōu)解[11-13]。本文中的遺傳算法運(yùn)算流程如圖2所示。

(1)基因編碼：在進(jìn)行搜索之前先將訂單分配和生產(chǎn)調(diào)度問(wèn)題轉(zhuǎn)換到遺傳算法的搜索空間，按一定變換規(guī)則進(jìn)行編碼，以向量形式表達(dá)。

(2)生成初始種群：形成初始種群，據(jù)基因編碼機(jī)制和規(guī)則，初始化生成染色體群。每個(gè)字符串結(jié)構(gòu)成為一個(gè)染色體，所有個(gè)體構(gòu)成一個(gè)染色體群，訂單分配和生產(chǎn)調(diào)度的初始方案為每個(gè)初始個(gè)體。

(3)適應(yīng)度評(píng)估：適應(yīng)度函數(shù)用來(lái)衡量種群中個(gè)體或解的優(yōu)劣性，不同問(wèn)題的適應(yīng)度函數(shù)各不相同。適應(yīng)度越高表示對(duì)環(huán)境的適應(yīng)越強(qiáng)，越能滿足尋優(yōu)的目的。

(4)選擇：選擇操作是將種群中優(yōu)秀的個(gè)體直接遺傳到下一代或通過(guò)配對(duì)交叉產(chǎn)生新的個(gè)體再遺傳到下一代，是選擇優(yōu)秀個(gè)體、淘汰劣質(zhì)個(gè)體的過(guò)程。個(gè)體適應(yīng)度越高，則其攜帶的染色體遺傳到子代的概率越大。

(5)交叉：交叉是兩個(gè)父代個(gè)體的相同位置的兩段基因片段相互交換的操作，以便獲得新的基因組合，從而達(dá)到產(chǎn)生更優(yōu)秀個(gè)體的目的。

(6)變異：變異是指當(dāng)前種群中單個(gè)個(gè)體中一個(gè)或幾個(gè)位置的基因進(jìn)行反向變換，產(chǎn)生新的個(gè)體。可增加遺傳算法局部的隨機(jī)搜索能力，維持群體的多樣性。

(7)判斷是否終止迭代：通過(guò)設(shè)置最大迭代次數(shù)，或者收斂條件，終止種群的進(jìn)化迭代次數(shù)，獲得問(wèn)題的近似最優(yōu)方案。

3 應(yīng)用實(shí)例

本文中所涉及的數(shù)據(jù)均來(lái)源于某大型預(yù)拌混凝土企業(yè)及攪拌站實(shí)地調(diào)研，能真實(shí)反映現(xiàn)實(shí)情況與調(diào)度模型優(yōu)化后的差異，可為預(yù)拌混凝土企業(yè)實(shí)施智能調(diào)度提供算法和數(shù)據(jù)支撐。該混凝土企業(yè)在一區(qū)域內(nèi)分布有8個(gè)攪拌站，各攪拌站資源約束情況如表1所示，在一個(gè)訂單周期內(nèi)，需要對(duì)57個(gè)工程項(xiàng)目進(jìn)行訂單分配(j=1,b1=197;j=2,b2=549,j=3,b3=54…j=57,b57=30.5),通過(guò)對(duì)各攪拌站和工程項(xiàng)目的實(shí)地調(diào)研，本文中權(quán)值α、β、γ、η分別取0.9、0.1、0.7、0.3。訂單分配模型中遺傳算法的種群數(shù)為400，進(jìn)化次數(shù)為2000次，交叉率為0.8，變異率為0.3，生產(chǎn)調(diào)度模型中種群數(shù)為500，進(jìn)化次數(shù)為2500次，交叉率為0.7，變異率為0.3。通過(guò)對(duì)遺傳算法平均適應(yīng)度和最佳適應(yīng)度的比較可證明模型的可靠性。

表1 各攪拌站資源約束情況Table.1 Resource constraints of mixing station

圖3 遺傳算法適應(yīng)度函數(shù)

Fig.3 The fitness function of genetic algorithm

4 結(jié)果與討論

通過(guò)兩步遺傳算法分別對(duì)訂單分配和生產(chǎn)調(diào)度求解。訂單分配結(jié)果如表2所示，與企業(yè)原有訂單分配方案相比，優(yōu)化后降低運(yùn)營(yíng)成本3.94元/方，總計(jì)56725.97元/天；減少運(yùn)輸時(shí)間11.07min/趟，總計(jì)13588.4min/天。與原有的人工經(jīng)驗(yàn)生產(chǎn)調(diào)度相比，模型優(yōu)化后的等待時(shí)間主要集中在10min以內(nèi)，平均等待時(shí)間由原來(lái)的22.4min下降到5.1min(圖4)。計(jì)算結(jié)果表明訂單分配和生產(chǎn)調(diào)度模型可有效降低生產(chǎn)運(yùn)營(yíng)成本，減少配送時(shí)間，提高服務(wù)水平。

表2 訂單分配計(jì)算結(jié)果Table.2 The calculation result of order distribution model

表3 生產(chǎn)配送流程時(shí)間計(jì)算結(jié)果Table.3 Time calculation results of production and distribution

圖4 模型優(yōu)化前后等待時(shí)間對(duì)比

Fig.4 Comparison of results before and after model optimization

5 結(jié)論

基于企業(yè)降低運(yùn)營(yíng)成本、提升服務(wù)水平的需求，本文從智能優(yōu)化算法出發(fā)，提出了基于兩步遺傳算法的智能調(diào)度模型。以某企業(yè)一區(qū)域內(nèi)的訂單及生產(chǎn)方案優(yōu)化為例，應(yīng)用本模型可降低運(yùn)營(yíng)成本3.94元/方、運(yùn)輸時(shí)間11.07min/趟次，減少卸料及來(lái)料等待時(shí)間17.3min/車(chē)。不僅證明了模型及算法的可行性，而且為預(yù)拌混凝土企業(yè)實(shí)施智能調(diào)度提供了強(qiáng)有力的算法和數(shù)據(jù)支撐。