考慮不確定因素的低碳配送優(yōu)化研究

王艷朋 臺(tái)玉紅

摘要：當(dāng)配送車輛遇到道路堵塞、惡劣天氣、限行、道路質(zhì)量差等不確定因素時(shí)，不僅行駛車速會(huì)受到影響，甚至可能會(huì)導(dǎo)致配送服務(wù)水平下降。即使在配送過(guò)程中有些路段是最短距離，當(dāng)遇到這些不確定的因素時(shí)，路徑優(yōu)化的結(jié)果將會(huì)發(fā)生變化。文章試將受不確定因素影響路段的實(shí)際距離轉(zhuǎn)化為理想距離，在其路徑優(yōu)化的過(guò)程中將碳的排放量轉(zhuǎn)換為成本，最終以成本最低為目標(biāo)函數(shù)建立數(shù)學(xué)模型，討論了基于改進(jìn)禁忌搜索算法的配送路徑優(yōu)化問(wèn)題的設(shè)計(jì)和實(shí)現(xiàn)。優(yōu)化對(duì)比結(jié)果表明，考慮不確定因素的配送路徑優(yōu)化比不考慮不確定因素的優(yōu)化結(jié)果更貼近實(shí)際。

關(guān)鍵詞：物流工程；低碳配送；禁忌搜索；電子商務(wù)；路徑優(yōu)化

一、引言

傳統(tǒng)的物流路徑優(yōu)化研究一般假設(shè)所有的信息（包括路況信息、車輛信息、顧客信息）都是確定的，這類車輛路徑問(wèn)題被稱為確定型VRP。但是，在配送過(guò)程中，難免會(huì)出現(xiàn)道路堵塞、惡劣天氣、限行、道路質(zhì)量差等不確定因素，這些不確定因素隨著時(shí)間的推移出現(xiàn)，需要適時(shí)改變車輛的運(yùn)行路線，對(duì)已安排好的車輛路徑進(jìn)行及時(shí)調(diào)整。此時(shí)需要研究一套考慮不確定信息車輛路徑問(wèn)題（Uncertain Information Vehicle Routing Problem，UIVRP）的理論和方法。并且，隨著全球氣候變暖，溫室氣體（主要是CO2）的減排問(wèn)題受到各國(guó)的密切關(guān)注，低碳經(jīng)濟(jì)、綠色物流逐漸成為國(guó)內(nèi)外研究的熱點(diǎn)。隨著供應(yīng)鏈全球化發(fā)展，供應(yīng)鏈中各物流節(jié)點(diǎn)距離不斷增加，車輛在運(yùn)輸配送過(guò)程中所帶來(lái)的碳污染等環(huán)境問(wèn)題逐漸顯現(xiàn)，因此把減少“碳排放”的理念融入到物流網(wǎng)絡(luò)設(shè)計(jì)當(dāng)中，構(gòu)建一個(gè)碳排放量最低的綠色物流網(wǎng)絡(luò)具有廣泛的現(xiàn)實(shí)意義。

已有學(xué)者提出了一些模型來(lái)研究這些問(wèn)題，其中通過(guò)運(yùn)輸距離的優(yōu)化間接達(dá)到減排目的的研究較多，而直接計(jì)算碳排放量并將其整合進(jìn)目標(biāo)函數(shù)的研究較少。國(guó)內(nèi)對(duì)VRP最先進(jìn)行系統(tǒng)性研究的是郭耀煌教授，他及其學(xué)生對(duì)多車場(chǎng)、多車型等類型的問(wèn)題進(jìn)行了較多的研究，并且先后承擔(dān)了多項(xiàng)基金項(xiàng)目的研究，出版了國(guó)內(nèi)車輛路徑問(wèn)題研究領(lǐng)域的第一部專著——《車輛優(yōu)化調(diào)度》，將sweep算法和節(jié)約算法結(jié)合起來(lái)使用，從而提出了一種多車場(chǎng)轉(zhuǎn)化為單車場(chǎng)的處理方法。國(guó)外Miguel Figliozzi文獻(xiàn)中以碳排放量最小為第一目標(biāo)函數(shù)和以燃油量為第二目標(biāo)函數(shù)提出了一種以碳排放量為目標(biāo)函數(shù)的車輛路徑問(wèn)題（EVRP），用啟發(fā)式算法對(duì)其進(jìn)行了求解，結(jié)論顯示通過(guò)優(yōu)化可以明顯地降低車輛運(yùn)行中的碳排放量，在擁堵的地區(qū)，可以通過(guò)增加少許的運(yùn)作成本來(lái)大幅降低溫室氣體的排放。Kim. N.S （2009）在多式聯(lián)運(yùn)網(wǎng)絡(luò)中探討了貨物運(yùn)輸成本與CO2排放量之間的關(guān)系，研究表明CO2排放量受運(yùn)輸系統(tǒng)載貨量的影響，通過(guò)優(yōu)化多式聯(lián)運(yùn)的組合可以降低CO2的排放量。Palmer在零售業(yè)背景下建立了一套以降低碳排放為目的的車輛路徑模型，模型具有優(yōu)化配送時(shí)間和將低碳排放量的功能。

二、問(wèn)題描述

當(dāng)配送車輛遇到道路堵塞、惡劣天氣、限行、道路質(zhì)量差等不確定因素時(shí)，不僅行駛車速會(huì)受到影響，甚至可能會(huì)導(dǎo)致配送服務(wù)水平下降。即使在配送過(guò)程中有些路段是最短距離，當(dāng)遇到這些不確定的因素時(shí)，路徑優(yōu)化的結(jié)果將會(huì)發(fā)生變化?？紤]到現(xiàn)實(shí)生活中配送路徑十分復(fù)雜，為確保模型的逼真性，需對(duì)現(xiàn)實(shí)問(wèn)題進(jìn)行必要的抽象和簡(jiǎn)化。

首先，在配送過(guò)程中，載貨量的多少不可避免地會(huì)對(duì)碳排放造成影響，若將載貨量考慮到模型里，模型規(guī)模將會(huì)很大。為降低建模難度的同時(shí)又不影響模型的真實(shí)性，本文在研究配送優(yōu)化時(shí)暫不考慮載貨量對(duì)碳排放的影響。

其次，為體現(xiàn)當(dāng)前各大物流公司的戰(zhàn)略目標(biāo)，即滿足客戶滿意度最大化的原則，對(duì)模型中車輛出現(xiàn)延遲配送的確定無(wú)窮大懲罰值，對(duì)車輛提前到達(dá)客戶處的確定懲罰值。

再次，為提高配送服務(wù)質(zhì)量和客戶滿意度，本文在建模時(shí)，按客戶對(duì)收貨時(shí)間的要求制定時(shí)間窗建模。

最后，考慮到車速變化對(duì)碳排放的影響較大，故模型假定以經(jīng)濟(jì)車速配送；為使建模更加逼真，由于是小范圍內(nèi)配送故暫不考慮天氣等不確定因素的影響，將每一條實(shí)際路徑賦予一個(gè)交通條件和道路條件系數(shù)來(lái)轉(zhuǎn)化為理想路徑，在此基礎(chǔ)上優(yōu)化路徑。

（一）實(shí)際距離轉(zhuǎn)化為理想距離

考慮到不確定因素對(duì)配送的影響，分別引入道路條件（hij）、交通條件（rij）、和天氣（wij=0）等影響因素定量討論其對(duì)城市交通運(yùn)行狀況的影響程度，計(jì)算公式為

其中，dij為客戶i和j之間的實(shí)際距離；d*ij為客戶i和j之間的理想距離。

（二）碳排放成本計(jì)算

在配送過(guò)程中的碳排放量，不僅與運(yùn)輸距離有關(guān)，還與載貨量等因素相關(guān)。本文收集相關(guān)數(shù)據(jù)進(jìn)行回歸分析，得出碳排放量是依賴于配送距離和載貨量的二元一次函數(shù)，即

其中，d是車輛行駛距離，Q0是車重，x是載貨量，α、β、b是一常數(shù)。

設(shè)車輛的最大載貨量為Q，滿載時(shí)單位距離排放量為

空載時(shí)單位距離碳排放量為

三、模型

（一）模型假設(shè)

設(shè)某城市有一個(gè)大型配送中心，隨機(jī)給這個(gè)城市里的n個(gè)客戶進(jìn)行配送。

1. 共有型號(hào)統(tǒng)一的M輛配送車輛。

2. 貨物流向?yàn)閱蜗?，即純送貨?/p>

3. 每個(gè)客戶只能由一輛車進(jìn)行配送服務(wù)。

4. 每輛車都從配送中心出發(fā)，然后又回到配送中心。

5. 每個(gè)客戶都有屬于自己的一個(gè)服務(wù)時(shí)間窗，服務(wù)必須在此時(shí)間范圍內(nèi)進(jìn)行。

6. 顧客總的需求量不能大于車輛總的載重量。

7. 每條線路上的車輛載重量之和不能超過(guò)車的載重量。

8. 假設(shè)公式（1）中城市配送中的交通現(xiàn)狀中道路條件（hij）、交通條件（rij）和天氣（wij）對(duì)交通運(yùn)行狀況的影響程度的取值范圍可參考。

（二）定義模型中的變量

M為配送車輛編號(hào)集合，M=[l，2，3，…，m]。

N為客戶編號(hào)集合，N=[1，2，…，n]。

dij為客戶i到客戶j的實(shí)際距離。

B為配送車輛的啟動(dòng)成本。

C1為車輛單位里程運(yùn)行成本。

Cij為客戶i和j之間碳排放成本。

Pe 、Pl為懲罰系數(shù)，其取值為正數(shù)，一般認(rèn)為早到要比晚到所帶來(lái)的損失要少一些，即令pe

[ai，bi]為客戶i要求的貨物到達(dá)時(shí)間窗。

Ti為配送車輛到達(dá)客戶i的時(shí)間點(diǎn)。

PTi 為未能按時(shí)到達(dá)客戶i的懲罰成本。

Di為客戶下訂單的時(shí)間。

Xijk=1，如果配送車輛k從客戶i到客戶j

0， 否則

Zk=1，如果配送車輛k被使用

0， 否則

Yik=1，如果客戶i需求由車輛k滿足

0， 否則

（三）低碳配送的數(shù)學(xué)模型

四、改進(jìn)的禁忌搜索算法設(shè)計(jì)

首先，通過(guò)貪婪算法，以客戶的訂貨的時(shí)間和收貨的時(shí)間窗按成本最低的原則確定車輛配送的數(shù)量，同時(shí)生成禁忌搜索算法的初始解。其次，設(shè)計(jì)鄰域結(jié)構(gòu)并從中選出候選解集，設(shè)計(jì)出禁忌表和禁忌長(zhǎng)度。再次，設(shè)計(jì)出特赦準(zhǔn)則。最后，確定迭代步數(shù)終止算法并輸出結(jié)果。

（一）編碼的方式

本文以自然數(shù)編碼的方式編碼，方式如下。

假設(shè)需要調(diào)用的配送車輛數(shù)為k，可以將配送路徑編譯成一個(gè)自然數(shù)序列數(shù)組，即

該數(shù)組中ikj表示配送車輛k的配送任務(wù)，每條子路徑之間用0進(jìn)行分割，表示每臺(tái)配送車輛從配送中心出發(fā)完成配送任務(wù)后回到配送中心。每條子路徑之間客戶之間的位置是有序的，表示配送車輛對(duì)客戶提供服務(wù)的順序。

（二）初始解生成

本文求初始解的具體步驟的如下。

步驟一，根據(jù)公式（1）得出客戶之間路徑的理想距離，然后計(jì)算出客戶間所需要的行駛時(shí)間，且令r=1。

步驟二，派出第一輛車配送，確定第一條帶有第一個(gè)客戶ir1的新路徑，其中客戶ir1需滿足與配送中心的理想距離最小，且有最遲服務(wù)時(shí)間。

步驟三，若能找到與客戶irn（n=2，3，…）之間理想距離最小的，且滿足時(shí)間窗中最遲服務(wù)時(shí)間的客戶作為irn+1，否則轉(zhuǎn)至步驟一。

步驟四，派出另外一輛車，開始一條新路徑，令r=r+l，轉(zhuǎn)至步驟二。

步驟五，若車輛配送到所有客戶，得到一個(gè)初始解。

（三）鄰域結(jié)構(gòu)設(shè)計(jì)

本文擬用路徑內(nèi)交換和路徑間變換的鄰域設(shè)計(jì)策略。路徑內(nèi)的交換主要是利用2-opt的方法在同一路徑中隨機(jī)找到兩個(gè)點(diǎn)進(jìn)行交換；路徑間的變換包括路徑間的交換與插入。

（四）選擇候選解

本文在選擇最佳候選解時(shí)利用鄰域結(jié)構(gòu)設(shè)計(jì)策略，使每個(gè)當(dāng)前解產(chǎn)生N個(gè)候選解，讓這些候選解對(duì)應(yīng)的適應(yīng)度從小到大排序，從中選出排在前面的n（n

（五）禁忌表設(shè)計(jì)

本文在設(shè)計(jì)禁忌表時(shí)選用從上一個(gè)當(dāng)前解變?yōu)楝F(xiàn)在當(dāng)前解時(shí)用到的兩兩交換的對(duì)象（客戶點(diǎn)）作為禁忌的對(duì)象，為了記錄這些禁忌對(duì)象的任期在每一次迭代中的變化，本文在編寫程序時(shí)設(shè)計(jì)了一個(gè)[26*26]的矩陣專門記錄這些禁忌對(duì)象任期的變化。本文選用固定型的禁忌長(zhǎng)度，用客戶點(diǎn)數(shù)n的作為禁忌的長(zhǎng)度。

（六）特赦準(zhǔn)則設(shè)計(jì)

本文選用基于適應(yīng)度的原則進(jìn)行特赦準(zhǔn)則設(shè)計(jì)，如果在迭代的過(guò)程中某個(gè)候選解的適應(yīng)度值優(yōu)于歷史最優(yōu)值，那么無(wú)論這個(gè)候選解是否處于被禁忌的狀態(tài)，都要被接受，成為下一次迭代的初始解并取代當(dāng)前的歷史最優(yōu)解成為新的“best so far”。

（七）終止準(zhǔn)則設(shè)計(jì)

本文用不同的迭代次數(shù)進(jìn)行實(shí)驗(yàn)，根據(jù)實(shí)驗(yàn)的結(jié)果確定合適的最大迭代步數(shù)終止算法。

五、算例仿真

（一）背景介紹

本文以某電子商務(wù)企業(yè)在某城市有一大型配送中心為例，配送車輛為10，設(shè)每臺(tái)車的啟動(dòng)成本為300，經(jīng)濟(jì)車速下每臺(tái)車每公里的運(yùn)輸成本為2，碳排放成本為0.5，等待時(shí)間的懲罰系數(shù)pe=10、pl=inf，若某一天客戶為25，且rij和hij可由rand命令隨機(jī)生成。因同城配送，天氣狀況基本相同，故可取wij=0。根據(jù)某電子商務(wù)企業(yè)隨機(jī)對(duì)客戶信息提取整理需要配送客戶的具體信息見(jiàn)表1。

（二）考慮不確定因素的路徑優(yōu)化

對(duì)于考慮不確定因素的路徑優(yōu)化，首先利用公式

為保證算法更具有穩(wěn)定性和求得更為滿意精確解，運(yùn)算10次并將與未考慮不確定因素的優(yōu)化結(jié)果進(jìn)行對(duì)比，見(jiàn)表2。

分析可知，雖然兩種路徑優(yōu)化方式結(jié)果的實(shí)際距離差不多，但考慮不確定因素的各種配送成本及總成本明顯比不考慮不確定因素的路徑優(yōu)化小。因此，物流企業(yè)在配送優(yōu)化時(shí)，需考慮不確定因素各種條件，首先將每條路徑的實(shí)際距離轉(zhuǎn)化為理想距離，在此基礎(chǔ)上再對(duì)路徑進(jìn)行優(yōu)化可以有效降低配送成本和碳排放量。所以，為提高配送服務(wù)滿意度及達(dá)到節(jié)能減排的目的，在路徑優(yōu)化過(guò)程中單純優(yōu)化實(shí)際路徑是不夠完善的。

本文在前人研究成果的基礎(chǔ)上，探討了考慮不確定因素前提下，配送路徑優(yōu)化問(wèn)題，經(jīng)過(guò)本文的研究，構(gòu)建相關(guān)模型并對(duì)其進(jìn)行求解，得到了預(yù)期的結(jié)果。

參考文獻(xiàn)：

[1]周葉，王道平，趙耀.中國(guó)省域物流作業(yè)的CO2排放量測(cè)評(píng)及低碳化對(duì)策研究[J].中國(guó)人口、資源與環(huán)境，2011（09）.

[2]SAMIR ELHEDHLI， RYAN MERRICK.Green supply chain network design to reduce carbon emissions[J].Transportation Research Part D，2012（05）.

[3]郭耀煌，李軍.車輛優(yōu)化調(diào)度[M].成都：成都科技大學(xué)出版社，1994.

[4]Kim N.S.，Janic M.，Wee B.Trade-Off Between Carbon Dioxide Emissions and Logistics Costs Based on Multiobjective Optimization[J].Transportation Research Record，2009.

[5]Palmer.The Development of an Integrated Routing and Carbon Dioxide Emissions Model for Good Vehicles[J].PHD thesis： Cranfield University，2007.

[6]李柞泳，鐘俊，彭蔡紅.基于蟻群算法的兩地之間的最佳路徑選擇[J].系統(tǒng)工程，2004（07）.

[7]Yiyong Xiao，Qiuhong Zhao Ikou Kaku，et al.Development of a fuel consumption optimization model for the capacitated vehicle routing problem[J].Computers & Operations Research，2012（07）.

[8]陳京榮.交通網(wǎng)絡(luò)路徑選擇及應(yīng)用[D].蘭州交通大學(xué)，2009.

（作者單位：上海理工大學(xué)管理學(xué)院）