帶碳費約束的同時取送車輛路徑問題研究

段鳳華

(湖南科技大學商學院，中國 湘潭　411000)

帶碳費約束的同時取送車輛路徑問題研究

段鳳華*

(湖南科技大學商學院，中國 湘潭411000)

摘要在基本車輛路徑問題基礎上增加“同時取送”、“時間窗”與“碳費”三個約束條件，發展為帶碳費約束的有軟時間窗同時取送車輛路徑問題．建立了相應的數學模型，設計了以Or-opt為鄰域結構、增加碳費懲罰機制的禁忌搜索算法對模型求解．通過與相關文獻進行比較，顯示了禁忌搜索算法搜索速度和尋優能力的優越性．物流企業若能采用以較好算法開發的車輛調度軟件，將能削減其碳費，提升自身經濟效益和社會效益．

關鍵詞車輛路徑問題；同時取送貨；軟時窗；碳費；禁忌搜索

The Simultaneous Pick-up and Delivery VRP with Carbon Emissions Fee

DUANFeng-hua*

(School of Business, University of Science and Technology, Xiangtan 411000, China)

AbstractAdding simultaneous pick-up and delivery, soft time windows and carbon emissions constraints, the corresponding mathematical model is established to solve the basic vehicle routing problem, and the tabu search (TS) algorithm is designed to solve the problem based on Or-opt for the neighborhood structure and evaluation mechanisms with carbon emissions fee. Compared with relevant literatures, the TS is proved to be superior in speed and optimization capabilities. If logistics enterprises use good algorithm to develop scheduling software, the carbon emissions will be reduced and the economic and social benefits will be upgraded.

Key wordsvehicle routing problem; simultaneous pick-up and delivery; soft time windows; carbon emissions fee; tabu search

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

對有碳排放約束的物流業發展規劃，國外研究較多，最近的如文獻[1~5]，而國內研究較少，但也有個別研究成果，如文獻[6~8]．

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

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

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

為構造數學模型，定義變量如下．

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

根據問題描述，建立SPDVRPSTWCEF數學模型如下：

minZ1=K,

(1)

(2)

(3)

(4)

qj=Qk-dj+pj,?k,?j∈{1,2,…,n}

(5)

qj=qi-dj+pj,?i,j∈{1,2,…,n}

(6)

Qk≤Q,?k

(7)

qj≤Q,?j∈{1,2,…,n}

(8)

max{di,pi}≤Q,?i∈{1,2,…,n}

(9)

(10)

(11)

模型中，式(1)表示第一優化目標，即最小化車輛數；式(2)表示第二優化目標，即車輛行駛總費用最小(包括距離費用、碳排放懲罰費用、時間窗懲罰費用)；式(3)表示車輛k離開車場時載重量；式(4)表示車輛行駛距離限制；式(5)表示第k條路線從車場出發后，離開第一個客戶點時的載重量；式(6)表示客戶i和客戶j在同一路線且客戶j恰好在客戶i之后服務時，車輛k離開客戶j時的載重量；式(7)、(8)和(9)表示受車輛載重量的限制，車輛在取送作業過程中不能超出其載重量；式(10)表示K輛車都從配送中心出發，最后又回到配送中心；式(11)表示每個客戶只由一輛車配送且所有客戶都得到服務．

2禁忌搜索算法設計

禁忌搜索算法是對局部鄰域搜索的一種擴展，是一種全局逐步尋優的智能和通用啟發式算法．本算法將以隨機方式產生初始解．

2.1　鄰域結構

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

1)Or-opt-1,將一條路徑中1個頂點在另一條路徑中兩個頂點間重新定位，例如:

X1=(012340567089)→X1=(012405637089).

2)Or-opt-2,將一條路徑中2個頂點在另外一條路徑中兩個頂點間重新定位，例如:

X1=(012340567089)→X1=(012056347089).

3)Or-opt-3,將一條路徑中3個頂點在另外兩個頂點間重新定位，例如:

X1=(012340567089)→X1=(012563407089).

2.2　解的評價

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

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

2.3　禁忌表與終止準則

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

2.3.2終止準則當總迭代次數達到一個給定值，或在給定的連續迭代步數內當前最好解沒有改變時，則算法終止．

表1　客戶點數據表

3 算例分析

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

本算法對文獻[17]單向取貨與送貨問題求解，計算10次取最優解如表2所示，單向取貨問題與送貨問題目標函數值比文獻[17]節省的比率分別了1.89%和2.92%．

圖1　配送線路圖Fig.1　Delivery routes

本算法取最大迭代步數取800，對SPDVRPSTWCEF問題求解，計算10次結果如表3所示，其中最好解的總配送距離為100.95 km，車輛數為3輛，碳費為8.496元，總配送費用(即目標函數值)為109.45元，時間窗口內比例100%，運行時間0.2 s，對應的配送線路為(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所示．

本算法將沒有碳費的文獻[12]和[17] 最好解的總費用加上碳費后，與其進行比較，結果如表4和表5所示．

表4和表5顯示，在SPDVRPSTWCEF的幾項關鍵指標方面，本文設計的禁忌搜索算法計算研究結果多方面優于文獻[12]和[17]．本算法結果時間窗內比例100%，運行時間僅用了0.2 s．車輛數比文獻[12]和[17]分別節省了1和2，節省比率分別為25%和40%；配送距離比文獻[12]和[17]分別節省了11.94和67.85，節省比率分別為10.58%和40.20%；總配送費用比文獻[12]節省了14.08，節省比率為11.40%；本算法采用的同時取送貨策略，配送總費用比文獻[17]的雙向配送策略的總費用節省了73.86，節省比率為40.29%．

表2　本算法采用文獻[17]數據的單向取貨與送貨問題最優解比較

表3　本算法10次同時取送的結果

表4　本文結果與文獻[12]結果比較

*表示該碳費系根據該文獻中配送距離乘以每百公里碳排放懲罰系數得出.

表5　本文同時取送貨結果與文獻[17]雙向配送結果比較

*表示該碳費系根據該文獻中配送距離乘以每百公里碳排放懲罰系數得出．

5結論

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

參考文獻：

[1]BEHNAM F, MOHSEN R, TUPAN P,etal. 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,etal. 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]史春陽.同時取送貨的車輛路徑問題中的低碳研究[D].北京:清華大學， 2011.

[11]潘立軍. 求解帶軟時間窗取送化問題的遺傳算法[J].系統工程理論與實踐, 2012,32(1):120-126.

[12]關麗霞.帶軟時間窗和同時取送貨的車輛路徑問題研究[D].長沙: 中南大學, 2010.

[13]陳萍,黃厚寬,董興業. 求解卸裝一體化的車輛路徑問題的混合啟發式算法[J]. 計算機學報, 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].系統工程理論與實踐, 2004,24(3):123-128.

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

(編輯陳笑梅)

*通訊作者,E-mail：1012564884@qq.com

基金項目：湖南省自然科學基金資助項目(11JJ3082); 湖南科技大學博士基金項目(e510a7)

收稿日期：2015-01-07

中圖分類號TP391

文獻標識碼A

文章編號1000-2537(2015)03-0069-005

DOI:10.7612/j.issn.1000-2537.2015.03.013