文思巧巧, 于 靜, 郭嘉偉

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

0 引言

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

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

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

以土石方調(diào)配中的填挖匹配問題和運輸路徑規(guī)劃問題為研究對象，分別對土石方調(diào)配的兩階段問題進(jìn)行模型構(gòu)建與算法求解，獲得了最優(yōu)填挖匹配方案與機械運輸路徑方案。

1 土石方兩階段調(diào)配模型

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

1.1 填挖匹配模型

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

根據(jù)上述土石方填挖匹配問題的數(shù)學(xué)描述，本階段的數(shù)學(xué)模型為：

(1)

(2)

(3)

(4)

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

1.2 土石方運輸路徑規(guī)劃算法模型

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

1.2.1模擬退火算法

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

SA算法首先選擇一個可行的填挖區(qū)路徑調(diào)度方案作為初始解，并設(shè)置算法的初始溫度與終止溫度，在SA實例中初始溫度設(shè)為T0=1 000 ℃，終止溫度為Tf=10-3℃；其次，基于鄰域交換規(guī)則產(chǎn)生新解，并依據(jù)Metropolis接受準(zhǔn)則確定當(dāng)前解；最后，判定熱平衡條件，繼續(xù)降溫尋優(yōu)，直至輸出當(dāng)前最優(yōu)解。

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

1.2.2禁忌搜索算法

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

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

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

圖2 禁忌搜索算法流程

2 實例求解

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

圖3 填挖方區(qū)域分布

2.1 土石方調(diào)配數(shù)據(jù)準(zhǔn)備

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

2)自卸車數(shù)量。自卸汽車數(shù)量根據(jù)挖-填方之間的填挖效率決定。即在施工期間以挖掘機不間斷施工作為自卸車數(shù)量優(yōu)化選擇的標(biāo)準(zhǔn)，選擇滿足條件下最小數(shù)量的自卸車。

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

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

2.2 土石方兩階段優(yōu)化調(diào)配算法求解

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

圖4為SA算法與TS算法在迭代次數(shù)為500時，土石方調(diào)運冗余路徑當(dāng)前最優(yōu)解的變化情況，2種求解算法都可在迭代200次內(nèi)達(dá)到當(dāng)前的最優(yōu)解。

圖4 SA的當(dāng)前最優(yōu)解變化情況

為了驗證迭代次數(shù)對SA、TS算法的影響，選取迭代次數(shù)分別為200、400、500、600、700、800次時進(jìn)行實驗驗證。圖5為不同迭代次數(shù)下SA算法與TS的實驗結(jié)果。整體上，SA算法與TS算法都可以實現(xiàn)5 s內(nèi)獲取當(dāng)前最優(yōu)解，2種算法的求解效率都很高。相較于TS算法，SA算法的求解效率更高，但其求解穩(wěn)定性稍差一些。TS算法的求解效率雖稍遜于SA算法，但TS算法可在迭代次數(shù)200次條件下100%獲取當(dāng)前最優(yōu)解，SA算法在迭代次數(shù)200次條件下獲取當(dāng)前最優(yōu)解的準(zhǔn)確率約為95%。

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

2.3 填挖匹配方案

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

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

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

2.4 土石方調(diào)運方案

為了對項目具體施工順序及機械運輸路徑進(jìn)行統(tǒng)一規(guī)劃，基于土石方最優(yōu)填挖匹配方案與土石方路徑規(guī)劃模型，以機械轉(zhuǎn)運最短運距為目標(biāo)函數(shù)，以項目實際的機械轉(zhuǎn)運規(guī)則為約束，采用Matlab對SA算法進(jìn)行求解，獲取土石方調(diào)運方案，包括施工機械轉(zhuǎn)運方案與自卸車路徑轉(zhuǎn)運方案。

SA算法求解的自卸汽車轉(zhuǎn)運方案如式(5)所示。其中，Ci代表第i個挖方區(qū)，F(xiàn)j代表第j個填方區(qū)。

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 結(jié)語

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

1)構(gòu)建了土石方調(diào)運填挖匹配的線性規(guī)劃模型與求解算法，獲取了土石方調(diào)運的最優(yōu)填挖匹配方案。

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

通過實例求解，驗證了模擬退火算法、禁忌搜索算法求解土石方調(diào)配問題的可行性與有效性。SA算法的求解效率更高，SA算法的求解穩(wěn)定性更高。兩種求解算法對包含45對填挖區(qū)的某高速公路某路段的土石方調(diào)運問題進(jìn)行求解，在5 s內(nèi)可獲取較優(yōu)的土石方調(diào)運方案。

本研究還存在以下不足：

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

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