考慮費用支付模式的公路網養護調度模型

毛新華 ，王建偉 ，袁長偉

（1.長安大學運輸工程學院，陜西 西安 710064；2.長安大學道路基礎設施數字化教育部工程研究中心，陜西 西安 710064；3.長安大學“一帶一路”沿線交通基礎設施建設與管理數字化國際聯合研究中心，陜西 西安 710064；4.長安大學西安市交通基礎設施建設與管理數字化重點實驗室，陜西 西安 710064）

隨著我國公路基礎設施逐步進入養護高峰期，公路養護將成為一項日常性和長期性工作.在日常性養護施工中，如何確定養護調度方案，即明確各養護路段的施工順序并將養護路段指派給各養護隊，是制定公路養護施工計劃的重要內容，而一個合理的養護調度方案有利于縮短養護工期、減少交通擁堵、節約養護成本等[1].因此，研究公路養護調度問題，制定科學的養護調度方案，對完善和提升公路養護管理水平具有重要意義.

目前針對公路網養護調度問題的研究按照計劃期長短可分為短期養護調度和長期養護調度[2].在短期養護調度中，所有路段均被養護一次，現有研究大多將其抽象成一個組合優化問題，并采用混合整數規劃模型求解[3].比如，Fontaine 等[4]構建了以出行時間最少為目標的養護調度非線性混合整數規劃模型，并采用精確算法求解.Santos 等[5]則采用一個線性混合整數規劃模型求解交通延誤最少為目標的養護調度問題.除出行時間最少和交通延誤最少的調度目標以外，養護成本和用戶成本總和最低[6]、養護后的路面損壞最少[7]、溫室氣體排放最少[8]等也被考慮為養護調度目標，因此，部分學者構建了多目標養護調度模型[9].近年來，隨著彈性基礎設施的概念越來越受到重視，部分研究還從公路網彈性最優的角度研究養護調度問題[10-11].比如，Li 等[12]構建了路網累計彈性損失最小和養護速度彈性最大的多目標養護調度模型.在長期養護調度中，所有路段需要被多次養護，現有研究大都將其抽象成一個動態規劃問題[13].部分學者采用馬爾可夫決策模型求解，比如，Sch?bi 等[14]采用后向遞歸函數表示路面最優養護方式的選擇策略，并構建動態規劃模型，解決養護方式和養護路段最優選擇的多階段決策問題.然而，馬爾可夫決策模型得到的養護調度方案本質上是一個概率型方案，無法明確地指導養護項目的具體安排，因此部分學者提出了基于近似動態規劃的養護調度模型，比如Kuhn[15]構建了養護資金約束下的路網養護調度近似動態規劃模型.相較于馬爾可夫決策模型，近似動態規劃模型可滿足更為松弛的假設條件，且得到結果是一個精確型的養護調度方案[16].本文主要研究公路養護的短期養護調度問題.

總的來講，按照假設條件的不同，現有的公路養護調度模型可以劃分為“由上至下”和“由下至上”兩類.“由上至下”決策模型假設路網中各路段具有類似的屬性特征.比如，Durango-Cohen 等[17]將各路段的初始路面特性統一采用離散條件評定集加以表示，并假設各路段路面性能具有相同的衰變速率.“由上至下”最優決策法在解決各路段具有相似屬性的小范圍路網養護最優決策問題具有較好的適用性，但是針對大范圍路網的養護最優決策問題具有局限性.因此，越來越多的學者開始研究“由下至上”最優決策法，該方法充分考慮路網中各路段屬性特征的差異性.比如，Ozer 等[18]采用閾值法判斷各路面采取何種養護措施，并對各路段的路面性能狀況設定了不同的閾值.

綜上所述，目前針對公路網養護調度的研究成果較多，然而，現有成果未從公路經營管理部門或業主對養護承包商的費用支付進度和支付額度角度確定公路網的養護調度方案.因此，本文研究基于不同費用支付模式的公路網養護調度問題，以承包方收益現值的最大化為目標，構建混合整數非線性規劃模型，并采用禁忌搜索算法求解，從而優化養護調度方案.

1 模型構建

1.1 基本假設

本文的模型構建主要基于以下假設條件：

1）每個養護隊可養護多條路段，但同時只能養護一條路段，即每個養護隊養護完一條路段后才能進行下一條路段的養護；

2）每條路段只能由一個養護隊養護，且每條路段在養護工期內只能被養護一次；

3）養護完成后，業主支付完合同規定的剩余費用；

4）養護承包方對每條路段的養護成本支出發生在該路段養護的開始時刻并且每天的資金消耗量均等.

1.2 問題描述

假設在某一養護周期內業主計劃對路網中的N條路段進行養護，路段n(n=1,2,···,N)的養護工期、實際養護成本和養護定額分別為dn、cn和wn(wn＞cn).因此，N條路段養護的總合同額為B=，實際養護費用為C=.業主通過公開招標的方式確定一個承包方完成所有路段的養護施工任務，該承包方共有R個養護施工隊.假設養護施工在第ts天開始，并且在第ts+M－1 天結束，總的實際養護工期則為M天.雙方約定承包方的最長養護工期不能超過Mmax，業主分K次向承包方支付合同規定的所有費用，可能的支付模式有以下3 種[19]：

1）基于時間進度的支付模式.從第ts天開始，每隔M/K天業主向承包方支付一次費用，直到養護結束.當養護完成后，業主支付最后一次費用.

2）基于養護進度的支付模式.采用承包方累計完成的合同額計量養護進度.承包方實際每完成B/K的合同額時，業主支付一次費用，直到養護結束.當養護完成后，業主支付最后一次費用.

3）基于養護費用的支付模式.由業主和承包方共同確定一個可接受的費用總額G，當在養護過程中，承包方實際每發生G/K的費用時，業主支付一次費用，直到養護結束.當養護完成后，業主支付最后一次費用.

當確定支付模式后，在業主的支付過程中，每次支付的費用根據承包方完成路段養護的定額總和確定，并且每次支付并非全額支付，而是按照某一比例 β（0 ≤β ≤1）進行支付，每次的實際支付額為pk(k=1,2,···,K).在上述規定下，為順利完成所有的養護任務，承包方需要進行墊資，假設承包方的最大墊資能力為U，承包方必須保證在養護結束前的任何一天，累計的費用支出與業主的累計支付額之差不能超過U，否則，承包方將面臨資金鏈斷裂，超過合同約定的養護工期.因此，承包方需要合理安排所有路段的養護施工順序以及各養護隊的養護任務，從而在保證養護工期的前提下實現最優現金流.為此，定義如下兩個0-1 決策變量：

xnt：如果路段n在第t(t=ts,ts+1,···,ts+Mmax-1)天開始養護，xnt=1；否則，xnt=0.

ynr：如果路段n指派給養護隊r(r=1,2,···,R)進行養護，ynr=1；否則，ynr=0.

因此，將本文研究的問題定義為：在給定的費用支付模式下，求解可行的xnt和ynr，使養護承包方的凈現金流最優，即承包方收益的現值H最大.

1.3 最優養護調度模型

根據上述基本假設和對研究問題的描述，本文首先構建如下最優養護調度的基本模型.該模型為一個單目標混合整數非線性規劃模型.

目標函數：

式（1）～（11）中：ρ 為折現率；Jk為第k次支付的時間；τ 為不同于t的時間；Kt為截止到第t天的累計支付次數.

式（1）為模型的目標函數，表示承包方收益現值的最大化，采用連續復利計算，其中第1 項為業主各次支付額（現金流入）的現值總和，第2 項為所有路段的養護費用（現金流出）現值總和；式（2）表示整個養護過程的總工期，為最后完成養護的路段的養護結束時間；式（3）是非搶占式約束，表示所有路段在養護過程中僅被養護一次；式（4）表示任何一個養護隊最多只能同時養護一條路段，不能同時養護多條路段；式（5）表示在第t天正在進行養護的路段數量不能超過養護隊數量；式（6）表示所有養護隊均不能在其所養護的路段的工期前完成養護工作；式（7）為業主的支付額約束，表示第k次的支付額等于從第k－1 次支付開始到第k次支付為止的時間段內承包方累計完成的合同額與業主支付比例的乘積；式（8）表示最后一次（即第K次）的支付額，是合同總額減去K-1 次的支付額總和的差，從而保證總的支付額等于合同額；式（9）表示在養護過程中任何一天的承包方累計費用支出與業主的累計支付額之差不能超過承包方的墊資能力；式（10）和式（11）定義兩個決策變量為0-1 變量.

上述模型中，在不同的支付模式下，支付的時間Jk不同.3 種支付模式下最后一次支付的時間均為JK=ts+M+1，而第k次（不包括最后一次K）的支付時間Jk(k=1,2,···,K-1) 可表示為

1）基于時間進度的支付模式

2）基于養護進度的支付模式

考慮到直接由kM/K得到的支付時間不一定是整數天，因此式（12）定義支付時間為養護施工開始后的第kM/K天或者其后的第1 個整數天；式（13）定義支付時間為承包方累計完成的合同額達到kB/K后的第1 天；式（14）定義支付時間為承包方累計的支出達到kG/K后的第1 天.將上述支付時間計算方程代入基本模型中的式（1）即可得到不同支付模式下的養護調度模型.

2 模型求解

業主對費用的支付模式和承包方的墊資能力一定程度上限制了養護過程中承包方的可用資金，從而使考慮費用支付模式的公路網養護調度問題從本質上是一類資源受限的項目調度問題，而該類問題已被證明具有NP（non-deterministic Polynomial）難的性質[20].因此，本文采用禁忌搜索算法[21]求解該模型.

2.1 解的表示和初始可行解

采用養護施工隊指派列表E、養護先后順序列表F表示模型的解 Γ(E,F).

養護施工隊指派列表由N個元素構成，每個元素是一個養護施工隊變量，并且對應每條路段所指派的養護施工隊.養護施工隊的指派必須滿足式（5）.列表E如圖1 所示.

圖1 養護施工隊指派列表示意Fig.1 Maintenance crew assignment list

養護先后順序列表包含R個子列表，子列表數量由養護隊數量決定，一個養護隊對應一個子列表.子列表Fr由多個路段代號構成，路段代號在子列表中的位置代表相應路段的養護先后順序，R個子列表中的代碼數量總和為N.列表F如圖2 所示.

圖2 養護先后順序列表示意Fig.2 Maintenance sequence list

根據上述兩個列表，采用如下步驟生成初始可行解：

步驟1輸入列表E，確定養護列表F的子列表數量，及每個養護路段的工期dn、成本cn及定額wn.

步驟2根據各子列表Fr，Fr中最先養護的開始時間ts,r隨機分布于 [ts,ts+Mmax-min{dn}]，結合各路段的養護工期，在前一個養護路段的結束時間后隨機安排下一個路段的養護開始時間，從而得到一個初始解 Γ0.

步驟3判斷 Γ0是否滿足式（7）～（9），若是，則接受 Γ0為模型的初始可行解；否則，拒絕 Γ0，并返回至步驟2，重復上述步驟，直至獲得一個可行解為止.

2.2 鄰域結構設計

采用如下兩個操作生成 Γ(E,F) 的鄰域 Γe(E,F) ：

1）改變養護施工隊的指派.如圖3 所示，在列表E中隨機選擇一個路段，所有路段具有R種指派可能，將各路段原來指派的養護隊變換為其他養護隊，即給每個路段重新選擇一個養護隊，直到列表E中所有路段指派的養護隊均被改變為止.養護施工隊的指派必須滿足式（5）.

圖3 養護施工隊指派變換示意Fig.3 Maintenance crew assignment mutation

2）交換養護先后順序.如圖4 所示，分別在列表F的各子列表中隨機選擇兩個養護路段，并交換其位置，從而改變其養護的先后順序，直到子列表中所有路段的養護先后順序均被改變為止.交換養護先后順序必須滿足式（7）～（9）.

圖4 養護先后順序交換示意Fig.4 Maintenance sequence swap

2.3 禁忌表和終止條件

禁忌表TL的更新采用“先進先出”原則進行更新：當執行向鄰域移動時，其反向移動添加至禁忌表的底部，并且禁忌表中最早的移動從列表的頂部移除，禁忌列表中的所有移動均被禁止.然而，如果被禁止的移動能夠產生一個比當前最優解更好的解，則取消其禁忌狀態.禁忌表的長度設置為當總的迭代次數達到預設的上限值時，算法終止執行，并輸出最優解.

2.4 禁忌搜索步驟

禁忌搜索算法的執行包含以下6 個步驟：

步驟1隨機生成一個初始可行解 Γ0，并根據Γ0計算式（1）中的目標函數值H0.定義算法終止條件，即總的迭代次數達到預設的上限值imax，初始化禁忌表TL，令迭代次數為i=0.將當前解 Γc和最優解 Γb賦值為初始解 Γ0，即 Γc=Γb=Γ0，并且將當前解 Γc和最優解 Γb所對應的目標函數值Hc和Hb賦值為H0，即Hc=Hb=H0.

步驟2生成當前解 Γc的一個鄰解 Γe，得到其目標函數值He.判斷生成鄰解的移動操作是否位于禁忌表TL內，若是，轉至步驟4；否則，轉至步驟3.

步驟3令 Γc=Γe，Hc=He，i=i+1.更新禁忌表TL.若Hc＞Hb，則令 Γb=Γc，Hb=Hc，并轉至步驟4；否則，轉至步驟5.

步驟4若He＞Hb，解除禁忌狀態，令 Γc=Γb=Γe，Hc=Hb=He，i=i+1，并更新禁忌表TL，轉至步驟5；否則，轉至步驟2.

步驟5判斷i≥imax是否成立，若成立，轉至步驟6；否則，轉至步驟2.

步驟6輸出最優解 Γ*，Γ*=Γb，相應的最優目標函數值為H*=Hb.

3 案例分析

3.1 基本數據

本文以西安市繞城高速公路小修保養工程為例驗證模型和算法的有效性.業主為陜西省交通建設集團公司西安繞城分公司，養護承包方為陜西交通建設養護工程有限公司.經雙方合同約定，該養護工程包含繞城高速24 個路段的小修保養，包括路面坑槽、裂縫等病害的修補等，整個養護工程的合同總價款為2 336.0 萬元，整個養護工程須在160 d 內完工，為便于表述，將養護工程的開工日期視為第1 天，即ts=1.業主共分4 次向承包方支付費用，前3 次的支付比例為80%，養護完工后業主進行最后一次支付并付清全部余款.養護承包方的墊資能力為600.0 萬元，共派出3 個養護隊進行養護作業.各路段的養護工期、成本及定額如表1 所示.

表1 各路段的養護工期、成本及定額Tab.1 Duration,maintenance cost and quota of each link

3.2 計算結果

采用MATLAB R2019a 對模型和算法進行編程，設置模型參數 ρ=10%，G=1 500，設置禁忌搜索算法參數Nmax=500.

由模型計算得到的最優養護調度方案如表2 所示.養護承包方收益的現值H主要受支付額pk、支付時間Jk及累計資金消耗等因素的影響，從收益最大化的角度出發，養護承包方將通過調整各路段養護的開始時間，獲得較高的支付額，并使支付時間提前，然而，有限的墊資能力使得對養護方案的調整受到限制，承包方必須保證一定的可用資金.因此，在不同的支付模式下，承包方需要在各路段的養護開始時間以及累計資金消耗之間做出均衡，從而使得在3 種不同的支付模式下，指派給3 個養護隊的路段以及各路段的養護順序均有較大的差異性，但3 種模式下的最優養護調度方案具有相同的養護工期，均為104 d.在基于時間進度的支付模式下，第1 次支付時間最早，為養護開始后的第29 天，但在該模式下承包方獲得最低的收益現值，即629.2 萬元；而在基于養護進度的支付模式下，第一筆支付金額最大，為659.0 萬元，且在該模式下承包方獲得最大的收益現值，為649.1 萬元.

表2 最優養護調度方案Tab.2 Optimal maintenance scheduling schemes

如圖5 所示，3 種支付模式下承包方的累計凈現金流具有相似的變化特征，即累計凈現金流在業主支付前持續下降并且在支付后迅速上升，當業主完成最后一次支付后，3 種支付模式下的承包方累計凈現金流量均達到674.0 萬元，等于合同總價減去養護成本的差值.3 種支付模式下的最大負累計凈現金流量分別為562.0、518.4、542.8 萬元，均低于養護承包方的墊資能力，即600.0 萬元，從而可以保證養護資金的持續周轉.

圖5 承包方累計凈現金流量變化Fig.5 Variation of contractor’s cumulative net cash flow

3.3 敏感性分析

3.3.1 墊資能力

設定承包方墊資能力U的變化幅度為50.0 萬元，變化范圍為400.0～650.0 萬元，敏感性分析結果如圖6 所示.隨著U的增加，承包方的收益現值H總體呈增長趨勢，但H的增長速度逐步降低，說明承包方的墊資能力所產生的邊際效益逐步降低.U=600.0 萬元和U=650.0 萬元時的養護調度方案相同，且具有相同的H，其主要原因是在同一種支付模式下，受養護隊數量限制，同時養護的路段不會超過3 條，因而承包方的資金消耗量有限，不需要進行過多的墊資.因此，當U達到一定的水平后，承包方繼續增加U不一定能獲得更優的養護調度方案且無法產生更多的收益現值.

圖6 墊資能力敏感性分析Fig.6 Sensitivity analysis of contractor’s advance-fund capacity

3.3.2 業主支付比例

業主的支付比例與支付額直接相關.如圖7 所示，當 β 由70%增加至95%時，H總體呈增長趨勢，并且兩者之間的變化近似單調遞增的關系，其主要原因是由模型目標函數的形式所導致的，從式（1）所知，pk與H是一元一次函數關系.

圖7 支付比例敏感性分析Fig.7 Sensitivity analysis ofpayment ratio

3.3.3 折現率

折現率的取值影響承包方的收益現值.設定 ρ以1%的幅度由8%增長至13%，承包方H的變化如圖8 所示.由目標函數可知，ρ 與H之間具有負指數關系，因此隨著 ρ 的增長，H逐步降低.

圖8 折現率敏感性分析Fig.8 Sensitivity analysis ofdiscount rate

3.3.4 養護隊數量

R的敏感性分析結果如圖9 所示.增加R可縮短養護工期，從而使業主的支付時間提前，因此隨著的R增加，H逐漸上升.但是，H的上升速度減慢，說明增加養護隊數量所產生的邊際收益降低.當R由5 個增加至6 個時，H未發生變化，其主要原因是過多的養護隊會增加承包方的資金消耗量，然而承包方的墊資能力是有限的，從而使資金消耗量受到限制.結合墊資能力的敏感性分析結果可知，只有當承包方的墊資能力和養護隊數量同步增長時，才能獲取更多的收益現值.值得注意的是，當養護隊數量增加至5 個時，基于時間進度的支付模式能使承包商獲得最大的收益現值，其原因是在該模式下，第一次支付時間最早且支付時間間隔較短.

圖9 養護隊數量敏感性分析Fig.9 Sensitivity analysis of maintenance crews

4 結 論

1）案例研究表明本文構建的路網養護最優調度模型可使養護承包方獲取最高的收益現值.在不同的支付模式下，指派給各養護隊的路段以及各路段的養護順序均有較大的差異性.對不同參數的敏感性分析結果可知承包方墊資能力、業主支付比例、折現率及養護隊數量等參數對承包方的收益現值具有較大的影響.

2）本文構建的公路網最優養護調度模型是針對確定型的養護調度問題，然而在實際養護中，養護工期、養護成本等可能存在不確定性，從而影響養護調度決策結果.因此，下一步將研究公路網養護的隨機調度問題.