基于兩步遺傳算法的預拌混凝土智能調度模型

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

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

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

因此，本文將以運營成本最低、配送時間最短、服務質量最優為目標，提出了基于兩步遺傳算法的全局最優調度模式以克服現有調度模型方法的不足。

1 數學模型建立

智能調度的目的是尋求生產運營成本最低、配送時間最短、服務質量最優的方案[14]，本文采用遺傳算法分別對企業訂單分配、廠站生產車輛調度進行求解，相關參數設置如下：

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

圖1 預拌混凝土調度模式Fig.1 ready-mixed concrete scheduling model

1.1 企業訂單分配模型

預拌混凝土企業由下屬的若干攪拌站組成，通常各攪拌站獨立運營，造成了資源和時間的浪費，通過遺傳算法以運營成本最低、配送時間最短的整體最優為目標進行求解。目標函數為：

式(1.1)表示總運營成本最小，(1.2)表示總配送時間最短，(1.3)表示采用加權法表示的整體最優分配函數。為保證(1.3)目標函數的最小化，需要滿足以下約束條件。

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

1.2 生產車輛調度模型

預拌混凝土是一種臨時過渡性產品，具有一定的時限性。一方面，生產配送過早將產生卸貨等待時間，造成質量的下降和時間的浪費。另一方面，生產配送過晚會產生工程項目來料等待時間，影響項目進度。卸料及來料等待時間越小意味著客戶服務水平越高。本文通過遺傳算法確定最優生產調度方案，目標函數為：

式(2.1)表示來料等待時間最小，(2.2)表示卸料等待時間最小，(2.3)表示采用加權法表示的整體最優生產調度函數，這些目標函數需要滿足以下約束。

其中，表示工程項目的連續兩次澆筑時間間隔不超過允許的最大間隔時間；表示攪拌站連續兩次發車時間間隔不小于混凝土攪拌時間；表示發出生產指令時，站內至少有一輛攪拌車；表示生產時間到開始澆筑時間不超過產品初凝時間，表示權值取值范圍。

2 遺傳算法原理

遺傳算法是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程，將搜索空間映射為遺傳空間，以概率化方式進行空間搜索尋優，根據適應度自動調整搜索方向，從而得到最優解的計算模型。它具有高隱含并行性、強隨機全局搜索和優化能力、強魯棒性等特點[9-10]。

圖2 遺傳算法運算流程

Fig.2 The operation flow of genetic algorithm

遺傳算法將潛在解按一定變換規則進行編碼，以向量形式表達，并生成一定數量的個體組成初始可行解，然后計算初始解集中各個體的適應度，以此來表現各個體適應環境的優劣狀態，從而體現各解的優劣。通過引入遺傳學機理中的選擇、交叉和變異的遺傳操作，將個體基因進行改變，產生新一代的種群。新一代的種群代表的是更優的個體，在這種隨機且帶一定規律的變化過程中，搜索大范圍的可行解，進而求得可能的最優解[11-13]。本文中的遺傳算法運算流程如圖2所示。

(1)基因編碼：在進行搜索之前先將訂單分配和生產調度問題轉換到遺傳算法的搜索空間，按一定變換規則進行編碼，以向量形式表達。

(2)生成初始種群：形成初始種群，據基因編碼機制和規則，初始化生成染色體群。每個字符串結構成為一個染色體，所有個體構成一個染色體群，訂單分配和生產調度的初始方案為每個初始個體。

(3)適應度評估：適應度函數用來衡量種群中個體或解的優劣性，不同問題的適應度函數各不相同。適應度越高表示對環境的適應越強，越能滿足尋優的目的。

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

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

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

(7)判斷是否終止迭代：通過設置最大迭代次數，或者收斂條件，終止種群的進化迭代次數，獲得問題的近似最優方案。

3 應用實例

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

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

圖3 遺傳算法適應度函數

Fig.3 The fitness function of genetic algorithm

4 結果與討論

通過兩步遺傳算法分別對訂單分配和生產調度求解。訂單分配結果如表2所示，與企業原有訂單分配方案相比，優化后降低運營成本3.94元/方，總計56725.97元/天；減少運輸時間11.07min/趟，總計13588.4min/天。與原有的人工經驗生產調度相比，模型優化后的等待時間主要集中在10min以內，平均等待時間由原來的22.4min下降到5.1min(圖4)。計算結果表明訂單分配和生產調度模型可有效降低生產運營成本，減少配送時間，提高服務水平。

表2 訂單分配計算結果Table.2 The calculation result of order distribution model

表3 生產配送流程時間計算結果Table.3 Time calculation results of production and distribution

圖4 模型優化前后等待時間對比

Fig.4 Comparison of results before and after model optimization

5 結論

基于企業降低運營成本、提升服務水平的需求，本文從智能優化算法出發，提出了基于兩步遺傳算法的智能調度模型。以某企業一區域內的訂單及生產方案優化為例，應用本模型可降低運營成本3.94元/方、運輸時間11.07min/趟次，減少卸料及來料等待時間17.3min/車。不僅證明了模型及算法的可行性，而且為預拌混凝土企業實施智能調度提供了強有力的算法和數據支撐。