王艷朋 臺玉紅

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

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

一、引言

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

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

二、問題描述

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

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

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

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

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

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

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

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

（二）碳排放成本計算

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

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

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

空載時單位距離碳排放量為

三、模型

（一）模型假設(shè)

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

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

2. 貨物流向為單向，即純送貨。

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

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

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

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

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

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

（二）定義模型中的變量

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

N為客戶編號集合，N=[1，2，…，n]。

dij為客戶i到客戶j的實際距離。

B為配送車輛的啟動成本。

C1為車輛單位里程運行成本。

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

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

[ai，bi]為客戶i要求的貨物到達時間窗。

Ti為配送車輛到達客戶i的時間點。

PTi 為未能按時到達客戶i的懲罰成本。

Di為客戶下訂單的時間。

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

0， 否則

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

0， 否則

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

0， 否則

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

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

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

（一）編碼的方式

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

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

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

（二）初始解生成

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

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

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

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

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

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

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

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

（四）選擇候選解

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

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

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

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

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

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

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

五、算例仿真

（一）背景介紹

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

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

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

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

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

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

參考文獻：

[1]周葉，王道平，趙耀.中國省域物流作業(yè)的CO2排放量測評及低碳化對策研究[J].中國人口、資源與環(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é)院）