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

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

0 引言

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

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

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

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

1 問題描述與解決思路

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

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

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

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

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

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

環(huán)衛(wèi)車在實(shí)際行駛過程中包括兩種模式，即作業(yè)模式和非作業(yè)模式。為完整描述車輛行駛軌跡，并保證車輛在時空網(wǎng)絡(luò)上的流量守恒，分別構(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)所需時間。

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

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

1 輛車的時空行駛軌跡描述示例如圖3所示，加粗實(shí)線表示車輛處于作業(yè)模式下的行駛路段，虛線表示車輛處于非作業(yè)模式下的行駛路段。車輛由0 時刻從起始節(jié)點(diǎn)1 出發(fā)，經(jīng)過3 個時間單位作業(yè)至節(jié)點(diǎn)2，然后，經(jīng)過6個時間單位作業(yè)至節(jié)點(diǎn)3，之后，按照非作業(yè)速度行駛2 個時間單位至節(jié)點(diǎn)5，最后，經(jīng)過4 個時間單位作業(yè)至節(jié)點(diǎn)6 完成環(huán)衛(wèi)作業(yè)任務(wù)。上述車輛時空行駛軌跡可以描述為(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é)點(diǎn)，并建立非作業(yè)時空弧(O,j,0,0)∈A″與路網(wǎng)時空節(jié)點(diǎn)(j,0)相連。需要注意的是，時空弧(O,j,0,0)表示由0 時刻從虛擬節(jié)點(diǎn)O出發(fā)，并在0 時刻到達(dá)節(jié)點(diǎn)j，該建模方式用以描述車輛可由路網(wǎng)任一節(jié)點(diǎn)開始作業(yè)。定義D為所有車輛的虛擬退出節(jié)點(diǎn)，并建立作業(yè)時空弧(i,D,t,t)∈A′與路網(wǎng)時空節(jié)點(diǎn)(i,t)相連，用以描述車輛可在任意時刻由路網(wǎng)任一節(jié)點(diǎn)結(jié)束作業(yè)。城市道路環(huán)衛(wèi)車輛配置及路徑優(yōu)化模型建立如下。

目標(biāo)函數(shù)為

流量平衡約束為

服務(wù)約束為

決策變量為

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

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

3 求解算法設(shè)計

考慮到實(shí)際應(yīng)用中主要以節(jié)約環(huán)衛(wèi)運(yùn)營成本為首要考量因素，且分支定價算法是一種適用于大規(guī)模問題的精確式求解算法，本文基于分支定價算法求解模型。該算法的基本思想是通過設(shè)計列生成算法與分支定界算法求解整數(shù)規(guī)劃問題的松弛問題。首先，基于Dantzing-Wolfe分解技術(shù)(D-W分解技術(shù))將原始問題的數(shù)學(xué)模型分解為環(huán)衛(wèi)車運(yùn)營總成本最小的主問題和含有多條件約束最短路徑的子問題；其次，利用列生成算法求解主問題的松弛問題，求得的初始解生成部分可行列，形成受限主問題(Restricted Master Problem，RMP)；然后，求解RMP 得到對偶變量，再將其帶入子問題中重新定價，通過求解子問題檢驗(yàn)數(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ī)模較小的子問題，通過求解子問題進(jìn)而得到原問題的最優(yōu)解。為獲得高質(zhì)量的線性規(guī)劃問題松弛值，設(shè)計路徑?jīng)Q策變量構(gòu)建模型，并對其進(jìn)行Dantizg-Wolfe分解。假定所有滿足約束條件的可行路徑集為R，即R為環(huán)衛(wèi)車從虛擬節(jié)點(diǎn)出發(fā)，完成作業(yè)任務(wù)后生成的所有可行路徑集合，則所求解的問題可轉(zhuǎn)化為從R中選擇若干條路徑組成1 個可行解，使模型的目標(biāo)函數(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)建主問題模型如下。

目標(biāo)函數(shù)為

服務(wù)約束為

決策變量為

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

3.1.2 子問題建模

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

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

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

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

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

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

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

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

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

3.2 分支策略設(shè)計

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

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

4.1 路網(wǎng)拓?fù)錁?gòu)建

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

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

4.2 實(shí)驗(yàn)結(jié)果分析

4.2.1 評估指標(biāo)

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

(1)運(yùn)營成本

在運(yùn)營成本中，車輛配置成本計算為所有環(huán)衛(wèi)車的采購成本，車輛出行成本計算為所有環(huán)衛(wèi)車在路網(wǎng)上行駛的總公里數(shù)與每公里作業(yè)單價乘積的累計總和。令路網(wǎng)環(huán)衛(wèi)作業(yè)運(yùn)營總成本為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è)任務(wù)所需的總行駛里程L2的比值，計算式為

式中：為路網(wǎng)上第b輛環(huán)衛(wèi)車在作業(yè)模式下，第k條路段的長度。路徑有效率E越接近100%，表明路網(wǎng)上環(huán)衛(wèi)車的作業(yè)效率越高，相應(yīng)的路徑規(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ā)動機(jī)的摩擦系數(shù)；α為環(huán)衛(wèi)車發(fā)動機(jī)轉(zhuǎn)速；φ為環(huán)衛(wèi)車的排量；η′為車輛轉(zhuǎn)動系統(tǒng)效率；η為柴油發(fā)動機(jī)效率參數(shù)；β為空氣的阻力系數(shù)；γ為車輛前方表面積；ρ為空氣密度；為路網(wǎng)上第b輛環(huán)衛(wèi)車在作業(yè)模式下的第k條路段上的燃油能耗量；為路網(wǎng)上第b輛環(huán)衛(wèi)車在非作業(yè)模式下的第k條路段上的燃油能耗量；δ為燃料對應(yīng)的排放因子；Q為路網(wǎng)上環(huán)衛(wèi)車完成作業(yè)任務(wù)的碳排總量。本文ξ、κ、ψ、ω、α、φ、η′、η、β、γ和ρ這11 個參數(shù)依據(jù)文獻(xiàn)[17]提供的柴油環(huán)衛(wèi)車動力系數(shù)表進(jìn)行取值，δ的設(shè)置則參考文獻(xiàn)[18]提供的IPCC2006修訂標(biāo)準(zhǔn)，取值為2.73 CO2kg·L-1。

4.2.2 算例分析

本文車輛配置數(shù)量B是3 個評估指標(biāo)的關(guān)鍵參數(shù)。19 個實(shí)例路網(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àn)配置方法具有顯著優(yōu)勢。

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

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

圖6 不同路網(wǎng)上環(huán)衛(wèi)車運(yùn)營成本優(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)化后的總運(yùn)營成本下降約871萬元，尤其是在路網(wǎng)S2、S8和S9上，對應(yīng)的運(yùn)營成本分別下降18.20%、21.43%和19.77%；對于大規(guī)模路網(wǎng)而言，其總運(yùn)營成本下降約854萬元，下降比例較為顯著的兩個路網(wǎng)為L3和L7，分別下降了20.28%和18.87%。由對比結(jié)果可知，所提出的方法能夠顯著節(jié)約運(yùn)營成本，產(chǎn)生顯著的經(jīng)濟(jì)效益。

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

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

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

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

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

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

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

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

從環(huán)保效益角度對所提出方法進(jì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)。以實(shí)例路網(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)中的進(jìn)入節(jié)點(diǎn)和退出節(jié)點(diǎn)，實(shí)現(xiàn)對環(huán)衛(wèi)車輛的科學(xué)快速調(diào)度，有效提升環(huán)衛(wèi)運(yùn)營與管理效益。

5 結(jié)論

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

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