代楚楚，徐 菱

（西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院，四川 成都 610031）

0 引言

快遞業(yè)作為城市內(nèi)物流配送業(yè)的重要組成部分，其營業(yè)額年均增速高達(dá) 25%～30%。據(jù)測算，我國快遞市場規(guī)模與 GDP 的增長關(guān)系密切，GDP每增長 1%，快遞市場規(guī)模將增長 2.93%[1]。特別是在電子商務(wù)的刺激下，快遞業(yè)規(guī)模將進(jìn)一步擴(kuò)大。根據(jù)中國電子商務(wù)研究中心的監(jiān)測數(shù)據(jù)顯示：僅2013 年上半年，中國網(wǎng)絡(luò)購物用戶規(guī)模達(dá)到 2.77 億人，占中國網(wǎng)民的 40.9%，網(wǎng)絡(luò)零售市場交易規(guī)模達(dá)到7 542 億元[2]，每天由電子商務(wù)產(chǎn)生的快件已經(jīng)超過500 萬件。如此巨大數(shù)額的快件量配送勢必導(dǎo)致碳排放量的大幅提高，因而對快遞企業(yè)配送路徑選擇進(jìn)行節(jié)能減排優(yōu)化將對抑制溫室氣體排放具有較大促進(jìn)作用。

在傳統(tǒng)的車輛路徑問題 ( Vehicle Routing Problem，VRP ) 中，通常將車輛數(shù)最少和路徑最短作為模型的目標(biāo)函數(shù)，既有研究成果較少將降低碳排放作為一個目標(biāo)在 VRP 模型中進(jìn)行考慮。Figliozzi在基于有時間窗約束的車輛路徑問題 ( Vehicle Routing Problem with Time Windows，VRPTW ) 中構(gòu)建考慮碳排放的車輛路徑模型 ( Vehicle Routing Problem for Emission Minimization，EVRP )，首次將降低碳排放和減少車輛能耗作為 VRP 問題的目標(biāo)，第一次將客戶服務(wù)開始時間作為 1 個決策變量考慮進(jìn)有時間窗約束的 VRP 問題中，并且考慮不同擁堵條件對車輛碳排放的影響，最后設(shè)計路徑構(gòu)造算法 ( Iterated Route Construction and Improvement，IRCI ) 對模型進(jìn)行求解[3-4]。Saberi 等[5]認(rèn)為客戶點(diǎn)連續(xù)均勻分布，存在密度函數(shù)，并且任意 2 個客戶點(diǎn)間的距離與分布密度有關(guān)，因而將速度處理成隨旅行時間連續(xù)變化的函數(shù)，應(yīng)用連續(xù)近似分析模型對問題進(jìn)行求解。楊子岳[6]研究考慮碳排放的 B2C電子商務(wù)企業(yè)配送路徑優(yōu)化，通過道路條件、天氣狀況等參數(shù)將電商實際配送路徑轉(zhuǎn)化為考慮碳排放的虛擬路徑，以此處理速度對車輛碳排放的影響，并且通過禁忌搜索算法對模型進(jìn)行求解。

由于車輛在行駛過程中的碳排放與行駛距離、行駛速度 2 個變量有關(guān)，如果僅在傳統(tǒng)的靜態(tài)車輛路徑問題 ( Static Vehicle Routing Problem，SVRP ) 目標(biāo)函數(shù)中加入碳排放最少這一目標(biāo)并不符合實際。為此，參考 Figliozzi 所建模型，在考慮旅行速度時間依賴性的同時將車輛數(shù)最少、旅行時間最短及碳排放最少作為模型的 3 個目標(biāo)函數(shù)，建立基于時間依賴車輛路徑模型 ( Time Dependent Vehicle Routing Problem，TDVRP ) 模型的 EVRP 模型，并且設(shè)計多種群遺傳算法求解模型，為快遞企業(yè)選擇低碳配送路徑提供理論支撐。

1 快遞企業(yè)配送EVRP模型建立

1.1 問題描述

快遞企業(yè)配送 EVRP 模型基于 TDVRP 模型構(gòu)建，具有旅行時間嚴(yán)格依賴于出發(fā)時間的特點(diǎn)。TDVRP 模型最早由 Malandraki 和 Daskin 在 1992 年提出，問題描述為有n個客戶點(diǎn)，每個客戶點(diǎn)的需求量及位置已知，至多用K輛車從配送中心出發(fā)去服務(wù)這批客戶點(diǎn)，要求車輛在規(guī)定時間內(nèi)完成任務(wù)并返回配送中心，每輛車載質(zhì)量一定，要求安排車輛的行駛線路使總旅行時間最短。其中，每個客戶點(diǎn)的服務(wù)時間窗已知，任意 2 個客戶點(diǎn)間的旅行時間與距離、出發(fā)時間有關(guān)[7]。

考慮到快遞企業(yè)的特殊性，EVRP 模型所描述的問題還需要滿足以下條件：①配送與攬收獨(dú)立進(jìn)行。在快遞企業(yè) 1 臺車服務(wù) 1 個網(wǎng)點(diǎn)的情況下，為避免大量的資源浪費(fèi)和成本劣勢，將配送和攬收同步進(jìn)行，但國內(nèi)的快遞企業(yè)可以達(dá)到上述規(guī)模的很少，考慮操作的方便性，簡化操作流程，節(jié)省時間，默認(rèn)快遞企業(yè)的配送和攬收獨(dú)立進(jìn)行。②每條線路上的客戶需求不超過車輛的最大載質(zhì)量。③每條配送線的距離不超過車輛的 1 次行駛最大距離。④每個客戶點(diǎn)有且只有 1 輛車服務(wù)。

1.2 模型建立

TDVRP 模型描述與 VRP 模型基本相同，只是在時間段的劃分及車輛出發(fā)時間的定義上有所不同。TDVRP 模型描述如下。

在 1 個無向圖G= (V，A) 上，V= {v0，v1，…，vn} 為頂點(diǎn)集合，A= {(vi，vj) :i≠j∧i，j∈V} 為弧集合。頂點(diǎn)v0為配送中心，停放著K輛型號相同、載質(zhì)量為Q的車；頂點(diǎn)集合C= {v1，…，vn} 為需要服務(wù)的客戶集，V中每個頂點(diǎn)都有1 個相應(yīng)的非負(fù)需求量qi≤Q與之對應(yīng)，服務(wù)時間gi≥0。其中，g0= 0，q0= 0。每個頂點(diǎn)允許服務(wù)的時間窗為 [ei，li]；車輛到達(dá)客戶i(i∈C) 的時間定義為ai，服務(wù)開始時間定義為si，離開時間定義為bi；對于任意弧 (vi，vj)，對稱的距離矩陣dij≥0，旅行時間tij(bi)≥0。假設(shè)每輛車的固定成本為C，系統(tǒng)規(guī)劃時間被分成M段，記為T=T1，T2，…，TM。

在 TDVRP 模型中，旅行時間為出發(fā)時間函數(shù)，為方便區(qū)分，用fij(t) 表示車輛在時刻t出發(fā)，從節(jié)點(diǎn)i經(jīng)過 (i，j) 到達(dá)j的旅行時間，建立模型如下。

其中：⑵式為每個客戶點(diǎn)有且只有 1 輛車到達(dá)和服務(wù)；⑶式為離開每個客戶點(diǎn)的車輛有且只有 1輛；⑷式為每輛車均從車場出發(fā)；⑸式為抵達(dá)客戶的車同時也是離開客戶的車；⑹式為每輛車最后回到車場；⑺式為車容量約束；⑻、⑼式為時間窗約束，具體含義為假如 1 輛車從客戶i到客戶j，那么其在客戶j開始服務(wù)的時間不能早于到達(dá)時間si+ti+fij(si+ti)，同時在j的服務(wù)時間窗[aj，bj] 內(nèi)；⑽式為硬時間窗約束，表示車輛在任意客戶點(diǎn)服務(wù)完成時間必須在該客戶點(diǎn)的服務(wù)時間窗內(nèi)；⑾式為車輛數(shù)約束。

1.3 碳排放最小化模型

英國交通運(yùn)輸研究實驗室研究表明，車輛在行駛過程中的碳排放與行駛速度、行駛距離 2 個因素有關(guān)，并且存在以下關(guān)系[4]。

其中，英國交通運(yùn)輸研究實驗室經(jīng)過大量實驗?zāi)M出的 3 者關(guān)系參數(shù) { ?0，?1，?2，?3} ={ 1 576，-17.6，0.001 17，36 067 }。在 TDVRP 模型中，每個時間段都有相應(yīng)的即時速度sm≥0，對于任意i，j，均有發(fā)生在時間段T m，表示離開客戶i的速度；發(fā)生在時間段表示到達(dá)客戶j的速度，1≤m≤m+p≤M。為相應(yīng)的距離與時間，滿足以下條件。

其中：⒀式為客戶i，j之間的旅行時間為分段之和；⒁式為客戶i，j之間的距離為分段之和；⒂式為車輛在某段時間的行駛距離為對應(yīng)時間段的速度與時間的乘積；⒃式為時間窗約束，表示將時間段劃分，則每個客戶點(diǎn)的到達(dá)時間和離開時間必在其所屬時間段范圍內(nèi)。

任意客戶i，j之間的碳排放模型計算公式為

從⒅式可知，任意兩點(diǎn)間的碳排放為車輛在不同時間段行駛時碳排放的和。

為對快遞企業(yè)碳排放進(jìn)行預(yù)防監(jiān)督，采用碳稅換算將快遞企業(yè)的碳排放成本化。假設(shè)碳稅稅率為w，則碳排放成本模型計算公式為

1.4 模型求解

快遞企業(yè)配送 EVRP 模型與一般 VRP 模型的不同之處在于：①旅行時間的時間依賴性；②將降低碳排放成本作為目標(biāo)函數(shù)之一。通過調(diào)研可知，快遞企業(yè)通常將 1 次配送的持續(xù)時間作為衡量企業(yè) 1次配送作業(yè)完成的優(yōu)劣，考慮將配送車輛 1 次配送的旅行時間近似為快遞企業(yè) 1 次配送的可變成本。因此，模型目標(biāo)函數(shù)為旅行時間、車輛固定費(fèi)用和碳排放費(fèi)用之和。快遞企業(yè) EVRP 模型的目標(biāo)函數(shù)和約束條件如下。約束條件同⑵式至⑾式，這里不再贅述。

2 模型的求解

（1）染色體編碼設(shè)計。VRP 問題與旅行商問題 ( Travelling Salesman Problem，TSP ) 一樣，適合采用自然數(shù)編碼的方式來構(gòu)造染色體[8]。在編碼中，數(shù)字“0”為配送中心，數(shù)字 1，2，…，N為N個客戶點(diǎn)，形成的客戶點(diǎn)序列首尾均為 0，表示車輛從配送中心出發(fā)最后又返回配送中心，其余的“0”插入到客戶點(diǎn)序列中，形成諸如 0，1，2，0，3，4，5，0，6，0，7，8，9，0 的序列，表示 4 輛車遍歷 9 個客戶點(diǎn)形成的 4 條路徑：0-1-2-0，0-3-4-5-0，0-6-0 及 0-7-8-9-0。

（2）生成初始解。采用節(jié)約法、貪心算法和隨機(jī)產(chǎn)生初始解的方式生成 3 個初始解，以初始化3 個種群。其中，節(jié)約法的流程描述為首先將n個客戶點(diǎn)初始成n條獨(dú)立的路線，每條路線上的 1 輛車服務(wù)完當(dāng)前客戶即返回配送中心，形成路徑 ( 0，i，0 )；在不違反車容量限制的條件下合并 2 條獨(dú)立路線，合并方法為“首尾相連”，合并條件為路徑節(jié)約值最大，這樣每次合并即可減少 1 輛車。例如，路線 1 的最后 1 個客戶為i，路線 2 的第 1 個客戶為j，則合并路線 1 和路線 2 的方式為將弧 (i，0 ) 和弧 ( 0，j)移除，同時添加弧 (i，j)，不斷重復(fù)上述步驟直到某輛車的車容量不再滿足為止[8]。某 2 條路線的路徑節(jié)約值計算公式為

對貪心算法的流程進(jìn)行描述：從配送中心 0 開始，從未服務(wù)的客戶中選擇 1 群不違反車容量約束的客戶，再在其中挑選 1 個旅行時間最小的添加到已有路線中，同時不能違反該客戶點(diǎn)的時間窗；如果從未服務(wù)的客戶中找不到滿足車容量約束的客戶，那么該輛車返回配送中心，即 1 條新路徑生成。重復(fù)上述步驟，直到所有客戶均有車輛經(jīng)過。

（3）種群初始化。每個種群由 1 個初始解通過隨機(jī)互換算子得到，隨機(jī)互換算子隨機(jī)互換路徑中2 個客戶點(diǎn)的位置，每個子種群分別由 1 個初始解通過隨機(jī)互換產(chǎn)生。

（4）適應(yīng)度評價。評價前應(yīng)先形成可評價的染色體，具體操作為在隨機(jī)產(chǎn)生的客戶點(diǎn)序列中插入車輛“0”，插入準(zhǔn)則為車容量約束，直至找出不滿足容量約束條件的客戶在其前插入“0”，以此形成 1 個可評價解。

（5）選擇算子。將所有的個體進(jìn)行交叉變異，并且按照其適應(yīng)度值大小進(jìn)行排序，取一定數(shù)量的優(yōu)秀子代進(jìn)入新群體。

（6）交叉算子。個體的交叉策略采用 OX 順序交叉，具體操作方法：隨機(jī)在父代個體中產(chǎn)生 2 個交叉點(diǎn) ( 交叉點(diǎn)相同 )，中間部分為交叉區(qū)域，把 1個父代染色體的交叉區(qū)域部分放置于另 1 父代染色體的交叉區(qū)域中，后者檢查交叉區(qū)域后的部分依次刪除與交叉區(qū)域中相同的數(shù)字，得到 1 條子代染色體，另 1 父代染色體進(jìn)行同樣操作得到另 1 條子代染色體。

（7）變異算子。采用隨機(jī)互換、隨機(jī)插入和隨機(jī)逆轉(zhuǎn) 3 個變異算子，分別用于 3 個種群的變異操作。隨機(jī)互換算子如圖 1 所示，隨機(jī)插入示意圖如圖 2 所示，隨機(jī)逆轉(zhuǎn)算子示意圖如圖 3 所示。

圖2 隨機(jī)插入示意圖

圖3 逆轉(zhuǎn)算子示意圖

（8）移民算子。在多種群遺傳算法(Multiple Population Generation Algorithm，MPGA)中，移民算子將各種群在遺傳迭代中產(chǎn)生的最優(yōu)個體間隔固定代數(shù)遷移至另外的種群中，從而實現(xiàn)彼此的基因交換。

（9）產(chǎn)生精華種群。在負(fù)責(zé)遺傳操作群進(jìn)化過程中，每隔一定的代數(shù)將最優(yōu)個體存儲到精華種群中，該操作通過人工選擇算子實現(xiàn)。

（10）算法終止條件。通過采用精華種群中的最優(yōu)個體最少保持代數(shù)作為算法的停止依據(jù)[9]。

3 算例分析

3.1 算例描述

以成都市某快遞企業(yè)為例，其有 1 個大型配送中心，位于成都市邊緣地區(qū)，設(shè)其坐標(biāo)為 [5，10]。企業(yè)在成都市共有 50 個網(wǎng)點(diǎn)，配送車輛每天在配送中心和網(wǎng)點(diǎn)之間進(jìn)行 5 次配送作業(yè)，配送時間段分別為 ( 6 : 30，9 : 30 )、( 9 : 30，12 : 30 )、( 12 : 30，15 : 30 )、( 15 : 30，18 : 30 ) 及 ( 18 : 30，21 : 30 )，其中第1次配送持續(xù)時間段 ( 6 : 30，9 : 30 ) 和第 4 次配送持續(xù)時間段 ( 15 : 30，18 : 30 ) 與城市路網(wǎng)的早高峰和晚高峰時段有重疊。由于所建模型的旅行速度考慮到城市路網(wǎng)交通擁堵影響，以每天第 1 次配送為例進(jìn)行算例分析。在調(diào)研中發(fā)現(xiàn)，快遞企業(yè)各網(wǎng)點(diǎn)的服務(wù)時間窗均為 1 次配送的持續(xù)時間，配送中心與客戶網(wǎng)點(diǎn)的工作時間均為 1 次配送持續(xù)時間段( 6 : 30，9 : 30 )，配送車輛在每個客戶點(diǎn)的服務(wù)時間為 10 min。將配送車輛數(shù)的上限設(shè)為 50，即在最壞的情況下 1 個網(wǎng)點(diǎn)配備 1 輛車，配送車輛型號統(tǒng)一，1 輛車的 1 次投入成本為 1 000。碳排放成本采用碳稅制為 10 元。

（1）客戶坐標(biāo)。通過查閱資料，成都市轄區(qū)面積為 1 412 km2，將客戶坐標(biāo)限制在邊長為 40 的矩形中，通過隨機(jī)生成產(chǎn)生?？蛻糇鴺?biāo)信息如表 1所示。

（2）客戶需求。通過調(diào)研可知，該快遞企業(yè)在配送過程中，每輛車容量平均可以滿足 3～5 個客戶網(wǎng)點(diǎn)的需求。因此，每次等概率地從集合{ 10，12，15，20，25 } 中隨機(jī)選取 1 個數(shù)作為某個客戶點(diǎn)的需求量，并將配送車輛的容量上限設(shè)為50。各網(wǎng)點(diǎn)需求量如表 1 所示。

（3）服務(wù)時間。快遞企業(yè)的車輛在各網(wǎng)點(diǎn)不存在服務(wù)等待時間，故ai=si，車輛每次配送時間約為 10 min。將算例中客戶網(wǎng)點(diǎn)的服務(wù)時間定為 11 min，其中 1 min 表示配送車輛在起步和減速過程中浪費(fèi)的時間。

（4）時間窗限制。由于模型研究對象為快遞企業(yè)早高峰配送，因而各客戶的服務(wù)時間窗均為系統(tǒng)規(guī)劃的 3 h，即 ( 6 : 30，9 : 30 )。

（5）時間依賴旅行速度。以快遞企業(yè)早高峰配送為例，將早高峰 3 h 分為 6 : 30—7 : 30、7 : 30—8 : 30、8 : 30—9 : 30，為與城市路網(wǎng)的實際運(yùn)行相符合，將中間時段設(shè)為出行高峰期 ( 擁堵時段 )，兩端為非高峰期 ( 暢行時段 )。在城市路網(wǎng)中，通常將道路分成主干路、次干路和支路，不同路段上的實時速度不同，主要與道路的長度、車道數(shù)、通行能力等因素有關(guān)。為盡可能模擬實際路網(wǎng)，將客戶點(diǎn)間的距離按照長度進(jìn)行劃分，各路段上高峰期與非高峰期對應(yīng)的速度如表 2 所示。

（6）初始化種群。采用節(jié)約法、貪心算法及隨機(jī)生成初始解的方法生成 3 個初始解。其中，節(jié)約法與貪心算法生成的初始解如表 3 和表 4 所示。

（7）算法控制參數(shù)。種群內(nèi)個體數(shù)目為 30；交叉概率pc= 0.9；變異概率pm= 0.09；每隔 20 代進(jìn)行 1 次移民操作；精華種群中最優(yōu)解保持 50 代算法停止。

表1 客戶坐標(biāo)及需求量

表2 各路段上高峰期與非高峰期速度

表3 節(jié)約法生成初始解

表4 貪心算法生成初始解

3.2 計算結(jié)果分析

每次程序運(yùn)行 136 min。Matlab 運(yùn)行 5 次，5 次運(yùn)行的收斂性均較好。5 次運(yùn)行結(jié)果中有 2 次結(jié)果相同，舍去 1 組結(jié)果，保留 4 組運(yùn)行結(jié)果，該結(jié)果與 2 組構(gòu)造算法產(chǎn)生的局部最優(yōu)解進(jìn)行比較，最優(yōu)解比較表如表 5 所示。通過比較分析，選取最優(yōu)的 1 組作為算例最優(yōu)解，最優(yōu)解車輛成本為 18 000元，即需要 18 輛車，時間成本為 2 033.97 元，碳排放成本為 9 194.023 元，總成本為 23 963.59 元，最優(yōu)解相關(guān)指標(biāo)、最優(yōu)路徑規(guī)劃圖分別如表 6 和圖 4 所示，圖 4 中每種顏色的線條代表 1 輛車服務(wù)客戶點(diǎn)的旅行路徑，共有 18 種顏色，分別代表 18輛車。

表5 MPGA4 組運(yùn)行結(jié)果與 2 組局部最優(yōu)解比較表

表6 EVRP 模型最優(yōu)解相關(guān)指標(biāo)

圖4 EVRP 模型最優(yōu)解規(guī)劃圖

4 結(jié)束語

在研究 1 種新車輛路徑問題時，通過考慮碳排放的車輛路徑問題 ( EVRP )，構(gòu)建基于時間依賴車輛路徑問題模型 ( TDVRP )，將碳排放、車輛數(shù)和旅行時間最少共同作為模型的目標(biāo)函數(shù)，并且首次將該模型與快遞企業(yè)的配送特殊性相結(jié)合，應(yīng)用到快遞企業(yè)配送路徑選擇中。通過設(shè)計適合該模型的多種群遺傳算法求解模型，以某快遞企業(yè)在成都市的網(wǎng)點(diǎn)布局和早高峰配送數(shù)據(jù)為例進(jìn)行算例分析，結(jié)果表明 MPGA 用于求解 EVRP 問題具有良好的收斂性和時間特性，這對快遞企業(yè)低碳配送路徑選擇具有重要意義。

[1] 張洪斌. 我國快遞業(yè)現(xiàn)狀和發(fā)展趨勢預(yù)測[J]. 中國物流與采購，2006，8(9)：34-37

[2] 中國電子商務(wù)研究中心. 2013(上)中國電子商務(wù)市場數(shù)據(jù)監(jiān)測報告[M]. 杭州：中國電子商務(wù)研究中心，2013.

[3] FigliozziI M A. The Impacts of Congestion on Commercial Vehicle Tour Characteristics and Costs [J]. Forthcoming Transportation Research Part E：Logistics and Transportation，2009(46)：496-506.

[4] Miguel Figliozzi. Emissions Minimization Vehicle Routing Problem[J]. Transportation Research Board，2010(1)：10-14.

[5] Meead Saberi，I Omer Verbas. Continuous Approximation Model for the Vehicle Routing Problem for Emissions Minimization at the Strategic Level [J]. Journal of Transportation Engineering，2012(138)：1368-1376.

[6] 楊子岳. 低碳視角下B2C電子商務(wù)配送路徑優(yōu)化研究[D]. 成都：西南交通大學(xué)，2012.

[7] Malandraki C，Daskin M S. Time-dependent Vehicle-routing Problems-formulations，Properties and Heuristic Algorithms[J]. Transportation Science，1992，26(3)：185-200.

[8] 周 冬. 基于TDVRP和STDVRP模型的金融押運(yùn)車輛路徑問題研究[D]. 北京：清華大學(xué)，2010.

[9] 史 峰，王 輝，郁 磊，等. Matlab智能算法30個案例分析[M]. 北京：北京航空航天大學(xué)出版社，2011.