“雙成本”視閾下雙向物流車輛路徑選擇問題研究

劉 躍，付世敏

（重慶郵電大學，重慶 400065）

“雙成本”視閾下雙向物流車輛路徑選擇問題研究

劉 躍，付世敏

（重慶郵電大學，重慶 400065）

在運輸中汽車尾氣造成的環境污染越來越嚴重，在傳統路徑研究中由于正逆向物流分離，其路徑優化結果不能滿足低碳化社會的需要。在傳統路徑研究的基礎上，增加“同時取送”、“環境成本”約束條件，建立“雙成本”視閾下雙向物流車輛路徑選擇模型并設計相應的遺傳算法，通過案例證明模型和算法的有效性和可行性。結果分析表明，綜合考慮環境成本和運輸成本的車輛路徑問題在有效降低物流成本的同時，能實現綠色物流。

雙成本；同時取送貨；物流車輛；路徑選擇；運輸費用；CO2排放；遺傳算法

1 引言

物流被認為是獲取利潤的“第三源泉”。中國物流與采購聯合會發布的2017年1-5月社會物流總費用為4.6萬億元，運輸費用為2.4萬億元，占物流總費用的一半；而在交通運輸中產生的大量的CO2排放嚴重污染環境，企業在減少經濟成本的同時也要兼顧著社會責任，因而減少環境成本成為物流配送路徑選擇問題中的目標。

車輛路徑問題（VRP）是Dantzig和Ramser[1]在1959年提出的，之后的學者也進行了大量研究，產生了很多重要的研究成果，大多集中在單向物流方面。而在實際情形中，同時取送貨的顧客很常見，因此，研究同時取送貨車輛路徑問題（VRP-SDP）更加接近實際的配送管理。VRP-SDP的概念首次是由Min[2]在1989年提出的，研究了車輛數量限制和裝載能力限制情況下如何處理1個配送中心和22個客戶點之間圖書的配送和回收問題，采用先分組后排序的算法，把各個組群當作一個獨立的旅行商問題進行路徑求解；張建勇、李軍[3]設計了一種混合遺傳算法求解具有同時配送和回收需求的車輛路徑問題；劉晴[4]對隨機需求的同時取送貨車輛路徑問題進行了研究；王超，穆東[5]以一種主從式并行模擬退火算法代替傳統的串行模擬退火算法研究物流配送和廢舊產品回收的VRPSDP問題；一些學者認為[6]，擴展車輛路徑問題的目標，路徑安排不應該只考慮經濟成本，更應該考慮對社會和環境的影響，以減少碳排放量。Demir[7]等提出以減少環境污染為目標，綜合考慮經濟成本及社會環境成本的PRP模型；鐘聰兒[8]等在配送路徑優化中綜合考慮碳排放和運輸費用并以其費用最小為目標函數；侯躍[9]等提出碳交易環境下固定車輛數的多車型車輛配送路徑優化問題，考慮碳交易市場機制對運輸企業收益成本的影響；朱長征[10]等在經典的車輛路徑優化模型的基礎上考慮碳排量，建立了碳排量最小的車輛路徑優化模型；張立毅[11]等針對物流配送中碳排放的度量方法，以碳排放成本為目標函數，建立了低碳物流配送路徑優化模型；葛顯龍[12]等在分析現有文獻中多車型車輛路徑問題中車輛使用優先原則的基礎上，將車輛使用費用分為固定費用和油耗費用。以上文獻雖然探討了如何降低企業的經濟成本和環境成本，但大多只是假設配送中心具有同種車型，然而每種車型的裝載能力、碳排放能力等都不同，這與實際情況不相符；此外，以上文獻并沒有把“雙成本”和雙向物流綜合聯系起來。基于此，本文在雙向物流路徑選擇問題研究中，結合實際情況將不同車型考慮到CO2排放量的計算過程中，并結合運輸成本建立以總成本最小為目標的車輛路徑選擇問題，合理調配車輛、優化路線，不僅提高企業的經濟效益也避免了運輸車輛的空載和重復運輸等，減少了CO2排放量。

2 碳排放計算模型

根據不同的精確度要求和所采集的數據種類，二氧化碳排放量的計算可以選取不同的計算方法，參考文獻[13]有：

其中F為貨物運輸過程中的燃油消耗；G為地形坡度因子；D為車輛的行駛距離；L為載貨重量；a、b為燃油消耗參數（該參數隨車型的變化而變化，并忽略駕駛情況、交通路況的影響）。直接的二氧化碳排放量=燃油消耗量×燃油轉換系數，設燃油轉換系數為π，則二氧化碳排放量為:

由式（2）可知，二氧化碳排放量與燃油消耗成正比例關系；而燃油消耗與行駛距離成正比例關系，與裝載量成正線性相關。為模型求解方便，令地形坡度因子G為1，根據實際問題可以得出：

3 考慮運輸成本和環境成本的同時取送貨車輛路徑選擇模型

3.1 問題描述

假設一個配送中心有L輛K種不同類型的車輛服務于多個客戶，任務完成后最終返回配送中心，已知配送中心和每個顧客的位置，且顧客的需求量和回收量已知。要求合理安排車輛路線，使得運輸成本和環境成本之和最小，并滿足以下條件：（1）在顧客節點可以同時完成取貨和送貨任務，每個顧客的需求只能被一輛車服務且服務一次；（2）每一條路徑上車輛的裝載量不能超過車輛的最大載重量；（3）每一條路徑的長度不能超過車輛行駛的最大距離；（4）每種車型的車輛數固定，且具有不同的載重量和燃油消耗（與計算碳排放量有關）。

為了描述方便，定義以下使用的符號和決策變量：

（1）現有一個有向圖 G=(V,E)，其中 V=（0，1，2，…，n）有n+1個頂點，0表示配送中心，剩余的集合表示顧客點；E為弧集，則E＝｛(i,j)/i,j∈V，i≠j｝；

（2）yi為節點i的配送需求量，i∈V；

（3）zi為節點i的回收量，i∈V；

（4）Dij為節點i到節點j之間的距離；

（5）π表示燃油轉換系數；

（6）L為配送中心的汽車數量；

（7）K表示車型種數，mk為車型k的數量，滿足

（9）Qk為車型k的裝載能力，同種車型裝載能力相同；

決策變量：

3.2 模型的建立

綜合考慮運輸成本和環境成本的同時取送貨路徑選擇模型如下：

約束條件：

目標函數式（4）表示總成本最小，包括運輸成本和環境成本兩部分；約束條件式（5）表示離開配送中心的數量和回到配送中心的數量相等，即車輛從配送中心出發，任務完成后返回配送中心；式（6）表示每個顧客只能被車輛服務一次；式（7）表示每種車型的數量限制；式（8）表示車的裝載量不大于它的最大裝載能力；式（9）和式（10）表示送貨需求和取貨需求被滿足；式（11）為決策變量的約束。

4 VRPSDP問題的遺傳算法設計

遺傳算法是模擬生物在自然環境中的遺傳和進化過程而形成的一種自適應全局優化概率搜索算法，它廣泛應用于各種學科。本文所研究的是組合優化問題，其問題規模較大，搜索空間也急劇擴大，要尋找到一種能以有限的代價來解決最優化問題的通用方法仍是一個難題。而遺傳算法卻為我們解決這類問題提供了一個有效的途徑和通用框架，開創了一種新的全局優化搜索算法。

遺傳算法的特點：（1）可以直接以目標函數作為搜索信息。傳統的算法不僅需要利用目標函數值，而且往往需要目標函數的導數值等其他一些輔助信息才能確定搜索方向。（2）可以同時使用多個搜索點的搜索信息。由很多個體所組成的一個初始群體開始最優解的搜索過程，而不是從單一的個體開始搜索，這也是遺傳算法所持有的一種隱含并行性。

遺傳算法的求解步驟：（1）選擇能夠直觀反映問題的編碼方式，并設置相應的參數；（2）隨機產生初始種群；（3）對群體中的每一個個體進行適應度評價；（4）對種群進行選擇操作；（5）對種群進行交叉操作；（6）對種群進行變異操作；（7）判斷是否滿足本論文選擇的終止條件的標準，若不滿足繼續執行（3）、（4）、（5），如果滿足則輸出結果。

4.1 編碼

為了便于直觀反映車輛的路徑，本文采用自然數編碼策略，同時需要相應調整遺傳操作策略。自然數編碼方式也存在著三種不同的編碼方法，為避免計算機存儲量較大，將采用顧客直接排列的編碼方式，即用1～n自然數表示顧客，這些自然數的任意排列就是一個解，按照問題的約束條件，依次將解的每個顧客納入車輛的配送路徑中。如123456789，首先將顧客1納入第一條配送路徑中，看是否滿足約束條件，若滿足則構成配送路徑0-1-0，再將2納入這條配送路徑中，判斷是否滿足約束條件，若滿足則構成配送路徑0-1-2-0，接著將3納入這條配送路徑中，若不能滿足問題的約束條件，則顧客3不能由這條路徑配送，要重新開始一條新的配送路徑即0-3-0；重復上述過程，直到把每個顧客都納入到配送路徑中。

4.2 適應度函數

遺傳算法中使用適應度這個概念來度量群體中各個個體在優化計算中有可能達到或接近于或有助于找到最優解的優良程度。為了遺傳操作的簡單進行，適應度函數可以基于目標函數式（4）進行構建。

4.3 遺傳算子

4.3.1 選擇算子。選擇操作建立在對個體的適應度進行評價的基礎上，選擇操作的主要目的是為了避免基因缺失、提高全局收斂性和計算效率。

由于選擇、交叉、變異等遺傳操作的隨機性，它們也有可能破壞掉當前群體中適應度最好的個體，降低群體的平均適應度，對遺傳算法的運行效率、收斂性有不利的影響，所以我們希望適應度最好的個體要盡可能的保留到下一代群體中。為達到這個目的，將采用輪盤賭選擇法并結合最優保留策略進化模型來進行優勝劣汰操作。

4.3.2 交叉算子。從遺傳算法運算過程中產生新個體的能力方面來說，交叉運算是產生新個體的主要方法，它決定了遺傳算法的全局搜索能力。本文采用了適用于整數編碼問題的部分匹配交叉法。其優點是能夠保證即使兩個相同的個體進行交叉依然能產生新的個體，從而擺脫了傳統交叉算子對群體多樣性的要求，同時避免了早熟現象，降低了局部最優解的可能。在一定程度上保持了種群的多樣性，避免陷入局部最優解。假設隨機選擇兩個父代P1：123|456|78和P2:437|816|52，隨機產生兩個交叉點，交叉點中間的區域部分稱為匹配區域，交換P1和P2的兩個匹配區域，從而獲得匹配關系：8和4；1和5；6和6交換映射基因碼，得到兩個子代C1:52381674和C2:83745612。

4.3.3 變異算子。從遺傳算法運算過程中產生新個體的能力方面來說，變異運算是產生新個體的輔助方法，它決定了遺傳算法的局部搜索能力。變異算子的目的是增強種群的多樣性，本文針對所研究問題的特征，采用倒位變異算子。以一定的變異概率從種群中隨機選取其中的一個個體并產生兩個變異點，將變異點中間的元素進行逆轉操作。如一個個體為12|3456|789，“3”和“6”是兩個變異點，將變異段進行逆轉得新個體12|6543|789。

5 算例分析

5.1 實例計算

假設某一配送中心為27個顧客同時配送貨物和取貨，配送中心和顧客的坐標及配送量與回收量見表1，配送中心有2種車型且每種車型的數量已知，每種車型的參數見表2，參考文獻[13]設置燃油轉化系數為2.68（千克CO2/升）。求解如何合理地安排車輛的行駛路線，使得企業的運輸成本和環境成本最小。

表1 客戶節點坐標及取送貨需求量統計表

表2 配送車輛信息

遺傳算法參數的設定：

遺傳算法中需要選擇的運行參數主要有群體大小M、交叉概率Pc、變異概率Pm、終止代數T等。這些參數對遺傳算法的運行性能影響較大，須認真選取。

（1）群體大小M。群體大小M表示群體中所含個體的數量。M取值較小時，可提高遺傳算法的運算速度，卻降低了群體的多樣性，有可能引起遺傳算法的早熟現象；若M取值較大時，又會使得遺傳算法的運行效率降低。一般取值范圍為20～100，本文M取值為100。

（2）交叉概率Pc。交叉操作是遺傳算法中產生新個體的主要方法。Pc若取值過大，會破快群體中的優良模式，對進化運算產生不利影響；Pc若取值過小，產生新個體的速度較慢，一般建議的取值范圍是0.4～0.99，本文Pc取值為0.9。

（3）變異概率Pm。Pm取值較大雖然能產生較多的新個體，但可能破快掉很多較好的模式，使得遺傳算法的性能近似于隨機搜索算法的性能；若Pm取值太小，則變異操作產生新個體的能力和抑制早熟現象的能力就會較差。一般建議的取值范圍為0.000 1-0.1，本文Pm取值為0.01。

（4）終止代數T。其有兩個判定標準：①設定遺傳算法運行結束條件的一個參數，當遺傳算法運行到指定的進化代數之后就停止運行，并將當前群體中的最佳個體作為所求問題的最優解輸出。一般建議的取值范圍是100～1 000。②當群體已經進化成熟且不再有進化趨勢時就可終止算法的運行過程，本文選擇第2個標準終止代數，在進化到后五次后收斂性趨于穩定。

5.2 求解結果分析

根據以上數據，利用遺傳算法在計算機上運用C#進行算法編程，求解本文所建立的VRPSDP模型，得到最優目標函數值及相對應的最優車輛路徑可行解，算法運行10次的結果見表3。

表3 算法運行10次取得的同時取送貨結果

從10次運行結果來看，通過對比分析，本文選取總成本最小的最優路徑即方案7，其具體的車輛安排及行駛路線見表4。

表4 最優結果

車輛路徑示意圖如圖1所示。

圖1 車輛路徑示意圖

根據算例結果，本文所建立的模型和設計的算法較好地解決了既考慮運輸成本又考慮環境成本的同時取送貨的車輛路徑選擇問題。結果分析：（1）從10次運行的結果來看，總里程短的并不一定總成本最低，說明影響成本的因素有很多，不能片面追求里程最優；（2）環境成本在總成本中所占的比例較小，考慮環境成本對企業的總成本影響并不大，但對二氧化碳排放的減少有很好的效果，所以企業在考慮減少經濟成本時兼顧環境成本，更能履行好企業的社會責任；（3）不同的車型其裝載能力和碳排放量不同，所花費的運輸成本和環境成本也不同，應根據裝載量等要求進行合理的安排車輛。

6 結論與展望

6.1 結論

（1）建立“雙成本”視閾下雙向物流車輛路徑選擇模型，通過使用遺傳算法求得總成本最少的最終路徑。通過實驗證明，該算法計算效率高，能得到較滿意的解，結果穩定，表明該算法在求解該問題的有效性。

（2）研究結果為快遞企業在減少運輸成本時也能履行社會責任提供了合理的方案及決策支持，具有一定的參考價值和建議。

（3）車輛的碳排放是產生全球碳排放的主要因素，影響車輛碳排放的因素很多，例如：道路狀況、車速、距離、載重等。本文在研究過程中做了簡化，只研究了車型、距離、載重對碳排放的影響，這與實際運作情況存在一定的差異。

6.2 展望

（1）路徑優化問題在實際情況中更加復雜，本文的研究是一種相對理想的狀態，模型中的參數獲取比較理想化，后續應該進行大量的實驗，尋找更加精準的參數值。

（2）本文只考慮了一個配送中心，在實際中可能有多個配送中心；而且當前顧客需求趨于多樣性和及時性，也要求企業在時間上有特殊的要求，所以未來的研究應該更加貼近現實。

[1]Dantzig G,Ranser J.The truck dispathing problem[J].Management Science,1959,6(1):80-91.

[2]Min H.The multiple vehicle routing problems with simultaneous delivery and pick-up points[J].Transportation Research,1989,23(5):377-386.

[3]張建勇,李軍.具有同時配送和回收需求的車輛路徑問題的混合遺傳算法[J].中國公路學報,2006,(4):118-122.

[4]劉晴.隨機需求同時取送貨車輛路徑問題建模及優化研究[D].南京:南京航空航天大學,2012.

[5]王超,穆東.物料配送和廢舊產品回收的VRPSDP問題的并行模擬退火算法[J].北京交通大學學報,2014,(6):19-26.

[6]Sbihi A,Eglese R W.Combinatorial optimization and green logistics[J].Annals of Operations Research,2010,175(1):159-175.

[7]Demir E,Bektas T,Laporte G.The bi-objective Pollution-Routing Problem[J].European Journal of Operational Research,2014,232(3):464-478.

[8]鐘聰兒,邱榮祖.綜合考慮碳排放與運輸費用的配送路徑優化[J].數學的實踐與認識,2016,(21):89-94.

[9]侯躍,楊斌,許波桅,等.考慮碳交易的多車型運輸車輛配送路徑優化[J].遼寧工程技術大學學報(自然科學版),2015,(5):647-652.

[10]朱長征,李艷玲.碳排量最小的車輛路徑優化問題研究[J].計算機工程與應用,2013,(22):15-18.

[11]張立毅,王迎,費騰,等.混沌擾動模擬退火蟻群算法低碳物流路徑優化[J].計算機工程與應用,2017,(1):63-68,102.

[12]葛顯龍,許茂增,王偉鑫.多車型車輛路徑問題的量子遺傳算法研究[J].中國管理科學,2013,(1):125-133.

[13]史春陽.同時取送貨的車輛路徑問題中的低碳研究[D].北京:清華大學,2011.

A Duo-cost Perspective on Logistics Vehicle Two-way Route Selection Problem

Liu Yue,Fu Shimin
(Chongqing University of Posts&Telecommunications,Chongqing 400065,China)

In this paper,on the basis of traditional researches on the routing problem,we added in such constraints as"simultaneous pick-up and delivery"and"environment cost",built the logistics vehicle two-way route selection model from the duo-cost perspective,and designed the suitable genetic algorithm for its solution.Next,through a case study,we demonstrated the validity and feasibility of the model and algorithm.

duo-cost;simultaneous pick-up and delivery;logistics vehicle;route selection;transportation fee;CO2discharge;genetic algorithm

F252.14;F253.7

A

1005-152X(2017)10-0069-06

10.3969/j.issn.1005-152X.2017.10.015

2017-08-19

國家郵政局委托研究項目（E2016-84）

劉躍（1958-），男，四川內江人，重慶郵電大學經濟管理學院副院長，教授，碩士，研究方向：電子商務；付世敏（1989-），通訊作者，女，河南商丘人，重慶郵電大學經濟管理學院碩士研究生，研究方向：物流規劃與設計。