多約束條件下城市道路環(huán)衛(wèi)車優(yōu)化配置與路徑規(guī)劃

聶慶慧，龍秀江，梁程，夏井新，歐吉順*

(1.揚州大學，建筑科學與工程學院，江蘇揚州 225127；2.東南大學，智能運輸系統(tǒng)研究中心，南京 211189）

0 引言

隨著城市化建設進程不斷加快，傳統(tǒng)人工作業(yè)方式已經(jīng)難以滿足日益增長的城市環(huán)衛(wèi)需求。相較于人工作業(yè)，機械化作業(yè)具有更加安全和高效的優(yōu)點，已經(jīng)成為我國大中型城市的主流環(huán)衛(wèi)作業(yè)方式。然而，針對機械化環(huán)衛(wèi)車輛的配置與調(diào)度，大部分城市仍主要依賴于市政管理人員的主觀經(jīng)驗，缺乏科學客觀的規(guī)劃與管理決策，從而造成車輛資源閑置或作業(yè)時行走路徑非最優(yōu)等突出問題。隨著“智慧城市”試點工作的不斷深化，環(huán)衛(wèi)領域亦迎來了“智能化”革命。由此，研究如何對環(huán)衛(wèi)車輛進行科學合理的配置與路徑規(guī)劃，使得“車盡其用和路徑最優(yōu)”，成為交通工程領域一項熱點研究課題。

車輛配置與路徑規(guī)劃問題可以從數(shù)學角度建模為以節(jié)點為研究對象的車輛路徑問題(Vehicle Routing Problem,VRP)[1]和以弧為研究對象的弧路徑問題(Arc Routing Problem,ARP)[2]。本文研究的環(huán)衛(wèi)車配置與路徑規(guī)劃問題屬于ARP。標準的ARP可以表述為：某車隊中的車輛從路網(wǎng)中某起始節(jié)點(交叉口或路網(wǎng)邊界出入口)出發(fā)，對所有有服務需求的弧(路段)進行遍歷作業(yè)1 次，對無服務需求的弧(路段)可以空駛通過多次，待所有作業(yè)完成后返回出發(fā)節(jié)點，最終建模目標是為所有指派車輛分配能夠滿足路網(wǎng)作業(yè)需求且成本最小或利益最大的行駛路徑。ARP在環(huán)衛(wèi)領域有著廣泛應用，包括：道路維護[3]、冬季道路除雪[4]及城市垃圾回收[5]等。盡管如此，現(xiàn)實中大多數(shù)應用問題由于作業(yè)任務的復雜性以及存在諸多現(xiàn)實約束條件，通常難以用標準的ARP 進行描述。為此，一些學者針對考慮不同現(xiàn)實約束條件的擴展ARP 展開了深入研究。

HUANG等[6]構(gòu)建了以周期性和中轉(zhuǎn)補給為約束條件的城市道路灑水ARP，并設計基于蟻群算法的啟發(fā)式求解策略，以在合理時間內(nèi)獲得一組近似最優(yōu)解；CHEN 等[7]提出一種魯棒優(yōu)化方法解決道路日常維護時服務時間不確定性的ARP，并運用分支平面切割算法進行求解；RIQUELME等[8]研究了含周期性約束和車輛行駛速度約束的道路灑水ARP，并通過設計一種精確數(shù)學優(yōu)化求解算法在小規(guī)模路網(wǎng)上獲得了令人滿意的車輛路徑規(guī)劃方案；MOFID 等[9]提出一種自適應搜索與鯨魚優(yōu)化相結(jié)合的算法搜尋城市固體垃圾收集的最佳路線；陳博曉等[10]綜合考慮服務水平約束和養(yǎng)護車輛工作時長限制，建立養(yǎng)護服務區(qū)域規(guī)劃模型，實現(xiàn)對養(yǎng)護區(qū)域作業(yè)時間的準確計算，為養(yǎng)護資源合理配置提供決策依據(jù)；考慮帶時間窗的甩掛運輸路徑優(yōu)化問題，邊展等[11]建立了以行駛時間最短為目標的優(yōu)化模型，并開發(fā)兩階段混合啟發(fā)式算法求解最優(yōu)車輛路徑組合；JIN 等[12]研究帶樞紐港靠泊時間選擇約束的船舶路線規(guī)劃與轉(zhuǎn)運協(xié)調(diào)問題，并設計了分支定價精確式和列生成啟發(fā)式兩類算法對其進行求解。

綜上，國內(nèi)外學者從不同工程應用角度探索了帶各類現(xiàn)實約束條件的ARP[13]。本文涉及的環(huán)衛(wèi)車優(yōu)化配置與路徑規(guī)劃問題屬于帶以下現(xiàn)實約束條件的ARP，包括：①作業(yè)時限約束，即對于每一作業(yè)路段要求車輛在給定時段內(nèi)完成作業(yè)任務；②不同道路功能等級下的服務次數(shù)約束，即要求車輛在不同功能等級路段上完成特定次數(shù)的作業(yè)任務(不同于僅需在給定路段上完成1次作業(yè)的標準ARP，本文的ARP 在部分路段上需要完成多次作業(yè))；③車輛行駛速度約束，即需要考慮作業(yè)和非作業(yè)兩類情形下的速度限制；④路網(wǎng)流量平衡約束，即駛?cè)肽彻?jié)點的車輛總數(shù)應該等于駛出該節(jié)點的車輛總數(shù)；⑤車輛退出約束，即車輛可以在用戶指定的路網(wǎng)中任一節(jié)點自由退出(包括起始節(jié)點)。本文ARP 的優(yōu)化目標是使車輛配置成本與車輛出行成本最小。由以上描述可知，該ARP 屬于典型的非確定多項式時間難題(Non-deterministic Polynomial-time Hardness,NP-hard)，具有較高的模型求解復雜度?？紤]到實際工程應用主要以節(jié)約環(huán)衛(wèi)運營成本為首要考量因素，且所設計的環(huán)衛(wèi)車調(diào)度方案允許以離線方式生成，而分支定價算法通過分支定界和列生成策略能夠顯著降低求解問題的復雜度，本文基于分支定價算法優(yōu)化求解所構(gòu)建的模型。利用蘇州工業(yè)園區(qū)19個真實區(qū)域路網(wǎng)綜合評估所提出的方法，并從經(jīng)濟成本、作業(yè)效率和環(huán)保效益這3 方面驗證所提方法的可行性和有效性。

1 問題描述與解決思路

本文模型構(gòu)建過程中涉及的數(shù)學變量符號含義說明如表1所示。

表1 本文模型構(gòu)建過程中涉及的數(shù)學變量符號含義說明Table 1 Description of mathematical symbols associated with model development in this study

本文環(huán)衛(wèi)車優(yōu)化配置與路徑規(guī)劃問題描述為：給定城市道路網(wǎng)絡拓撲G=(L,I)，其中，L為路段(弧)集合，I為交叉口(節(jié)點)集合，L=L′?L″，其中，L′為作業(yè)路段集合，L″為非作業(yè)路段集合。對于給定任務的b輛環(huán)衛(wèi)車，規(guī)劃其行駛路徑，使車輛從路網(wǎng)內(nèi)給定節(jié)點出發(fā)，遍歷所有作業(yè)路段L′完成作業(yè)任務，然后經(jīng)由用戶指定的路網(wǎng)中的任意節(jié)點退出。建模優(yōu)化目標是使環(huán)衛(wèi)運營成本最低。本文的環(huán)衛(wèi)運營成本包括車輛配置成本和車輛出行成本。車輛配置成本由車輛固有成本和配置車輛數(shù)目決定，車輛出行成本通過車輛在路網(wǎng)上的行駛時間進行量化評估。考慮的約束條件包括：①作業(yè)時限約束；②不同道路功能等級下服務次數(shù)約束；③車輛行駛速度約束；④路網(wǎng)流量平衡約束；⑤車輛退出約束?？紤]到城市道路環(huán)衛(wèi)作業(yè)在工作時通常會避開早晚高峰時段，本文在建模時忽略了高峰期不穩(wěn)定交通狀況對環(huán)衛(wèi)車作業(yè)的影響。路網(wǎng)中道路功能等級與其需求服務次數(shù)緊密相關(guān)，以保潔和清洗作業(yè)任務為例，路網(wǎng)中含有中央分隔帶和機非隔離帶的單向路段需作業(yè)2次，不含中央隔離帶的單向支路路段僅需作業(yè)1次。此外，在標準ARP中，車輛完成作業(yè)后通常會返回開始節(jié)點，而在本文所要解決的ARP 中，車輛需要根據(jù)用戶要求從路網(wǎng)中任一指定節(jié)點自由退出(包括起始節(jié)點)，這在增加工程應用靈活性的同時，也為建模帶來了挑戰(zhàn)性。根據(jù)上述需求分析，給出的解決思路如圖1所示。

圖1 城市道路環(huán)衛(wèi)車優(yōu)化配置與路徑規(guī)劃問題的解決思路Fig.1 Solutions to problem of optimal allocation and routing of sanitation vehicles on urban roads

2 城市道路環(huán)衛(wèi)車優(yōu)化配置與路徑規(guī)劃建模

2.1 時空網(wǎng)絡建模

本文研究的ARP 需要實現(xiàn)在多個現(xiàn)實約束下運營成本最小，其中，配置成本由調(diào)度的車輛數(shù)量決定，出行成本由車輛在路網(wǎng)上的行駛時間決定。行駛時間通過路段長度與車輛在該路段上的平均行駛速度計算獲得。環(huán)衛(wèi)車的平均行駛速度分為作業(yè)模式下的平均行駛速度和非作業(yè)模式下的平均行駛速度，其中，前者由環(huán)衛(wèi)機械化作業(yè)標準確定，后者設置為對應功能等級的道路限速。

為方便描述車輛在路網(wǎng)上的時空行駛軌跡，將道路物理網(wǎng)絡拓展為時空網(wǎng)絡。具體而言，將交叉口節(jié)點i擴展為時空點(i,j)，將路段(i,j)擴展為時空弧(i,j,t,s)，表示車輛由t時刻進入路段(i,j)，并在s時刻駛出，s-t為路段行駛時間。通過構(gòu)建時空網(wǎng)絡，將原始問題轉(zhuǎn)化為帶路段服務次數(shù)約束的網(wǎng)絡流問題。

為保證起始節(jié)點和終點節(jié)點流量守恒，本文構(gòu)建1 個虛擬起始時空節(jié)點和1 個終點時空節(jié)點，即所有車輛均由虛擬出發(fā)節(jié)點駛出，并在虛擬退出節(jié)點結(jié)束作業(yè)。由此，路網(wǎng)上所有起始時空節(jié)點和終點時空節(jié)點均為滿足流量守恒的普通節(jié)點，從而簡化了建模復雜度。同時，上述設置也可以保證環(huán)衛(wèi)車可由路網(wǎng)任一節(jié)點進入或退出。

環(huán)衛(wèi)車在實際行駛過程中包括兩種模式，即作業(yè)模式和非作業(yè)模式。為完整描述車輛行駛軌跡，并保證車輛在時空網(wǎng)絡上的流量守恒，分別構(gòu)建作業(yè)時空弧A′和非作業(yè)時空弧A″。對于作業(yè)時空弧(i,j,t,s) ∈A′，s-t為車輛處于作業(yè)模式下通過路段(i,j)所需時間；對于非作業(yè)時空弧(i,j,t,s)∈A″，s-t為車輛處于非作業(yè)模式下通過路段(i,j)所需時間。

假設1個含3個節(jié)點的示例物理網(wǎng)絡及其拓展的時空網(wǎng)絡。節(jié)點1到節(jié)點2的作業(yè)時間為1個時間單位，節(jié)點2 到節(jié)點3 的作業(yè)時間為2 個時間單位。環(huán)衛(wèi)車從節(jié)點1到節(jié)點2的允許作業(yè)時間范圍為[2,4]。在規(guī)定時間范圍內(nèi)完成作業(yè)的時空弧表示為有效時空弧；否則，表示為無效時空弧。等待弧表示環(huán)衛(wèi)車到達作業(yè)路段的時間早于路段服務最早時間的情形。在構(gòu)建時空網(wǎng)絡時，通過刪除處于規(guī)定作業(yè)時間范圍外的無效時空弧有效刻畫環(huán)衛(wèi)車在作業(yè)路段上的作業(yè)時限約束。物理網(wǎng)絡及其拓展的時空描述示例如圖2所示。

圖2 物理網(wǎng)絡及其拓展時空網(wǎng)絡描述示例Fig.2 Description example of physical network and its corresponding time-space network

1 輛車的時空行駛軌跡描述示例如圖3所示，加粗實線表示車輛處于作業(yè)模式下的行駛路段，虛線表示車輛處于非作業(yè)模式下的行駛路段。車輛由0 時刻從起始節(jié)點1 出發(fā)，經(jīng)過3 個時間單位作業(yè)至節(jié)點2，然后，經(jīng)過6個時間單位作業(yè)至節(jié)點3，之后，按照非作業(yè)速度行駛2 個時間單位至節(jié)點5，最后，經(jīng)過4 個時間單位作業(yè)至節(jié)點6 完成環(huán)衛(wèi)作業(yè)任務。上述車輛時空行駛軌跡可以描述為(1,2,0,3)→(2,3,3,9)→(3,5,9,11)→(5,6,11,15)。

圖3 車輛時空行駛軌跡描述示例Fig.3 Description example of a vehicle spatiotemporal travel trajectory

2.2 優(yōu)化模型構(gòu)建

令O為所有車輛的虛擬出發(fā)節(jié)點，并建立非作業(yè)時空弧(O,j,0,0)∈A″與路網(wǎng)時空節(jié)點(j,0)相連。需要注意的是，時空弧(O,j,0,0)表示由0 時刻從虛擬節(jié)點O出發(fā)，并在0 時刻到達節(jié)點j，該建模方式用以描述車輛可由路網(wǎng)任一節(jié)點開始作業(yè)。定義D為所有車輛的虛擬退出節(jié)點，并建立作業(yè)時空弧(i,D,t,t)∈A′與路網(wǎng)時空節(jié)點(i,t)相連，用以描述車輛可在任意時刻由路網(wǎng)任一節(jié)點結(jié)束作業(yè)。城市道路環(huán)衛(wèi)車輛配置及路徑優(yōu)化模型建立如下。

目標函數(shù)為

流量平衡約束為

服務約束為

決策變量為

式(1)由兩部分組成，其中，第1 部分表示環(huán)衛(wèi)車輛的配置成本(固定使用成本)，第2 部分表示所有環(huán)衛(wèi)車完成作業(yè)任務的總行駛時間；式(2)為路網(wǎng)流量守恒約束，對于非虛擬節(jié)點O和D路網(wǎng)中的其他時空節(jié)點需保持流量守恒，即進出任意一時空節(jié)點的車輛數(shù)相等；式(3)表示從虛擬節(jié)點O駛出的所有車輛數(shù)量應該和最后從虛擬節(jié)點D退出的車輛數(shù)量保持一致；式(4)保證了對于所有需要服務路段(i,j)∈L′，滿足車輛在作業(yè)模式下駛過該路段的次數(shù)大于等于最少作業(yè)服務次數(shù)。

在目標函數(shù)中，當yO,j,0,0=1時，表示有1輛車從虛擬節(jié)點O駛出進入節(jié)點j開始作業(yè)，對所有的yO,j,0,0求和，可得到進行環(huán)衛(wèi)作業(yè)的總車輛數(shù)。上述環(huán)衛(wèi)車輛最優(yōu)配置與路徑規(guī)劃問題本質(zhì)上屬于雙目標規(guī)劃問題，可構(gòu)建雙層規(guī)劃模型進行求解。然而，考慮到雙層規(guī)劃問題求解復雜度較高，本文通過線性加權(quán)法將第1部分的目標函數(shù)乘以1個大常數(shù)M，讓模型在車輛數(shù)最少的情形下有效優(yōu)化目標函數(shù)中第2 部分的目標函數(shù)，將雙目標規(guī)劃問題轉(zhuǎn)化為單目標規(guī)劃問題，有效簡化建模復雜度。

3 求解算法設計

考慮到實際應用中主要以節(jié)約環(huán)衛(wèi)運營成本為首要考量因素，且分支定價算法是一種適用于大規(guī)模問題的精確式求解算法，本文基于分支定價算法求解模型。該算法的基本思想是通過設計列生成算法與分支定界算法求解整數(shù)規(guī)劃問題的松弛問題。首先，基于Dantzing-Wolfe分解技術(shù)(D-W分解技術(shù))將原始問題的數(shù)學模型分解為環(huán)衛(wèi)車運營總成本最小的主問題和含有多條件約束最短路徑的子問題；其次，利用列生成算法求解主問題的松弛問題，求得的初始解生成部分可行列，形成受限主問題(Restricted Master Problem，RMP)；然后，求解RMP 得到對偶變量，再將其帶入子問題中重新定價，通過求解子問題檢驗數(shù)小于0 的列添加到RMP 中再次迭代，直到求得最優(yōu)整數(shù)解。分支定價算法的主要工作流程如圖4所示。

圖4 分支定價算法的主要工作流程Fig.4 Main workflow of branch-and-price algorithm

3.1 Dantzing-Wolfe分解

考慮到本文ARP 模型的變量和約束條件數(shù)量較多，利用Dantzig-Wolfe 分解算法提升求解速度，基本思想是將原始問題分解為若干個規(guī)模較小的子問題，通過求解子問題進而得到原問題的最優(yōu)解。為獲得高質(zhì)量的線性規(guī)劃問題松弛值，設計路徑?jīng)Q策變量構(gòu)建模型，并對其進行Dantizg-Wolfe分解。假定所有滿足約束條件的可行路徑集為R，即R為環(huán)衛(wèi)車從虛擬節(jié)點出發(fā)，完成作業(yè)任務后生成的所有可行路徑集合，則所求解的問題可轉(zhuǎn)化為從R中選擇若干條路徑組成1 個可行解，使模型的目標函數(shù)值最小。

3.1.1 主問題建模

模型分解過程涉及的參數(shù)變量定義如表2所示。令ci,j,t,s=croad·di,j,t,s，則車輛在路徑r上的總成本cr為

表2 模型分解過程涉及的符號說明Tabel 2 Symbol description associated with model decomposition

通過上述定義，構(gòu)建主問題模型如下。

目標函數(shù)為

服務約束為

決策變量為

式(7)為目標函數(shù)；式(8)表示車輛在作業(yè)模式下駛過該路段的次數(shù)大于等于其最少服務次數(shù)。由于無法枚舉主問題模型的所有可行路徑，需要利用列生成算法迭代的過程轉(zhuǎn)化為求解主問題的松弛問題。

3.1.2 子問題建模

依據(jù)上述主問題的松弛問題得到其對偶模型為

設zi,j,t,s為對偶問題最優(yōu)解，則主問題對偶模型檢驗數(shù)為

子問題模型可構(gòu)建為

式(14)中，子問題目標函數(shù)與檢驗數(shù)表達式相同，本質(zhì)是盡可能尋找使得檢驗數(shù)小于0 的列，并將該列帶入到主模型中迭代，優(yōu)化當前最優(yōu)解。在初始狀態(tài)下，主問題需要通過初始解求得對偶值，對子問題進行定價。然后，將子問題求得的路徑集作為新的列加入到原始路徑集中，并對主問題求解，得到新的解zi,j,t,s，對子問題重新定價，并繼續(xù)尋找有效路徑集合。通過不斷迭代，直至無法找到有效路徑為止。上述過程描述如下：

Step 1 初始化主問題，生成主問題所需的初始路徑集合R。

Step 2 求解主問題，得到子問題模型所需的解zi,j,t,s，并重新定價。

Step 3 求解子問題，搜索滿足條件的最短路徑集合。

Step 4 若集合為非空集，則將集合中所有的路徑加入到R中，并且在主問題模型中生成對應新的列，轉(zhuǎn)Step2；否則，轉(zhuǎn)Step5。

Step 5 用分支策略求解主問題的整數(shù)解。

3.2 分支策略設計

由上述描述可知，從包含部分列的主問題出發(fā)，求得使子問題目標函數(shù)值(對偶模型的檢驗數(shù))小于0 的解，并將其作為新列帶入主問題求解過程，可為主問題的松弛問題提供更近的下界。當子問題的目標函數(shù)無法產(chǎn)生小于0的解時，可以獲得主問題線性松弛問題的最優(yōu)解。在此基礎上，利用基于弧的分支策略求得最優(yōu)整數(shù)解。

本文設計的基于弧的分支策略為：首先，將基于路徑的浮點數(shù)解轉(zhuǎn)化為與其對應弧的浮點數(shù)值。當存在浮點數(shù)解時，可以找到兩條路徑r1和r2，滿足路徑r1經(jīng)過弧(i,j)訪問j點，路經(jīng)r2經(jīng)過弧(m,j)訪問j點(i≠m)；然后，對弧的浮點數(shù)值取整，優(yōu)先選擇值改變較大的弧。假設選擇弧(i,j)，則存在兩個分支，即最優(yōu)解中是否包含該弧。當最優(yōu)解中存在弧(i,j)時，將其他所有到達j點的弧的成本和其他所有離開i點的弧的成本設為足夠大的值，并重新計算；反之，只需設弧(i,j)的成本為足夠大的值，并且在已有的路徑集中刪除包含弧(i,j)的路徑，再重新計算。具體步驟如下：

Step 1 初始化主問題分支定界樹的根節(jié)點，生成初始路徑集合R。

Step 2 通過初始解得到部分可行列集合，從而構(gòu)建RMP。

Step 3 求解RMP，傳遞對偶變量，重新定價子問題。

Step 4 判斷檢驗數(shù)-dr是否小于0，若小于0，將小于0的檢驗樹對應的列加入RMP中，并轉(zhuǎn)Step 3；否則，轉(zhuǎn)Step 5。

Step 5 求解主問題模型，若解為整數(shù)解，則轉(zhuǎn)Step 6；否則，轉(zhuǎn)Step 7。

Step 6 與當前的上界進行比較，若小于上界，則更新上界值，并且根據(jù)新的上界值，對分支定界樹進行剪支，轉(zhuǎn)Step 8。

Step 7 若浮點數(shù)解小于當前的上界，則根據(jù)上述分支策略選擇1 條弧進行分支，刪除當前節(jié)點，將分支節(jié)點加入路徑集合中；否則，無需進行分支操作。

Step 8 若路徑集合為非空集合，則轉(zhuǎn)Step 2；否則，轉(zhuǎn)Step 9。

Step 9 當前上界的值即為最優(yōu)整數(shù)解。

4 實驗結(jié)果與分析

本文以蘇州工業(yè)園區(qū)19個真實道路網(wǎng)絡的環(huán)衛(wèi)車優(yōu)化配置與路徑規(guī)劃問題為例，評估所提出的方法。依據(jù)路段數(shù)量和節(jié)點數(shù)量將19個路網(wǎng)劃分為中小規(guī)模路網(wǎng)和大規(guī)模路網(wǎng)。19 個實例路網(wǎng)的車輛作業(yè)任務特征描述如表3所示。其中，路段數(shù)小于70 且節(jié)點數(shù)小于50 的為中小規(guī)模路網(wǎng)，共10個，在表中標記為S1～S10；路段數(shù)大于70且節(jié)點數(shù)大于50 的為大規(guī)模路網(wǎng)，共9 個，在表中標記為L1～L9。

表3 待評估路網(wǎng)的作業(yè)任務特征Tabel 3 Task characteristics of evaluated road networks

4.1 路網(wǎng)拓撲構(gòu)建

為提取道路網(wǎng)絡拓撲，首先，從OpenStreetMap網(wǎng)站下載蘇州工業(yè)園區(qū)城市路網(wǎng)地理信息數(shù)據(jù)文件；然后，對數(shù)據(jù)文件進行解析、信息提取和預處理，生成結(jié)構(gòu)化的路網(wǎng)節(jié)點和路段關(guān)聯(lián)數(shù)據(jù)；最后，基于QGIS(Quantum Geographic Information System，QGIS)軟件對生成的路網(wǎng)節(jié)點和路段數(shù)據(jù)進行路網(wǎng)拓撲構(gòu)建與可視化。根據(jù)蘇州市市政管理要求和環(huán)衛(wèi)作業(yè)任務，從蘇州工業(yè)園區(qū)路網(wǎng)提取19 個相互獨立的環(huán)衛(wèi)作業(yè)路網(wǎng)為本文研究路網(wǎng)。19個環(huán)衛(wèi)作業(yè)路網(wǎng)的道路網(wǎng)絡拓撲如圖5所示。

圖5 蘇州工業(yè)園區(qū)19個環(huán)衛(wèi)作業(yè)路網(wǎng)拓撲Fig.5 Network topologies of 19 local area networks in Suzhou Industrial Park

4.2 實驗結(jié)果分析

4.2.1 評估指標

本文從經(jīng)濟成本、作業(yè)效率和環(huán)保效益這3個方面評估所提出方法的可行性和有效性。其中，經(jīng)濟成本用運營成本指標進行評估；作業(yè)效率用車輛路徑有效率指標進行評估；環(huán)保效益用環(huán)衛(wèi)車作業(yè)過程中產(chǎn)生的碳排放量指標進行評估。

(1)運營成本

在運營成本中，車輛配置成本計算為所有環(huán)衛(wèi)車的采購成本，車輛出行成本計算為所有環(huán)衛(wèi)車在路網(wǎng)上行駛的總公里數(shù)與每公里作業(yè)單價乘積的累計總和。令路網(wǎng)環(huán)衛(wèi)作業(yè)運營總成本為C，定義為

式中：B為路網(wǎng)上配置的環(huán)衛(wèi)車的總數(shù)量；cveh為環(huán)衛(wèi)車的采購成本；為路網(wǎng)上第b輛環(huán)衛(wèi)車行駛通過的第k條路段的長度。

(2)車輛路徑有效率

路徑有效率E定義為配置的所有環(huán)衛(wèi)車在路網(wǎng)作業(yè)狀態(tài)下的行駛總里程L1與其完成指定作業(yè)任務所需的總行駛里程L2的比值，計算式為

式中：為路網(wǎng)上第b輛環(huán)衛(wèi)車在作業(yè)模式下，第k條路段的長度。路徑有效率E越接近100%，表明路網(wǎng)上環(huán)衛(wèi)車的作業(yè)效率越高，相應的路徑規(guī)劃也更合理。

(3)車輛碳排放量

車輛燃油能耗與其碳排放具有緊密關(guān)聯(lián)關(guān)系。首先，利用BARTH 等[16]提出的綜合排放模型測算所配置環(huán)衛(wèi)車的能耗；然后，基于燃油能耗與碳排放轉(zhuǎn)換關(guān)系估算路網(wǎng)上配置的環(huán)衛(wèi)車的總碳排放量。計算過程為

式中：為環(huán)衛(wèi)車在作業(yè)模式下的平均行駛速度；為環(huán)衛(wèi)車在非作業(yè)模式下的平均行駛速度；為路網(wǎng)上第b輛環(huán)衛(wèi)車在非作業(yè)模式下的第k條路段的長度；ξ為燃料和空氣的質(zhì)量比值；κ為柴油燃料熱值；ψ為能源從g·s-1到L·s-1的轉(zhuǎn)化因子；ω為環(huán)衛(wèi)車發(fā)動機的摩擦系數(shù)；α為環(huán)衛(wèi)車發(fā)動機轉(zhuǎn)速；φ為環(huán)衛(wèi)車的排量；η′為車輛轉(zhuǎn)動系統(tǒng)效率；η為柴油發(fā)動機效率參數(shù)；β為空氣的阻力系數(shù)；γ為車輛前方表面積；ρ為空氣密度；為路網(wǎng)上第b輛環(huán)衛(wèi)車在作業(yè)模式下的第k條路段上的燃油能耗量；為路網(wǎng)上第b輛環(huán)衛(wèi)車在非作業(yè)模式下的第k條路段上的燃油能耗量；δ為燃料對應的排放因子；Q為路網(wǎng)上環(huán)衛(wèi)車完成作業(yè)任務的碳排總量。本文ξ、κ、ψ、ω、α、φ、η′、η、β、γ和ρ這11 個參數(shù)依據(jù)文獻[17]提供的柴油環(huán)衛(wèi)車動力系數(shù)表進行取值，δ的設置則參考文獻[18]提供的IPCC2006修訂標準，取值為2.73 CO2kg·L-1。

4.2.2 算例分析

本文車輛配置數(shù)量B是3 個評估指標的關(guān)鍵參數(shù)。19 個實例路網(wǎng)優(yōu)化前后的配置車輛數(shù)量對比結(jié)果如表4所示。

表4 車輛配置數(shù)量優(yōu)化前后對比結(jié)果Tabel 4 Comparison results of number of allocated vehicles before and after optimization

由表4可知，對于中小規(guī)模路網(wǎng)而言，優(yōu)化后車輛配置數(shù)量平均下降31.95%，尤其是在路網(wǎng)S3、S5 和S6 上優(yōu)化效果較為顯著，分別下降50.00%、36.36%和45.45%；對于大規(guī)模路網(wǎng)而言，優(yōu)化后的車輛配置數(shù)量平均下降19.61%，在路網(wǎng)L7 上優(yōu)化效果最為顯著，下降了27.27%。由對比分析可知，所提出方法相較人工經(jīng)驗配置方法具有顯著優(yōu)勢。

(1)營運成本優(yōu)化對比分析

本文中，保潔車、灑水車和清洗車的采購單價分別設置為18 萬，15 萬，25 萬元·輛-1，平均行駛單價分別設置為18.7，23.43，39.37 元·km-1。19 個實例路網(wǎng)的運營成本優(yōu)化前后對比結(jié)果如圖6所示。

圖6 不同路網(wǎng)上環(huán)衛(wèi)車運營成本優(yōu)化前后對比結(jié)果Fig.6 Comparison results of operation cost of sanitation vehicles on different road networks before and after optimization

由圖6中可知，優(yōu)化后各個路網(wǎng)的配置成本和出行成本均顯著下降。對于中小規(guī)模路網(wǎng)而言，優(yōu)化后的總運營成本下降約871萬元，尤其是在路網(wǎng)S2、S8和S9上，對應的運營成本分別下降18.20%、21.43%和19.77%；對于大規(guī)模路網(wǎng)而言，其總運營成本下降約854萬元，下降比例較為顯著的兩個路網(wǎng)為L3和L7，分別下降了20.28%和18.87%。由對比結(jié)果可知，所提出的方法能夠顯著節(jié)約運營成本，產(chǎn)生顯著的經(jīng)濟效益。

(2)車輛路徑有效率優(yōu)化對比分析

由式(18)可知，路徑有效率E值越接近100%，規(guī)劃路徑中車輛行駛的非作業(yè)里程數(shù)越少，環(huán)衛(wèi)車路徑有效利用率越高。10 個中小規(guī)模實例路網(wǎng)上優(yōu)化后的車輛路徑有效率如表5所示。

表5 中小規(guī)模實例路網(wǎng)上優(yōu)化后的車輛路徑有效率Tabel 5 Routing efficiency of sanitation vehicles on medium-size road networks after optimization

由表5可知，中小規(guī)模路網(wǎng)上，優(yōu)化后車輛的平均路徑有效率可以達到97.40%。10個路網(wǎng)中有6 個路網(wǎng)在優(yōu)化后車輛路徑有效率達到了99%以上，其中，路網(wǎng)S3、S4和S6甚至可以達到100%。

9個大規(guī)模實例路網(wǎng)上優(yōu)化后的車輛路徑有效率如表6所示。

表6 大規(guī)模實例路網(wǎng)下車輛路徑有效率Tabel 6 Routing efficiency of sanitation vehicles on large-size networks after optimization

由表6可知，該規(guī)模路網(wǎng)上的平均車輛路徑有效率達到91.89%，其中，有7 個路網(wǎng)的路徑有效率到達90%以上，最高路徑有效率達到98%。對比結(jié)果表明，所提出方法能夠有效避免路段重復作業(yè)問題，有效提升環(huán)衛(wèi)車的作業(yè)效率。隨著路網(wǎng)規(guī)模不斷增加，路徑有效率有所下滑，但其平均路徑有效率仍高于90%，表明所提出方法在不同規(guī)模路網(wǎng)上均具有較好的適用性。

(3)碳排放優(yōu)化對比分析

從環(huán)保效益角度對所提出方法進行評估分析。優(yōu)化前后的碳排放對比結(jié)果如圖7所示。

由圖7可知，在中小規(guī)模路網(wǎng)上，優(yōu)化后的平均碳排放量下降了19.07%，其中，以S2、S7 和S10碳排放量下降效果最為顯著，分別下降了26.21%、21.04%和24.00%；在大規(guī)模路網(wǎng)上，優(yōu)化后平均碳排放量下降了21.47%，在路網(wǎng)L2、L4、L6和L7上碳排放量分別下降了23.68%、23.28%、23.09%和24.39%。綜合而言，無論是中小規(guī)模路網(wǎng)，還是大規(guī)模路網(wǎng)，優(yōu)化后碳排放量都有較為顯著的下降，表明，所提出方法能夠顯著降低環(huán)衛(wèi)車輛尾氣排放量，產(chǎn)生有效的城市環(huán)保效益。

4.3 車輛規(guī)劃路徑可視化

所構(gòu)建的優(yōu)化模型可與GIS相結(jié)合，用于輔助開發(fā)城市道路環(huán)衛(wèi)車智慧調(diào)度系統(tǒng)。以實例路網(wǎng)L9為例，模型輸出的環(huán)衛(wèi)車最優(yōu)規(guī)劃路徑在GIS上的可視化表征如圖8所示。

圖8 路網(wǎng)L9上環(huán)衛(wèi)車最優(yōu)路徑規(guī)劃GIS表征Fig.8 GIS representations of optimal routing paths of sanitation vehicles on road network L9

結(jié)合路徑可視化結(jié)果，市政管理人員可通過自定義環(huán)衛(wèi)車在作業(yè)路網(wǎng)中的進入節(jié)點和退出節(jié)點，實現(xiàn)對環(huán)衛(wèi)車輛的科學快速調(diào)度，有效提升環(huán)衛(wèi)運營與管理效益。

5 結(jié)論

本文通過綜合考慮環(huán)衛(wèi)車作業(yè)時限、服務次數(shù)、行駛速度和車輛退出節(jié)點等多約束條件，構(gòu)建了以車輛配置與出行總成本最小為優(yōu)化目標的環(huán)衛(wèi)車優(yōu)化配置與路徑規(guī)劃模型，并基于分支定價算法精確求解所構(gòu)建模型。從經(jīng)濟成本、作業(yè)效率和環(huán)保效益這3 方面綜合評估所提出方法。結(jié)果表明，同人工經(jīng)驗方法相比，所提出的方法在中小規(guī)模路網(wǎng)上，環(huán)衛(wèi)車配置數(shù)量下降31.95%，總運營成本下降約871 萬元，平均車輛路徑有效率達到97.40%，碳排放量降低19.07%；在大規(guī)模路網(wǎng)上，環(huán)衛(wèi)車配置數(shù)量下降19.61%，總運營成本下降約854 萬元，平均車輛路徑有效率達到91.89%，碳排放量降低21.47%。

盡管所提出方法考慮了多類現(xiàn)實約束條件，且能夠被有效應用于保潔、灑水、清洗等多類城市道路環(huán)衛(wèi)作業(yè)任務。然而，在現(xiàn)實應用中，環(huán)衛(wèi)車輛的調(diào)度仍會受到其他一些復雜約束條件的影響，例如，車輛容量限制、動態(tài)交通環(huán)境及作業(yè)周期性排班等，使得建模與求解過程仍充滿了挑戰(zhàn)性。