基于填挖匹配與智能優化算法的土石方調配優化

文思巧巧, 于 靜, 郭嘉偉

(1.長沙理工大學 交通運輸工程學院，湖南 長沙 410014； 2.公路養護技術國家工程研究中心，湖南 長沙 410014)

0 引言

土石方調配通常包括不同區域的挖掘、裝載、搬運、卸載和壓實作業，普遍存在于道路、土石壩、大型場平等工程建設項目中[1-2]，是建筑工程的基本組成部分。土石方調配可分為填挖匹配和運輸路徑規劃兩個階段，旨在通過合理優化填挖匹配方案與運輸路徑規劃方案，提高工程效率、降低施工成本。在實際土石方調運過程中需要綜合考慮運輸路徑、運輸工具選擇、調運時間安排等多個因素，而傳統的土石方調配設計?；诮涷灪椭庇X，缺乏科學分析和優化方法，易導致不必要的資源浪費與施工周期延長[3-4]。

填挖匹配問題常采用線性規劃模型、自動生成模型[5-6]、多目標決策模型[7]等確定其填挖匹配方案。如以工程總調配費用最小為目標[8]，以多個土石方填挖區間的物料和進度協調關系為約束規則[9]，建立填挖匹配問題的可行性規劃模型[10]。上述研究雖然能很快獲取填挖匹配方案，但施工機械的運輸路徑與施工順序方案無法確定。

由于土石方工程中土石方調運量往往較大[11]，且土石方材料從一個地點運輸到另一個地點一般費用較高[12-15]，為了降低施工成本、提高土石方施工的智能化調度水平，學者對土石方運輸路徑規劃進行了研究[16-20]。土石方運輸路徑規劃問題實質上是車輛路徑問題的一個擴展應用，屬于NP-Hard問題[3]，即無法在多項式時間內獲取問題解決方案。當任務規模很大時，傳統的精確算法無法在有限時間內獲取調度方案，需采取有效的啟發式算法進行求解。土石方運輸路徑規劃問題通常是一個連續且可重復的迭代優化過程，因此可通過有效的求解方法來優化土石方調配路徑，如最短路徑Floyd[21]、Dijkstra改進算法[22]、遺傳算法[23]、粒子群算法[24]等。

以土石方調配中的填挖匹配問題和運輸路徑規劃問題為研究對象，分別對土石方調配的兩階段問題進行模型構建與算法求解，獲得了最優填挖匹配方案與機械運輸路徑方案。

1 土石方兩階段調配模型

本文的土石方兩階段調配模型包括填挖匹配模型與運輸路徑規劃模型。填挖匹配模型是以填挖對(土石方等量劃分后，可進行土石方調運的一個填方區與對應的挖方區)間的運輸成本、機械人工費用為最小成本為目標，匹配填挖對，獲取最小施工費用下的填挖匹配方案。由于填挖匹配方案只明確了土石方的調運數量與調運關系，未對項目的具體施工順序及機械運輸路徑進行統一規劃，本文在填挖匹配方案基礎上，同時求解了最小機械轉運距離下的機械運輸路徑方案。

1.1 填挖匹配模型

設某土石方調配項目有m個挖方區，對應的挖方量集合記為E={E1,E2,…,Em},Ei表示第i個挖方區的挖方量;設有n個填方區,對應的填方量集合記為F={F1,F2,…,Fn},Fj表示第j個填方區的填方量。記C=(Cij)nm為挖方區與填方區間的施工費用矩陣,Cij表示第i個挖方區與第j個填方區間的總施工費用,主要由填挖對之間人工與機械費用確定。記Xij為第i個挖方區的土方運輸到第j個填方區的決策變量,其中,Xij=1表示第i個挖方區的土方運輸到第j個填方區,Xij=0表示第i個挖方區的土方沒有運輸到第j個填方區。

根據上述土石方填挖匹配問題的數學描述，本階段的數學模型為：

(1)

(2)

(3)

(4)

式 (1)為土石方調配的目標函數，即以最小施工成本為目標對土石方填挖進行匹配；式 (2)為填挖區的填挖平衡條件，即挖方區總量與填方區總量相同；式 (3)為挖方區約束條件，1個挖方區最多被服務1次；式 (4)為填方區約束條件，表示每個填方區最多被服務1次。式(1)～(4)為土石方填挖匹配問題的線性規劃模型。

1.2 土石方運輸路徑規劃算法模型

對于土石方運輸路徑規劃問題，為了盡可能訪問到所有填挖對，要求路徑規劃模型需有較強的隨機搜索能力。因此，結合土石方調運問題特點，本文選用隨機搜索能力較強的禁忌搜索(Tabu Search,TS)算法與模擬退火優化(Simulated Annealing, SA)算法模型求解土石方調運的運輸路徑規劃問題。

1.2.1模擬退火算法

SA算法是一種模擬物理退火的過程而設計的優化算法，即模擬物體先加熱后冷卻的退火過程。SA基于蒙特卡洛迭代求解策略，模擬熱能在下降并趨于穩定的過程中允許跳出局部最優解的機制，從而可獲取全局較優的可行解。

SA算法首先選擇一個可行的填挖區路徑調度方案作為初始解，并設置算法的初始溫度與終止溫度，在SA實例中初始溫度設為T0=1 000 ℃，終止溫度為Tf=10-3℃；其次，基于鄰域交換規則產生新解，并依據Metropolis接受準則確定當前解；最后，判定熱平衡條件，繼續降溫尋優，直至輸出當前最優解。

SA算法土石方運輸路徑規劃算法流程如圖1所示。

1.2.2禁忌搜索算法

TS算法是一種元啟發式隨機搜索算法，其特點是采用了一種靈活的“記憶”技術--禁忌表。禁忌表用于記錄已經訪問過的解，防止重復搜索，以此來避免陷入局部最優解。

TS算法在填挖區的路徑調度方案中可以高效安排好車輛的運輸路徑，模仿人類的“記憶”功能，使用禁忌表記錄已搜索局部最優解的歷史信息，赦免禁忌區域中的優良狀態，不斷迭代更新從而獲得全局最優解。

TS算法土石方運輸路徑規劃算法流程如圖2所示。

圖2 禁忌搜索算法流程

2 實例求解

以某高速公路路段的土石方調配問題為例進行土石方調運方案設計。本項目土石填方區調運量為675599m3，考慮土石方挖填平衡，需要借土超過4萬m3。本項目土石方的借方區與挖方區位置如圖3所示。以15000m3作為1個填挖對等量劃分標準，將原有挖、填方區劃分為等土方量的填、挖方子集。

圖3 填挖方區域分布

2.1 土石方調配數據準備

1)運距計算。填方與挖方區域之間的距離是主干道運距與便道運距之和。

2)自卸車數量。自卸汽車數量根據挖-填方之間的填挖效率決定。即在施工期間以挖掘機不間斷施工作為自卸車數量優化選擇的標準，選擇滿足條件下最小數量的自卸車。

3)施工費用計算。土石方調配成本主要包括施工期間內機械費用與人工費用，其中施工機械主要包括挖掘機、壓路機、自卸汽車。根據2018公路工程預算定額，相關的施工機械費用、施工機械、人員安排如表1所示。

表1 機械費用、施工機械安排、人員安排機械名稱單價(元·臺班-1)數量/臺(人)挖掘機1 195.011自卸汽車841.461振動壓路機903.681推土機2 355.271人工105.495 注:人工包含觀察員1名,挖掘機、自卸汽車、壓路機、推土機駕駛員各1名。

2.2 土石方兩階段優化調配算法求解

為驗證土石方兩階段優化調配算法的可行性與有效性，采用Matlab軟件對實例進行算法求解。經過多次實驗與分析統計，確定了SA算法的相關參數：初始溫度T0=1 000 ℃，終止溫度Tend=10-3℃，各溫度層的鏈長L=125次，降溫率q=0.98；禁忌搜索算法的禁忌長度為45次。為避免實驗結果贅述，只列出在迭代步數500下，SA算法、TS算法當前最優解的變化與算法求解效率情況。

圖4為SA算法與TS算法在迭代次數為500時，土石方調運冗余路徑當前最優解的變化情況，2種求解算法都可在迭代200次內達到當前的最優解。

圖4 SA的當前最優解變化情況

為了驗證迭代次數對SA、TS算法的影響，選取迭代次數分別為200、400、500、600、700、800次時進行實驗驗證。圖5為不同迭代次數下SA算法與TS的實驗結果。整體上，SA算法與TS算法都可以實現5 s內獲取當前最優解，2種算法的求解效率都很高。相較于TS算法，SA算法的求解效率更高，但其求解穩定性稍差一些。TS算法的求解效率雖稍遜于SA算法，但TS算法可在迭代次數200次條件下100%獲取當前最優解，SA算法在迭代次數200次條件下獲取當前最優解的準確率約為95%。

圖5 不同迭代次數下的算法求解時間

2.3 填挖匹配方案

以最小土石方調運成本為目標，在確定施工機械與人員安排以及實際測算填挖對間運距的情況下，基于填挖匹配模型與2種求解算法，采用Matlab編程獲取的最優填挖匹配方案如表2所示。

表2 最優填挖匹配方案1.5×104 m3填方挖方1～34567～91011-1213141516171819202122～23242526272829303132333435～45總數1112～12111113111411151116～172218～20332111221123112411251126～2833

續表2 最優填挖匹配方案1.5×104 m3填方挖方291130111～34567～91011～1213141516171819202122～23242526272829303132333435～45總數311132113311341135113611371138113911401141114211431144～4522總數311131211111111121111111111111 注: 1個填挖對的土方量為15 000 m3,表中數值為填挖對的個數。

2.4 土石方調運方案

為了對項目具體施工順序及機械運輸路徑進行統一規劃，基于土石方最優填挖匹配方案與土石方路徑規劃模型，以機械轉運最短運距為目標函數，以項目實際的機械轉運規則為約束，采用Matlab對SA算法進行求解，獲取土石方調運方案，包括施工機械轉運方案與自卸車路徑轉運方案。

SA算法求解的自卸汽車轉運方案如式(5)所示。其中，Ci代表第i個挖方區，Fj代表第j個填方區。

C6→F23→C1～3→F26～28→C18→F38→C21→F40→C22～23→F44～45→C26→F30→C28→F36→C25→F33→C20→F14→C14→F35→C31→F34→C11～12→F16～17→C27→F42→C34→F31→C7～9→F18～20→C35～45→F2～12→C5→F25→C19→F43→C33→F37→C32→F32→C30→F29→C29→F41→C4→F39→C10→F1→C2～4→F21

(5)

3 結語

本文對土石方調配中填挖匹配和運輸路徑規劃兩個階段的問題進行了模型構建與算法研發。具體在考慮運輸路徑、運輸工具選擇、調運時間安排等多個實際場景下，以填挖對間的運輸成本、機械人工費用最小為優化目標，獲取以最小施工費用的填挖匹配方案；對項目具體施工順序及機械運輸路徑進行統一規劃，以最小機械轉運距離為目標，基于最優填挖匹配方案與土石方路徑規劃模型，采用模擬退火算法、禁忌搜索算法求解了帶有施工順序的土石方調運方案；最后，以某高速公路路段的土石方調配問題為例，對土石方兩階段調配模型與模擬退火算法進行驗證。研究成果如下：

1)構建了土石方調運填挖匹配的線性規劃模型與求解算法，獲取了土石方調運的最優填挖匹配方案。

2)基于模擬退火算法構建了土石方運輸路徑規劃模型?；谧钚∈┕べM用的最優填挖匹配方案，獲得了最小機械轉運距離下帶有施工順序的土石方調運方案。

通過實例求解，驗證了模擬退火算法、禁忌搜索算法求解土石方調配問題的可行性與有效性。SA算法的求解效率更高，SA算法的求解穩定性更高。兩種求解算法對包含45對填挖區的某高速公路某路段的土石方調運問題進行求解，在5 s內可獲取較優的土石方調運方案。

本研究還存在以下不足：

1)由于實際土石方調運問題中填挖區往往不能根據土方量進行等量劃分子填挖方，故本文中的土石方調運填挖匹配模型還需進一步考慮實際調運過程中的非線性因素。

2)本文采用的模擬退火算法穩定性方面還存在改進空間，接下來嘗試研究混合式的SA-TS算法，以此提高傳統SA算法的穩定性。