基于填挖匹配與智能優(yōu)化算法的土石方調(diào)配優(yōu)化

文思巧巧, 于 靜, 郭嘉偉

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

0 引言

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

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

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

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

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

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

1.1 填挖匹配模型

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

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

(1)

(2)

(3)

(4)

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

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

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

1.2.1模擬退火算法

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

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

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

1.2.2禁忌搜索算法

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

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

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

圖2 禁忌搜索算法流程

2 實(shí)例求解

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

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

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

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

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

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

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

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

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

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

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

為了驗(yàn)證迭代次數(shù)對(duì)SA、TS算法的影響，選取迭代次數(shù)分別為200、400、500、600、700、800次時(shí)進(jìn)行實(shí)驗(yàn)驗(yàn)證。圖5為不同迭代次數(shù)下SA算法與TS的實(shí)驗(yàn)結(jié)果。整體上，SA算法與TS算法都可以實(shí)現(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ù)下的算法求解時(shí)間

2.3 填挖匹配方案

以最小土石方調(diào)運(yùn)成本為目標(biāo)，在確定施工機(jī)械與人員安排以及實(shí)際測(cè)算填挖對(duì)間運(yùn)距的情況下，基于填挖匹配模型與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個(gè)填挖對(duì)的土方量為15 000 m3,表中數(shù)值為填挖對(duì)的個(gè)數(shù)。

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

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

SA算法求解的自卸汽車轉(zhuǎn)運(yùn)方案如式(5)所示。其中，Ci代表第i個(gè)挖方區(qū)，F(xiàn)j代表第j個(gè)填方區(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é)語(yǔ)

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

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

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

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

本研究還存在以下不足：

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

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