帶碳費(fèi)約束的同時(shí)取送車輛路徑問題研究

段鳳華

摘 要 在基本車輛路徑問題基礎(chǔ)上增加“同時(shí)取送”、“時(shí)間窗”與“碳費(fèi)”三個(gè)約束條件，發(fā)展為帶碳費(fèi)約束的有軟時(shí)間窗同時(shí)取送車輛路徑問題.建立了相應(yīng)的數(shù)學(xué)模型，設(shè)計(jì)了以O(shè)r-opt為鄰域結(jié)構(gòu)、增加碳費(fèi)懲罰機(jī)制的禁忌搜索算法對模型求解.通過與相關(guān)文獻(xiàn)進(jìn)行比較，顯示了禁忌搜索算法搜索速度和尋優(yōu)能力的優(yōu)越性.物流企業(yè)若能采用以較好算法開發(fā)的車輛調(diào)度軟件，將能削減其碳費(fèi)，提升自身經(jīng)濟(jì)效益和社會(huì)效益.

關(guān)鍵詞 車輛路徑問題；同時(shí)取送貨；軟時(shí)窗；碳費(fèi)；禁忌搜索

中圖分類號(hào) TP391 文獻(xiàn)標(biāo)識(shí)碼 A 文章編號(hào) 1000-2537（2015）03-0069-005

在物流配送活動(dòng)中，同時(shí)取送貨現(xiàn)象廣泛存在，如快遞業(yè)，既要將快件、包裹送給客戶，又要從客戶處帶回需要寄出的快件或包裹；啤酒行業(yè)，銷售商需要用車輛將啤酒產(chǎn)品送到客戶處，可能同時(shí)又需要回收空瓶等等.另一方面，大量車輛行駛在路上，汽車尾氣排放過多，已成為全球空氣污染加重、特別是諸多地方霧霾彌漫的重要原因.一般而言，在車輛排量既定、路況相似的情況下，運(yùn)輸距離是影響油耗的最主要因素，而油耗是決定車輛碳排放量的關(guān)鍵因素，因此，本文將車輛運(yùn)輸距離轉(zhuǎn)化為碳排放量，進(jìn)而轉(zhuǎn)化為碳費(fèi).在安排車輛行駛線路時(shí)，同時(shí)考慮碳費(fèi)，以兼顧配送成本最小化和減少環(huán)境破壞，具有理論價(jià)值和現(xiàn)實(shí)意義.

對有碳排放約束的物流業(yè)發(fā)展規(guī)劃，國外研究較多，最近的如文獻(xiàn)[1～5]，而國內(nèi)研究較少，但也有個(gè)別研究成果，如文獻(xiàn)[6～8].

1 帶碳排放約束的有軟時(shí)窗同時(shí)取送車輛路徑問題描述與數(shù)學(xué)模型

車輛路徑問題（Vehicle Routing Problem，VRP） 是1959年由Dantzig和Ramser提出的[9]，本文研究帶碳費(fèi)的有軟時(shí)窗同時(shí)取送車輛路徑問題（The Simultaneous Pick-up and Delivery VRP with Soft Time Windows and Carbon Emissions Fee，SPDVRPSTWCEF）是基本車輛路徑問題的擴(kuò)展.SPDVRPSTWCEF是指車輛從配送中心出發(fā)，訪問客戶.客戶位置已知、車輛對客戶的送貨量和取貨量都已知、客戶所希望的服務(wù)時(shí)間窗口已知；車輛沿途一邊送貨一邊取貨，完成任務(wù)后，各車輛把取回的貨物送回配送中心；根據(jù)車輛在運(yùn)輸中產(chǎn)生的碳排放量對其征收一定的碳費(fèi)，以促使承運(yùn)人減少配送活動(dòng)中的碳排放.車輛在訪問各客戶時(shí)，允許其到達(dá)客戶開始服務(wù)的時(shí)間不在客戶所要求的時(shí)間窗口內(nèi)，但必須給予相應(yīng)懲罰；完成任務(wù)后，車輛返回車場.問題是如何給每輛車確定其行駛路線，使得在滿足裝載量和行駛距離限制的條件下，以最少車輛數(shù)、最短行駛距離，最小服務(wù)時(shí)間偏離，以及最少碳費(fèi)完成規(guī)定的貨物取送業(yè)務(wù).目前，關(guān)于SPDVRPSTWCEF的公開文獻(xiàn)還不多見，文獻(xiàn)[10]研究考慮CO2減排因素的同時(shí)取送貨車輛路徑問題，采用Xpress-MP軟件對案例的數(shù)學(xué)模型進(jìn)行求解.其他的文獻(xiàn)，如[11～13]，在研究同時(shí)取送貨問題時(shí)，都沒有涉及碳費(fèi).對SPDVRPSTWCEF研究成果的應(yīng)用，將極大地提高物流效率和效益，并將促進(jìn)物流運(yùn)輸配送優(yōu)化信息技術(shù)產(chǎn)品開發(fā)和應(yīng)用，促進(jìn)我國低碳物流和整個(gè)社會(huì)低碳經(jīng)濟(jì)的發(fā)展.

SPDVRPSTWCEF可以描述為：有1個(gè)車場（編號(hào)為0），擁有容量為Q的車輛若干輛，負(fù)責(zé)對n個(gè)客戶（編號(hào)為1，2…，n）進(jìn)行同時(shí)取送貨物工作，客戶i的貨物需求為di，且di≤Q，表示從客戶i取回的貨物量為pi （目的地為發(fā)車場），且pi≤Q，每個(gè)客戶只能由一輛車服務(wù)一次，車輛早于或遲于客戶規(guī)定的服務(wù)時(shí)間窗口服務(wù)，均須支付一定罰金，車輛須根據(jù)其所消耗燃料排放的CO2繳納碳費(fèi).車輛完成任務(wù)后，返回車場.

為構(gòu)造數(shù)學(xué)模型，定義變量如下.

K表示所需車輛數(shù)；Q表示車輛最大載重量；dij表示客戶i和客戶j的直接距離，假設(shè)距離矩陣對稱，即dij=dji；di表示送達(dá)給客戶i的貨物量（從發(fā)車場發(fā)出）； qi表示車輛離開客戶i時(shí)的載重量；Qk表示車輛k離開車場時(shí)載重量；ai表示客戶i的最早服務(wù)時(shí)間窗，bi表示客戶i的最晚服務(wù)時(shí)間窗；p1表示車輛到達(dá)時(shí)間違返最早時(shí)間窗時(shí)的懲罰系數(shù)，p2表示車輛到達(dá)時(shí)間違返最晚時(shí)間窗時(shí)的懲罰系數(shù)；p0表示碳費(fèi)率；si表示車輛在客戶i的服務(wù)時(shí)間；ti表示車輛到達(dá)客戶i的時(shí)間；c表示客戶單位距離配送成本，客戶i的貨物由車輛k 配送到則yik=1，否則yik=0；車輛k從客戶i行駛到客戶j則yijk=1，否則yijk=0；如果客戶i和客戶j在同一路線且客戶j恰好在客戶i之后服務(wù)，則車輛到達(dá)客戶j的時(shí)間為：tj=ti+si+tij；D表示車輛行駛總距離.

根據(jù)問題描述，建立SPDVRPSTWCEF數(shù)學(xué)模型如下：

模型中，式（1）表示第一優(yōu)化目標(biāo)，即最小化車輛數(shù)；式（2）表示第二優(yōu)化目標(biāo)，即車輛行駛總費(fèi)用最?。òň嚯x費(fèi)用、碳排放懲罰費(fèi)用、時(shí)間窗懲罰費(fèi)用）；式（3）表示車輛k離開車場時(shí)載重量；式（4）表示車輛行駛距離限制；式（5）表示第k條路線從車場出發(fā)后，離開第一個(gè)客戶點(diǎn)時(shí)的載重量；式（6）表示客戶i和客戶j在同一路線且客戶j恰好在客戶i之后服務(wù)時(shí)，車輛k離開客戶j時(shí)的載重量；式（7）、（8）和（9）表示受車輛載重量的限制，車輛在取送作業(yè)過程中不能超出其載重量；式（10）表示K輛車都從配送中心出發(fā)，最后又回到配送中心；式（11）表示每個(gè)客戶只由一輛車配送且所有客戶都得到服務(wù).

2 禁忌搜索算法設(shè)計(jì)

禁忌搜索算法是對局部鄰域搜索的一種擴(kuò)展，是一種全局逐步尋優(yōu)的智能和通用啟發(fā)式算法.本算法將以隨機(jī)方式產(chǎn)生初始解.

2.1 鄰域結(jié)構(gòu)

為了進(jìn)一步增強(qiáng)禁忌搜索算法的機(jī)能，以便能在減少所使用的車輛數(shù)和車輛行駛費(fèi)用兩個(gè)方面都能得到更好的改進(jìn).本文使用Or[14]提出Or-opt方法，該方法是將一段路徑（1個(gè)、2個(gè)、3個(gè)連續(xù)的頂點(diǎn)）在另外兩個(gè)頂點(diǎn)間重新定位，相當(dāng)于一個(gè)受約束的3-opt交換.Or-opt方法是k-opt中的一種，k-opt通過每次交換條邊來改進(jìn)初始解.對于k=2，3……，Lin[15]等人從大量計(jì)算中發(fā)現(xiàn)，3-opt最優(yōu)算法比2-opt好，而4-opt最優(yōu)算法并不比3-opt最優(yōu)算法好多少，而且k越大，計(jì)算量增大速度越快，運(yùn)算時(shí)間越長.本文根據(jù)Or-opt將一段路徑（1個(gè)、2個(gè)、3個(gè)連續(xù)的頂點(diǎn)）在另外兩個(gè)頂點(diǎn)間重新定位，設(shè)計(jì)了Or-opt-1，Or-opt-2，Or-opt-3三種交換的組合，以隨機(jī)的方式選擇其中一種應(yīng)用于當(dāng)前解.下面對可行變換進(jìn)行說明，其中帶下劃線者為所挑選的頂點(diǎn).在同一線路或不同兩條線路中隨機(jī)挑選兩個(gè)頂點(diǎn)（客戶點(diǎn)或車場），隨機(jī)執(zhí)行下列3種變換之一.

1） Or-opt-1，將一條路徑中1個(gè)頂點(diǎn)在另一條路徑中兩個(gè)頂點(diǎn)間重新定位，例如：

X1=（012340567089）→X1=（012405637089）.

2） Or-opt-2，將一條路徑中2個(gè)頂點(diǎn)在另外一條路徑中兩個(gè)頂點(diǎn)間重新定位，例如：

X1=（012340567089）→X1=（012056347089）.

3） Or-opt-3，將一條路徑中3個(gè)頂點(diǎn)在另外兩個(gè)頂點(diǎn)間重新定位，例如：

X1=（012340567089）→X1=（012563407089）.

2.2 解的評(píng)價(jià)

SPDVRPSTWCEF類型的車輛調(diào)度問題有兩個(gè)需要優(yōu)化的目標(biāo)：所使用的車輛數(shù)和最低總配送費(fèi)用（指行駛費(fèi)用、偏離時(shí)間窗的懲罰和碳費(fèi)）.最小化所使用的車輛數(shù)是第一層優(yōu)化目標(biāo)，具有較高的優(yōu)先權(quán).為了充分對解空間進(jìn)行搜索，算法接受導(dǎo)致不可行解的變換.違反了車輛裝載能力和最大行駛距離限制時(shí)，其不可行性的程度可以通過引入一個(gè)懲罰值而將該約束條件包含到目標(biāo)函數(shù)中去進(jìn)行度量，即

∑Kr=1{T（r）+ET（r）+p[E（r）+L（（r）]+c（r）}.

其中K是該解中所使用的車輛數(shù)（線路數(shù)）；T（r）為車輛r的行駛費(fèi)用；ET（r）為在線路r上早于或晚于時(shí)間窗卸下的部分；c（r）為碳費(fèi)；E（r）為在線路r上超出車輛載重量的部分；L（r）為在線路r上超出車輛行駛距離的部分；而p是懲罰系數(shù).若一個(gè)解是可行的，則所有線路上的E（r）都等于零.p∈[0.000 01，200 000]開始時(shí)等于1，并通過一個(gè)自調(diào)整參數(shù)來加權(quán)：每隔10次迭代測試一次，若前面的10個(gè)解都是可行的，則將其除于2；若所有的10個(gè)解都是不可行的，則將其乘于2.這種機(jī)制可以產(chǎn)生一種可行解和不可行解的混合，有利于減少陷入局部最優(yōu)的可能性[16].

2.3 禁忌表與終止準(zhǔn)則

2.3.1 禁忌表 禁忌表用于記載在最近的10次迭代中解的變換特征.可以構(gòu)造一組（n+1）×（n+1）階矩陣來記錄禁忌情況.若點(diǎn)i 和 j 被挑選來進(jìn)行以下三種變換：Or-opt-1，Or-opt-2，Or-opt-3三種交換，則將其禁忌情況存入矩陣的元素（i，j）中.在每一次迭代時(shí)，都必須將上一步所進(jìn)行的變換填入到禁忌表中，而表中的其他元素相應(yīng)地減1直到等于零為止.

2.3.2 終止準(zhǔn)則 當(dāng)總迭代次數(shù)達(dá)到一個(gè)給定值，或在給定的連續(xù)迭代步數(shù)內(nèi)當(dāng)前最好解沒有改變時(shí)，則算法終止.

3 算例分析

本算法已用Delphi語言編程，并在Pentium-Ⅳ 2.67 GHz微機(jī)上實(shí)現(xiàn).目前，對于本文研究的帶碳費(fèi)約束的車輛路徑問題，國際上還沒有統(tǒng)一的標(biāo)準(zhǔn)測試數(shù)據(jù)，為了方便對比分析，為了測試算法的計(jì)算效果，本文使用文獻(xiàn)[12]和[17]中的算例，客戶點(diǎn)數(shù)據(jù)表見表1，車場坐標(biāo)為（3.2，14.1），配送中心有若干輛載重量均為8 t的車，車輛最大的行駛距離為50 km，車輛行駛速度為20 km/h，每公里配送成本為1 元/h，為了提高客戶的滿意度，車輛早到在該客戶點(diǎn)等待，車輛晚于時(shí)間窗口服務(wù)則懲罰系數(shù)（p2）為6 元/h，沒有考慮服務(wù)時(shí)間（si=0）.需要優(yōu)化的目標(biāo)：最小化所需車輛總數(shù)，最小化總配送費(fèi)用.碳費(fèi)計(jì)量方面，為了簡化問題，參照澳大利亞政府CO2排放稅擬征收標(biāo)準(zhǔn)（23澳元/t，約相當(dāng)于人民幣160元），定為0.16 元/kg CO2；載重量8 t的車百公里油耗約為20 L，根據(jù)BP中國碳排放計(jì)算器提供的資料，1 L柴油排放2.63 kg CO2，所以每百公里碳排放懲罰系數(shù)=20×2.63×0.16=8.416（元）.

本算法對文獻(xiàn)[17]單向取貨與送貨問題求解，計(jì)算10次取最優(yōu)解如表2所示，單向取貨問題與送貨問題目標(biāo)函數(shù)值比文獻(xiàn)[17]節(jié)省的比率分別了1.89%和2.92%.

本算法取最大迭代步數(shù)取800，對SPDVRPSTWCEF問題求解，計(jì)算10次結(jié)果如表3所示，其中最好解的總配送距離為100.95 km，車輛數(shù)為3輛，碳費(fèi)為8.496元，總配送費(fèi)用（即目標(biāo)函數(shù)值）為109.45元，時(shí)間窗口內(nèi)比例100%，運(yùn)行

時(shí)間0.2 s，對應(yīng)的配送線路為（1）0-12-7-20-1-6-14-0，（2）0-13-5-4-16-17-19-15-0，（3） 0-9-18-11-10-3-2-8-0，配送線路圖如圖1所示.

本算法將沒有碳費(fèi)的文獻(xiàn)[12]和[17] 最好解的總費(fèi)用加上碳費(fèi)后，與其進(jìn)行比較，結(jié)果如表4和表5所示.

表4和表5顯示，在SPDVRPSTWCEF的幾項(xiàng)關(guān)鍵指標(biāo)方面，本文設(shè)計(jì)的禁忌搜索算法計(jì)算研究結(jié)果多方面優(yōu)于文獻(xiàn)[12]和[17].本算法結(jié)果時(shí)間窗內(nèi)比例100%，運(yùn)行時(shí)間僅用了0.2 s.車輛數(shù)比文獻(xiàn)[12]和[17]分別節(jié)省了1和2，節(jié)省比率分別為25%和40%；配送距離比文獻(xiàn)[12]和[17]分別節(jié)省了11.94和67.85，節(jié)省比率分別為10.58%和40.20%；總配送費(fèi)用比文獻(xiàn)[12]節(jié)省了14.08，節(jié)省比率為11.40%；本算法采用的同時(shí)取送貨策略，配送總費(fèi)用比文獻(xiàn)[17]的雙向配送策略的總費(fèi)用節(jié)省了73.86，節(jié)省比率為40.29%.

5 結(jié)論

通過對SPDVRPSTWCEF進(jìn)行定義和描述，本文建立了SPDVRPSTWCEF數(shù)學(xué)模型.通過以隨機(jī)方式產(chǎn)生初始解、有3種Or-opt交換組合可隨機(jī)選擇一種應(yīng)用于當(dāng)前解、引入罰值對解進(jìn)行評(píng)價(jià)，設(shè)計(jì)了求解問題的禁忌搜索算法.與同類文獻(xiàn)的比較顯示，本文算法能得到較好的計(jì)算結(jié)果，計(jì)算效率也較高.說明采用同時(shí)取送貨的策略優(yōu)于雙向配送策略，物流企業(yè)在采用好的算法開發(fā)的軟件進(jìn)行車輛調(diào)度的情況下，企業(yè)能減少碳排放；即使征收一定的碳費(fèi)，企業(yè)仍能增加收益.因此，應(yīng)該鼓勵(lì)企業(yè)將新技術(shù)應(yīng)用于管理，以促進(jìn)低碳物流，同時(shí)提高企業(yè)運(yùn)營效率和經(jīng)濟(jì)效益.

參考文獻(xiàn)：

[1] BEHNAM F， MOHSEN R， TUPAN P， et al. The implications of carbon pricing in Australia： An industrial logistics planning case study[J].Trans Res Part D： Trans Environ， 2013，18（1）：78-85.

[2] STEPHANIE S. Policy in motion： reassembling carbon pricing policy development in the personal transport sector in British Columbia[J].Trans Geography， 2011， 19（6）：1474-1481.

[3] GEORGINA S HANNAH B， LAURA M， et al. Externalities and economic policies in road transport[J].Res Trans Econ， 2010，28（1）：2-45.

[4] KIM S T， HAN C H. Measuring environmental logistics practices [J].Asian Shipping Logist， 2011，27（2）：237-258.

[5] FEDELE I. The private and social cost efficiency of port hinterland container distribution through a regional logistics system[J]. Trans Res Part A： Policy and Practice， 2012，46（9）：1424-1448.

[6] JIANG B， LI J， MAO X Y. Container ports multimodal transport in China from the view of low carbon [J]. Asian Shipping Logist， 2012，28（3）：321-343.

[7] LI J， LIU X， JIANG B. An exploratory study on low-carbon ports development strategy in China [J]. Asian Shipping Logist， 2011，27（1）：91-111.

[8] YANG J H， GUO J D， MA S G. Distribution network design for carbon tax-constrained urban cold Chain logistics [J]. Ind Eng， 2012，15（5）：86-91.

[9] DANTZIG G， RAMSER J. The truck dispatching problem[J]. Manag Sci， 1959，2（6）：80-91.

[10] 史春陽.同時(shí)取送貨的車輛路徑問題中的低碳研究[D].北京：清華大學(xué)， 2011.

[11] 潘立軍. 求解帶軟時(shí)間窗取送化問題的遺傳算法[J].系統(tǒng)工程理論與實(shí)踐， 2012，32（1）：120-126.

[12] 關(guān)麗霞.帶軟時(shí)間窗和同時(shí)取送貨的車輛路徑問題研究[D].長沙： 中南大學(xué)， 2010.

[13] 陳 萍，黃厚寬，董興業(yè). 求解卸裝一體化的車輛路徑問題的混合啟發(fā)式算法[J]. 計(jì)算機(jī)學(xué)報(bào)， 2008，31（4）：565-573.

[14] OR I. Traveling salesman-type combinatorial optimization problems and their relation to the logistics of regional blood banking： [D]. Evanston， IL： Northwestern University， 1976.

[15] LIN S. Computer solutions of the traveling salesman problem[J]. Bell Syst Tech J， 1965，44（1）：2245-2269.

[16] 符 卓. 帶裝載能力約束的開放式車輛路徑問題及其禁忌搜索算法研究 [J].系統(tǒng)工程理論與實(shí)踐， 2004，24（3）：123-128.

[17] 朗茂祥. 物流配送車輛高度問題的模型和算法研究[D].北京：北京交通大學(xué)， 2002.

（編輯 陳笑梅）