兼顧成本與風險的渣土車運輸路徑優化模型

魏森，王永興，楊綠明，畢軍

（北京交通大學交通運輸學院，北京 100044）

0 引言

近年來，城市建設過程中產生的建筑垃圾占城市固體廢棄物的30%～40%，如何有效處理建筑垃圾已經成為各地政府及企業面臨的難題[1]。在建筑垃圾的處理過程中，運輸是整個流程的關鍵環節，其主要目標是通過渣土車將建筑垃圾從產生源運送至消納場或資源場進行處理。當前的建筑垃圾運輸流程首先需要運輸單位向政府部門提交包括運輸路徑信息的申請核準單，經審批部門核實通過后方可執行運輸任務。不同于常規車輛，渣土車在實際運輸過程中時常伴有超載、超速及拋灑等現象，故政府部門以保障人民群眾的生命和財產安全為重，在審核過程中更關注運輸路徑的安全性，而運輸單位則是從經濟性的角度出發更傾向于選擇成本較低的路徑。為此，在規劃渣土車運輸路徑時需要兼顧政府部門和運輸單位的需求，確保運輸路徑同時具備較好的安全性和經濟性。

國內外關于建筑垃圾運輸方面的研究主要側重于運輸過程監管，如Aleksanin[2]和White[3]分別從節約資源和保護環境的角度出發提出了針對建筑垃圾渣土車的管理策略；王瑾[4]以減少建筑垃圾運輸過程中交通事故發生率為目標，設計了一種渣土車動態跟蹤與管理系統；張學鋒[5]和李宇宏等[6]分別借助無線通信和圖像識別等技術建立建筑垃圾運輸監管平臺，以實現對渣土車的全過程智能化監管。有的學者是從路徑優化方面展開研究，如Dantzig等[7]首次基于運籌學理論對車輛路徑優化問題進行了深入探討，隨后Gillett等[8]和Schneider[9]進一步對車輛路徑優化問題的復雜性進行了研究，分別設計了掃描算法和禁忌搜索算法實現模型求解；劉蘭芬等[10]和柴獲等[11]分別以運輸風險和運輸距離為優化目標建立單目標車輛路徑優化模型；許冬明[12]進一步考慮實際運輸需求，提出同時考慮運輸時間和費用的多目標車輛路徑優化模型；陳婷婷[13]將時間窗約束融入路徑優化問題，建立了以運輸距離和風險最小為目標的多目標優化模型。此外，為有效解決多目標優化問題，現有研究在遺傳算法的基礎上設計了NSGA-Ⅱ算法，并將其廣泛應用于解決各類面向車輛路徑的組合優化模型，如Liu等[14]和徐慧英等[15]將NSGA-Ⅱ算法應用于車輛路徑多目標優化問題，得到權衡了多項優化目標的滿意解；Miguel等[16]將NSGA-Ⅱ算法引入帶時間窗的物流車輛路徑優化問題，研究結果證實NSGA-Ⅱ算法能夠有效處理實際場景規模下的多目標車輛路徑優化模型。

截至目前，關于車輛路徑優化問題的研究主要聚焦于通勤出行和物流配送等常規運輸場景，還沒有針對渣土車路徑優化方面的成果，所提出的方法忽略了渣土車在運輸環境和優化目標等方面的特殊性。為解決現階段渣土車運輸路徑難以兼顧經濟性和安全性的問題，本文在充分考慮建筑垃圾運輸特征的基礎上，擬提出同時考慮運輸成本和風險的渣土車運輸路徑優化模型，將時間成本、固定成本，以及運輸過程中產生的與渣土車流量、道路等級、單雙車道相關的風險因素納入模型的目標函數，并設計NSGA-Ⅱ算法對模型進行求解。最后通過山東省濟寧市渣土車實時監測數據設計實例對模型和算法的可行性和有效性進行驗證。

1 模型建立

渣土車的主要運輸任務是將建筑垃圾從產生源運送至消納場或資源場，故一般只有起點和終點，不考慮常規車輛路徑問題中經常涉及的中途客戶點。此外，建筑垃圾運輸需要綜合考慮運輸單位和政府部門的需求，做到兼顧經濟性和安全性。基于此，在充分考慮渣土車運輸特點的基礎上，本文將建立兼顧運輸成本和風險的多目標0-1整數規劃模型，旨在幫助相關企業和部門規劃出能夠同時降低運輸成本和風險的渣土車運輸路徑。

1.1 基本假設

考慮渣土車運輸的實際情況，對模型作出如下假設：

（1）渣土車的固定成本和時間成本已知。

（2）渣土車運輸過程中無拋灑，行駛速度均在限速之下。

（3）從起點到終點過程中，各路段均符合建筑垃圾運輸要求，渣土車可正常行駛，不會出現堵塞或無法通過等情況。

（4）路段風險值可疊加，路徑的總風險值為各路段風險值之和。

（5）不同路徑的相同路段渣土車流量和平均速度相同。

1.2 目標函數

本文模型兼顧運輸成本和風險，其中運輸成本包括固定行駛成本和時間成本；運輸風險主要與所經路段的渣土車流量、道路等級以及單雙車道指標有關。

（1）固定成本

渣土車運輸過程中產生的固定成本主要包括車輛維護費和司機工資等基本費用，且單次運輸的總固定成本受行駛距離的影響，具體計算公式如下：

式（1）中：C11為總運輸固定成本（元）；c1為渣土車單位距離行駛成本（元/km），可以從研究區域內建筑垃圾運輸單位提供的數據中獲取；K為研究區域內的節點集合；i,j為節點，兩個節點可構成一條路段ij；dij為路段ij的行駛距離（km），可以從當地城市管理局提供的數據中獲取；xij為模型的0-1 決策變量，用以確定車輛是否經過路段ij，若經過則等于1，反之等于0。

（2）時間成本

時間成本主要體現為渣土車完成一次單程運輸所消耗的時間。消納場地點固定的情況下，每天運輸的總次數越多，則運輸單位盈利越多。每天運輸的總次數主要與運輸路徑長度和平均速度有關。路徑總運輸時間成本按下式計算：

式（2）中：C12為總運輸時間成本（元）；t為渣土車單位時間行駛成本（元/h），可以從研究區域內建筑垃圾運輸單位提供的數據中獲取；vij為車輛在路段ij的平均行駛速度（km/h），可以從當地城市管理局提供的數據中獲取；其他變量含義同前。

（3）運輸風險

建筑垃圾渣土車在執行任務時面臨的運輸風險受多方面因素的影響，其中渣土車流量、道路等級和單雙車道是主要影響因素，因此模型中涉及的路段風險值主要考慮這3 個方面。渣土車龐大的體積使得渣土車流量成為建筑垃圾運輸過程中造成交通事故的嚴重隱患，路段上的渣土車數量越多，安全風險就越大；渣土車在較為狹窄的道路上行駛時會增大交通事故發生風險，通常道路越寬闊、路面越平坦，渣土車的運行相對就越安全，而道路等級是反映道路狀況的主要因素，道路等級越高則渣土車運輸環境越安全；雙向單車道由于允許不同車輛在同一條車道上相向而行，故會增加交通事故風險，而雙向雙車道可將不同方向行駛的車輛分配在不同車道，相對來說更加安全。需要說明的是，本文只考慮雙向單雙車道，而對單向單車道不作考慮，因為渣土車的行駛環境多以城市的雙向車道為主。路段總風險值為渣土車流量、道路等級和單雙車道三者風險值之和，計算公式為：

式（3）中：Rij為路段ij的風險值；R1ij為路段ij與渣土車流量相關的風險值；R2ij為路段ij與道路等級相關的風險值；R3ij為路段ij與單雙車道相關的風險值。

上述3 項風險值可以先通過實測數據和層次分析法獲得初始風險評估值，然后分別結合渣土車流量、道路等級和單雙車道指標的百分制評價得分轉化而來[17]。

（4）目標函數建立

基于上文提出的固定成本、時間成本和運輸風險計算式，建立目標函數。首先，將固定成本和時間成本歸為運輸成本，以總運輸成本最小為目標構建目標函數：

式（4）中：COD為起點到終點的總運輸成本（元）；C11和C12的含義同前。

然后，定義路徑總風險值為各路段風險值的加權平均，其中將各路段的行駛距離視為權重，建立以總風險值最小為目標的目標函數：

式（5）中：ROD為起點到終點的總運輸風險值；其他參數和變量含義同前。

1.3 約束條件

結合建筑垃圾渣土車運輸特點，模型考慮約束條件包括路段約束、時間窗約束、節點連續性約束和起終點約束，具體如式（6）～式（9）所示。各式中除新出現的變量外，其余參數和變量含義同前。

（1）路段約束

對于每條路段，要保證渣土車最多只能單程通過一次：

（2）時間窗約束

根據運輸單位的要求，渣土車必須在規定的時間內完成運輸任務，且只能提前不能延誤：

式（7）中：T為渣土車運輸時間限制（h）。

（3）節點連續性約束

渣土車在選擇路段時需保證其連續性，即到達某節點后，必須從該節點出發前往下一節點，其中不包含起終點：

式（8）中：n為集合K中的節點總數；p為集合K中除起點和終點外的任意節點。

（4）起終點約束

通過構成路段節點之間的關系來判斷節點是否為運輸路徑的起終點，主要判斷依據為：若某節點為路徑起點，則該點在構成路段時只能作為出發點；若某節點為路徑終點，則該點在構成路段時只能作為到達點；若某節點不是路徑的起終點，則該點在構成路段時既可以作為出發點也可以作為到達點。基于此，建立終點約束表達式如下：

2 求解算法設計

本文建立的渣土車運輸路徑優化模型是多目標0-1 整數規劃模型且兩個優化目標之間存在矛盾沖突，通常難以求得兩者均為最優的解。一種有效解決此類問題的方法是同時對多個目標函數進行求解，得到Pareto 最優解集，其特點為優化其中一個目標函數時無法同時對其他所有目標函數優化[18]。NSGA-Ⅱ是一種基于遺傳算法改進得到的啟發式算法，同時也是一種用于解決多目標組合優化問題的有效算法，能夠準確得到多目標優化問題的Pareto 最優解集，具有較好的求解性能[19]。本文將采用NSGA-Ⅱ算法對渣土車的雙目標路徑優化模型進行求解。針對渣土車路徑優化模型，NSGA-Ⅱ的算法流程如圖1所示。

根據圖1，NSGA-Ⅱ算法流程具體如下：

步驟1：首先對生成的種群P0進行初始化，并設進化代數Gen=1；

步驟2：判斷是否生成新一代子種群，若生成則令進化代數Gen=2，否則對當前種群中個體進行非支配分層排序，并依次通過選擇、交叉和變異等遺傳算子操作形成第一代子種群P1，并取進化代數Gen=2；

步驟3：將父代種群P0和生成的子代種群P1合并成新種群P2；

步驟4：對新種群P2中的個體進行快速非支配排序，并計算每個Pareto等級中的個體擁擠度，根據精英保留策略選擇出優勝個體并組成下一代種群P3；

步驟5：對步驟4產生的新的進化種群P3再次經選擇、交叉和變異操作產生新一代子種群，并判斷是否達到算法收斂準則，如果達到則停止迭代，否則令Gen=Gen+1，回到步驟3，繼續循環。

3 實例分析

3.1 實例數據

現基于山東省濟寧市建筑垃圾管控實踐進行實例分析。實驗數據從城市建筑垃圾智慧監管平臺獲取，該平臺可以通過車載終端設備對渣土車的實時位置及速度進行監控，并收集相關數據。本文選取濟寧市的孟子大道、濟鄒路和崇文大道所在區域為研究對象，對渣土車運輸路徑進行規劃。該區域為濟寧市高新技術開發區，也是渣土車的重點活動區域。同時該區域道路網復雜，工業園區眾多，還有不少學校與居民區，因此渣土車運輸勢必會給周邊居民帶來諸多影響，選定該區域為研究對象具有一定的現實意義。

為采用NSGA-Ⅱ算法實現模型求解，對各路段節點按自然數順序編碼，其中將運輸起點路段節點編號設為1，終點為德源路與濟鄒路交叉口。編碼所用地圖采用中國行政區劃地圖，可顯示區域內道路網信息，有利于對道路交叉口進行編碼操作。由于起終點呈現出近似矩形對角線分布，因此僅在以起終點連線為對角線的矩形路網范圍內進行編碼。研究區域的完整路網結構如圖2所示。

在圖2 展示的實例研究區域中共包含56 個路段節點和90條路段，路段在圖中以各節點之間的連線表示，根據連線的顏色區分道路等級，其中橙色（如路段16-17）、淺黃色（如路段16-19）、白色（如路段17-34）依次表示道路等級較高、居中、較低。部分路段長度信息如表1所示。

表1 實例研究區域內部分路段長度

由表1可知，在實例研究區域的所有路段中，最短路段長度為0.36km（路段13-14），而最長路段長度為3.6km（路段5-18）。由模型可知，路段長度直接關乎固定成本、時間成本和運輸風險，因此是運輸路徑優化的關鍵指標之一。

實例研究區域內，部分路段的車輛平均速度如表2所示。

表2 實例研究區域內部分路段平均速度

城市交通路網的各路段行駛速度通常被限制在一定范圍內，且不同路段間的行駛速度差異不大。由表2 可知，最小路段平均速度為30km/h（路段2-4），而最大路段平均速度為51km/h（路段41-42 和路段42-47）。由模型可知，路段行駛速度主要對時間成本有顯著影響。

研究區域內，部分路段的渣土車流量風險值如表3所示。

表3 實例研究區域部分路段渣土車流量風險值

本文根據實際監測數據，將實例研究區域內路段的渣土車流量風險值設定在48～79之間。由模型可知，渣土車流量風險值是構成路段風險值的重要組成部分。

研究區域內，部分路段的道路等級風險值如表4所示。

表4 實例研究區域部分路段道路等級風險值

基于實際路網數據，本文根據路段的道路等級屬性，將實例研究區域的道路等級風險值設為20,40及60。道路等級越高，相應的風險值越小。

研究區域內，部分路段的單雙車道風險值如表5所示。

表5 實例研究區域部分路段單雙車道風險值

基于實際路網數據，本文根據路段的單雙車道屬性，確定各路段的單雙車道風險值分別為40和0。

此外，在運營成本參數方面，設單位里程產生的行駛成本c1=10元/km，單位時間成本t=10元/h，運輸時間限制為1h。為保證實驗的運行效率，本文采用JavaScript編寫NSGA-Ⅱ算法程序。

3.2 結果分析

將3.1 節中的實例數據代入渣土車路徑優化模型，并用NSGA-Ⅱ算法對模型進行求解。NSGA-Ⅱ算法參數設置如下：取初始種群規模大小為30，交叉概率為0.6，變異概率為0.1，迭代次數為150。算法求解結果如圖3所示。

算法迭代過程在圖3 中主要表現為以運輸成本最小為目標和以運輸風險最小為目標的目標函數值依次從右上角到左下角收斂，即越靠近坐標原點的個體其兩個目標函數值越小。統計所得優勝個體的運輸成本、運輸風險、對應路徑路段組成情況如表6所示。

表6 實例求解結果

圖4進一步給出了渣土車路徑優化問題的Pareto 最優解集。相比于當前采用的運輸路徑（即1-2-5-18-37-35-31-29-28-25-26-53-55-56，運輸成本值為168，運輸風險值為129 8），最優運輸路徑的運輸成本值分別減少了17.8%,15.4%,8.9%和19.6%，運輸風險值分別減少了16.1%,18.3%,24.6%和14.3%，均達到了最小化目標函數值的效果。

根據實例求解得到的4 條最優運輸路徑映射在地圖上，如圖5 所示，分別為：1-2-5-7-10-12-13-14-23-24-54-56,1-3-6-9-10-12-13-14-23-24-54-56,1-2-5-18-17-16-14-23-24-54-56,1-3-6-9-11-12-13-14-23-24-54-56。

觀察結果可知，優化后的運輸路徑整體上更偏向于選擇道路等級較高及雙車道的路段。此外，雖然渣土車流量的增大會帶來路徑運輸風險值的提升，但是選擇道路等級較高的雙車道路段依舊可以使總運輸風險值降低。運輸成本方面，模型得到的最優路徑更偏向于選擇平均速度較大且行駛距離較短的路段，從而有效降低固定成本和時間成本。

綜上分析，本文提出的多目標優化模型得到的最優路徑均達到了較好的優化效果，可為運輸單位提供多條不同的運輸優化路徑，具體運輸路徑的選擇則可結合實際路況及司機經驗等因素來綜合決策。

4 結語

針對建筑垃圾渣土車運輸路徑優化問題，本文提出了一種多目標0-1 整數規劃模型，其中目標函數涉及的因素包括固定成本、時間成本，以及關于渣土車流量、道路等級、單雙車道的風險值，并設計NSGA-Ⅱ算法進行求解。將所建模型和算法應用于山東省濟寧市渣土車運輸問題實例，結果表明NSGA-Ⅱ算法適合求解本文提出的渣土車路徑優化模型。通過對模型求解可以得到最優運輸路徑的Pareto 解集，且所得路徑的運輸成本和風險相較原路徑均明顯降低，其中運輸成本最多可以降低19.6%，運輸風險最多可以降低24.6%。實驗結果證明本文提出的渣土車路徑優化模型和求解算法是可行和有效的，可供決策者結合不同目標之間的權衡和實際路況制定多種不同運輸方案。

本文提出的路徑評價和優化模型及其求解算法主要側重于尋找最優運輸路徑，但忽略了模型與渣土車運輸監管平臺的融合。未來將進一步完善模型和算法，并與渣土車運輸監管平臺進行集成，實現運輸路徑一鍵評價，通過設定運輸起點與終點自動生成多條最優運輸路徑以供運輸單位選擇。同時，在使用中也可不斷對該運輸路徑優化體系做適當調整，使其更加符合實際需要。