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

1、帶碳費(fèi)約束的同時(shí)取送車輛路徑問題研究 摘 要 在基本車輛路徑問題基礎(chǔ)上增加“同時(shí)取送”、“時(shí)間窗”與“碳費(fèi)”三個(gè)約束條件，發(fā)展為帶碳費(fèi)約束的有軟時(shí)間窗同時(shí)取送車輛路徑問題.建立了相應(yīng)的數(shù)學(xué)模型，設(shè)計(jì)了以or-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ì)效益和社會效益. 關(guān)鍵詞 車輛路徑問題；同時(shí)取送貨；軟時(shí)窗；碳費(fèi)；禁忌搜索 中圖分類號 tp391 文獻(xiàn)標(biāo)識碼 a 文章編號 1000-2537（2015）03-0069-005 在物流配

2、送活動中，同時(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ī)劃，國外研究較多

3、，最近的如文獻(xiàn)15，而國內(nèi)研究較少，但也有個(gè)別研究成果，如文獻(xiàn)68. 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ā)，訪問客戶.客戶位置

4、已知、車輛對客戶的送貨量和取貨量都已知、客戶所希望的服務(wù)時(shí)間窗口已知；車輛沿途一邊送貨一邊取貨，完成任務(wù)后，各車輛把取回的貨物送回配送中心；根據(jù)車輛在運(yùn)輸中產(chǎn)生的碳排放量對其征收一定的碳費(fèi)，以促使承運(yùn)人減少配送活動中的碳排放.車輛在訪問各客戶時(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í)取送貨

5、車輛路徑問題，采用xpress-mp軟件對案例的數(shù)學(xué)模型進(jìn)行求解.其他的文獻(xiàn)，如1113，在研究同時(shí)取送貨問題時(shí)，都沒有涉及碳費(fèi).對spdvrpstwcef研究成果的應(yīng)用，將極大地提高物流效率和效益，并將促進(jìn)物流運(yùn)輸配送優(yōu)化信息技術(shù)產(chǎn)品開發(fā)和應(yīng)用，促進(jìn)我國低碳物流和整個(gè)社會低碳經(jīng)濟(jì)的發(fā)展. spdvrpstwcef可以描述為：有1個(gè)車場（編號為0），擁有容量為q的車輛若干輛，負(fù)責(zé)對n個(gè)客戶（編號為1，2，n）進(jìn)行同時(shí)取送貨物工作，客戶i的貨物需求為di，且diq，表示從客戶i取回的貨物量為pi （目的地為發(fā)車場），且piq，每個(gè)客戶只能由一輛車服務(wù)一次，車輛早于或遲于客戶規(guī)定的服務(wù)時(shí)間窗口服務(wù)

6、，均須支付一定罰金，車輛須根據(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表示客戶單

7、位距離配送成本，客戶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í)的載重量

8、；式（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).本文使用or14提出or-opt方法，該方

9、法是將一段路徑（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，lin15等人從大量計(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)行說明，其中帶下劃線者為

10、所挑選的頂點(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 解的評價(jià) spdvrp

11、stwcef類型的車輛調(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=1t（r）+et（r）+pe（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（

12、r）為在線路r上超出車輛行駛距離的部分；而p是懲罰系數(shù).若一個(gè)解是可行的，則所有線路上的e（r）都等于零.p0.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，

13、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），配送中心有若干輛載重

14、量均為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ù)=202.630.16=8.4

15、16（元）. 本算法對文獻(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，配送線路圖

16、如圖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é)省了

17、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)行評價(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 beh

18、nam f， mohsen r， tupan p， et al. the implications of carbon pricing in australia： an industrial logistics planning case studyj.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 britis

19、h columbiaj.trans geography， 2011， 19（6）：1474-1481. 3 georgina s hannah b， laura m， et al. externalities and economic policies in road transportj.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.

20、the private and social cost efficiency of port hinterland container distribution through a regional logistics systemj. 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 lo

21、gist， 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 dant