基于云計算的冷鏈物流配送車輛路徑優(yōu)化方法研究

劉 鎮(zhèn)，徐優(yōu)香，王 譯

（江蘇科技大學 計算機科學與工程學院，江蘇 鎮(zhèn)江 212003）

物流配送信息化是物流發(fā)展的趨勢，冷鏈物流配送信息化過程中存在的問題有：運輸車輛實時路況信息的獲取，物流車輛的配送路線的快速計算，運輸車輛動態(tài)信息的實時獲取等，這些都是在提高配送效率方面亟待解決的問題。雖然目前國內對物流車輛路徑問題的研究已有一定的成果[2]，但是研究還處于初級階段，仍處在進一步研究和探討的問題，主要有以下幾個方面：

1）研究的問題大部分是對確定性問題的研究，即冷鏈物流中心、冷藏產品需求量、車輛的位置都是確定的，對復雜情況下路徑問題的研究比較少。

2）對于實際冷鏈物流配送中的多種不確定性[1-2]因素，在現(xiàn)有的研究中主要集中在針對單一因素引起的動態(tài)車輛路徑問題的研究，對實際冷藏車的位置、交通路況、天氣等因素較少綜合考慮。

3）冷鏈物流動態(tài)車輛路徑問題對實時性的要求較高，需要在有效的時間范圍內處理各種變化的信息，并提供計算結果，則處理該類問題的并行算法需要進一步分析和研究。

4）現(xiàn)有的配送車輛路徑問題的研究中，針對冷鏈物流這種特殊物流車輛路徑問題的研究比較少。

本文利用云中心中多源海量信息，采用云處理方法研究冷鏈物流配送實時車輛路徑優(yōu)化問題。

1 冷鏈物流配送車輛路徑優(yōu)化問題探討

1.1 冷鏈物流的特點

與常溫物流相比，冷鏈物流具有以下特點[3]：

1）產品具有易腐性，冷鏈物流配送的貨物為生鮮產品、速凍食品、藥品等，配送過程中由于各種原因會使產品質量逐漸下降。

2）產品具有時效性，由于冷場產品具有易腐蝕性，且生命周期比較短，其生產、貯存、配送和銷售要在短時間內完成。

3）對運輸裝備具有特殊要求，由于一天中氣溫會隨著時間推移而放生變化，因此在不同的氣溫下為了維持產品在適宜的低溫環(huán)境下，配送的車輛必須為冷藏車。

鑒于以上特點研究冷鏈物流配送車輛路徑優(yōu)化的問題，其目的是快速的為冷藏車提供實時最優(yōu)路徑，降低配送成本，提高配送效率。

1.2 云計算環(huán)境下冷鏈物流配送車輛路徑優(yōu)化的優(yōu)勢

基于云計算的冷鏈物流配送車輛路徑優(yōu)化問題的數學模型本質上與傳統(tǒng)冷鏈物流配送車輛路徑優(yōu)化問題的數學模型是一樣的，均為通過合理安排車輛的配送路線和行車時間，使目標函數最優(yōu)，即配送時間最短和成本最低，區(qū)別在于模型前提條件的構建，傳統(tǒng)優(yōu)化模型中所有的因素（貨物需求量、客戶位置、冷藏車載重量等）都是確定的，而基于云計算的冷鏈物流的車輛路徑優(yōu)化模型中有些因素（車輛的實時位置、行駛車速、車廂環(huán)境等）是動態(tài)變化的，該模型能有效的降低冷鏈物流配送成本和時間，提高服務效率，更具有實用價值，基于云計算[4]的冷鏈物流配送車輛路徑優(yōu)化服務具有以下優(yōu)勢。

1）云計算將各種分散獨立的應用資源集中在同一個平臺下。云中心中有豐富的海量信息資源，如構建冷藏車優(yōu)化模型所需的實時交通信息、天氣信息、物流信息等，用戶通過統(tǒng)一接口獲取所需多源數據資源，實現(xiàn)所需物流配送業(yè)務的自適應。

2）云模式中將所有計算、應用資源集中起來，通過軟件自動管理，在云端以服務形式向用戶提供基礎架構、應用服務、軟硬件資源等，冷鏈物流企業(yè)通過SaaS（軟件即服務）模式取得所需服務，不需要購買昂貴的硬件設備，也無需負擔頻繁的升級維護費用，只需支付低廉的服務費用即可所需的服務，提高物流的配送服務效率。

3）云計算實現(xiàn)資源開放和統(tǒng)一訪問，在云計算上構建冷鏈物流車輛路徑優(yōu)化應用服務，則用戶通過統(tǒng)一的接口就可以獲得物流配送的信息資源，構建自己的應用。

1.3 云計算中冷鏈物流配送的應用模式

云數據中心有交通信息、天氣信息、路段信息、地理信息等多源的海量信息，利用這些信息建立于云計算的冷鏈物流配送車輛路徑優(yōu)化服務平臺（其架構圖如圖1所示）。

圖1中底層資源層包括各種服務器、網絡等硬件設備，以及各種分散的冷鏈物流系統(tǒng)外的應用資源如交通、天氣等系統(tǒng)，通過虛擬化技術將存儲虛擬化、網絡虛擬化和服務虛擬化，形成龐大的資源池，其中在構建冷鏈物流配送車輛路徑優(yōu)化的服務平臺的應用中，將分散的冷鏈物流系統(tǒng)外的應用資源通過虛擬化技術將數據集成形成車輛優(yōu)化服務的中間件，并提供統(tǒng)一的訪問接口，從而為上層的服務平臺的構建提供資源支撐。

圖1中冷鏈物流配送車輛路徑優(yōu)化的服務平臺通過優(yōu)化模型的求解實現(xiàn)冷鏈物流配送車輛的動態(tài)路徑優(yōu)化，該平臺向下連接資源層，動態(tài)的聚合所有資源，向上通過接口為用戶提供可靠的最優(yōu)路徑。

圖1中上層服務應用層通過提供的服務的接口，用戶可以通過網絡隨時、隨地接入應用服務層，訪問需求的冷鏈物流配送車輛的動態(tài)路徑優(yōu)化服務，接入服務平臺的方式可以為Web服務接口、瀏覽器、桌面應用程序及移動終端等。

圖1 基于云計算的冷鏈物流配送車輛路徑優(yōu)化架構圖Fig.1 Cloud-based cold chain logistics distribution vehicle routing optimization architecture diagram

基于云計算的冷鏈物流配送車輛路徑優(yōu)化服務平臺，能夠有效的解決冷鏈物流配送車輛實時路徑優(yōu)化中對實時信息的需求。平臺中通過統(tǒng)一訪問接口獲取云數據中心中所需的多源數據信息資源，分析冷鏈物流配送的綜合成本和配送時間，構建冷鏈物流車輛出行的路徑優(yōu)化模型，并利用云中心的計算資源，在有效的時間內快速的計算出有效的實時優(yōu)化路徑，提高物流服務效率，使冷鏈物流的配送成本達到精細化的管理。

2 基于云計算的配送車輛路徑優(yōu)化模型

2.1 冷鏈物流車輛配送路徑問題描述

根據圖1構建冷鏈物流配送車輛路徑優(yōu)化的架構，其優(yōu)化模型的最終目標為車輛行駛總時間和配送成本最優(yōu)，但是當獲取的信息源變化時，其優(yōu)化模型會有差異。在此以獲取云中心的實時交通信息為例，建立冷鏈物流配送車輛實時路徑優(yōu)化模型，需滿足的約束條件如下：

1）實時提取冷藏車所在位置的路段的車速和道路信息；

2）每個客戶的總需求量不超過車輛的最大裝載量；

3）每條配送運輸路徑的總長度不能超過車輛一次配送的最大行駛距離；

4）貨物在一定的時間范圍內到達，若超過時間范圍，則支付一定的罰金；

5）配送過程中車廂內環(huán)境溫濕度要在一定的范圍內，否則將影響客戶對產品的滿意度；

6）道路寬度大于車輛的寬度。

數學描述：冷藏車從物流中心的倉庫出發(fā)，車輛一次配送的最大行程為S，冷藏車的最大裝載量為Q，車輛的寬度為L，為N個客戶供貨，已知每個客戶點i的位置及貨物的需求量qi，客戶i到j的運輸時間為tij，集合Rk表示第k條路徑，其中集合元素rki為客戶rki在路徑k中的順序為i，設rk0表示車輛出發(fā)的配送中心，車輛在第k條路徑上的實時速度為Vk，云計算中心獲取的實時路網信息Lk，以車輛配送時間和成本為目標函數。

2.2 冷鏈物流配送車輛路徑優(yōu)化模型

對冷藏車輛路徑優(yōu)化模型的分析包括配送時間和配送成本的分析，在架構中通過統(tǒng)一的接口訪問交通信息云，獲取車輛所在位置的交通信息進行配送時間分析，配送綜合成本分析包括固定成本、運輸成本、貨損成本、能源成本和懲罰成本的分析。

2.2.1 配送時間分析

通過在云中心的實時交通信息中獲取車輛行駛中所在路段的實時交通信息，進行配送時間的計算。車輛所在位置路段平均車速Vi、車道寬度LRi及允許通行車輛的噸位。根據Vi的大小判斷路段的交通擁堵程度和預測車輛經過所需的時間tj（j-1）。當Vi=0時，表示該路段當前處于擁擠狀態(tài)，只有當車道寬度LRi大于車輛寬度L并且允許通行車輛的噸位QRi大于車輛的總噸位Q時，路徑i才有被選擇的可能，因此車輛完成配送的總行駛時間T如公式（1）所示。

2.2.2 配送綜合成本的分析

1）固定成本

運輸車輛的固定成本C1有駕駛員和押運員的工資和車輛損耗的成本，C1=f為常數。

2）運輸成本

車輛的運輸成本C2包括車輛的油耗、維修和保養(yǎng)成本，與車輛行駛的里程數呈正比，如公式（2）所示。

cij為冷藏車在路段（vi，vj）上的運輸成本，并且cij=cji，其中xij用0，1表示，xij=1表示冷藏車經過了路段（vi，vj），否則xij=0。

3）冷藏品損壞成本

冷藏品的損壞成本包括3種情況：第一，由于運輸時間和卸貨時間的長短造成的貨損；第二，服務顧客時，車廂門的頻繁開啟造成車廂內的冷空氣與外界空氣交替流動，導致車廂內溫度上升，使冷藏品遭到損壞；第三，由于路況的好壞程度，使冷藏品遭到損壞。冷藏品損壞成本用C3表示，如公式（3）所示。

其中，r表示產品的單價，λj為0，1變量，λj=1表示該冷藏車服務客戶j，否則λj=0；α1為產品運送過程中損壞的比例；tij表示客戶i到客戶j所用的時間；α2表示產品在車廂門開啟及裝卸過程中損壞的比例；βj為客戶j的貨物的數量；α3表示車輛運輸過程中造成產品損壞的比例；sij表示客戶i到客戶j之間的里程數。

4）冷藏車輛的能源成本

冷藏車的能源成本主要是消耗制冷劑的成本。制冷劑消耗量跟車廂的傳熱系數、車廂內的溫度、車體內外的表面積及外界的溫度有關。制冷劑消耗量的計算公式，如公式（4）所示。

其中G表示制冷劑的消耗量，a為常數；b為傳熱系數；S為車體內外的平均表面積，Δt為車廂內外的溫度差。則車輛行駛中的制冷成本用C4表示，如公式（5）所示。

其中r1為制冷劑的價格，tij為從客戶i到客戶j的時間，xij為0，1變量。

打開車門時外界空氣直接與冷藏車內的空氣對流，發(fā)生冷熱交替，因此計算打開車廂門的制冷成本只需計算由車門的熱交換而消耗制冷劑的成本，用C5表示，如公式（6）所示。

其中ti為車輛在客戶i停留和等待的時間，S為車門的面積。

5）超出客戶配送時間的懲罰成本

向客戶配送貨物有時間限制，在此采用軟時間窗的限制方法進行處理，即對客戶需求的貨物在一定的時間范圍內到達，若未能按時到達，則將對物流配送企業(yè)給予一定的罰金。則因不在時間窗內將產品送到客戶點而產生的處罰成本用C6表示，如公式（7）所示。

其中ω1、ω2分別表示冷藏車輛早于和晚于時間窗將貨物卸下而帶來的損失成本。sj為車輛到達客戶j的時刻，tj為車輛在客戶j處等待的時間。

6）其他成本

冷藏品配送過程中，在有時間限制條件下，會產生其他費用如：在高速路上行駛產生高速的收費成本等。用C7表示，如公式（8）所示。

其中，式（9）將時間和成本作為優(yōu)化的目標函數，模型求解時根據其在實際冷鏈物流中的重要性賦予一定的權重W1和W2。式（10）為冷藏車配送總時間，等于車輛的行駛時間和其在客戶處的總停留時間之和。式（11）為冷藏車配送成本等于固定成本、運輸成本、損壞成本、能耗成本、懲罰成本之和。式（12）保證運輸路徑上各客戶的貨物需求量之和小于車輛的最大裝載量。式（13）保證車輛每次配送行駛的最大距離小于車輛的最大行駛距離。式（14）為車輛到達下一個客戶點的時刻＝車輛到達當前客戶時刻+在當前客戶等待卸貨時間+在當前客戶卸貨時間+從當前客戶到達下一客戶的行駛時間。式（15）表示車輛在客戶處等待時間由服務時間窗開始時刻和車輛到達客戶的時刻決定，到達時刻早于服務時間窗開始時刻，則車輛在客戶處等待，到達時刻晚于服務時間窗，則等待時間為0。式（16）保證每個客戶都被運輸車輛服務到。式（17）保證每個客戶由一輛冷藏車服務。式（18）保證行駛路段路寬大于車輛的寬度。

3 路徑優(yōu)化模型求解

并行計算是云計算應用具體實現(xiàn)的關鍵技術，因此，本文在云計算環(huán)境下，利用云中心的計算資源，采用粗粒度并行遺傳算法[5－10]對冷藏車路徑實時優(yōu)化模型進行求解，可以加快優(yōu)化路徑的計算效率。其流程圖如圖2所示，隨機生成m*n個子群體分布在可行集內，依處理器個數將群體分割成m個子群體，每個子群體有n個個體，每個子群體在不同的處理器上獨立的并發(fā)執(zhí)行遺傳操作，每個子群體最后都會找到一個或多個局部極值點，通過子群體之間的信息傳遞，使采樣點集中在最優(yōu)解的區(qū)域，經過t次操作后搜索出最優(yōu)個體。其實現(xiàn)步驟如下：

圖2 并行化遺傳算法流程圖Fig.2 Parallel genetic algorithm flowchart

步驟1：種群初始化：通過隨機方法產生m*n個體，每個個體對應一個解，形成初始種群；

步驟2：將初始種群平均分為m個子種群；步驟3：主循環(huán)開始While i≠t do

步驟3.1：while k≠n do

步驟3.1.1：染色體編碼：根據冷鏈物流車輛路徑特點，對產生的種群進行二進制編碼；

步驟3.1.2：計算函數的適應度值：算法使用適應值來評估個體所對應行車路徑的優(yōu)劣，個體適應度越大則被遺傳到下一代的概率越大，本文中適應值函數取目標函數的倒數；

步驟3.1.3：選擇：從種群中選擇適應環(huán)境的個體，適應值越高的個體被選擇的幾率就越大；本文采用輪轉法作為選擇方法，選擇概率為為種群個數；

步驟3.1.4：交叉：對兩個不同個體的相同位置的基因進行交換，產生新的個體，采用OX方法進行交叉；

步驟3.1.5：變異：以相同的變異率改變染色體的一個或幾個基因，每條染色體的變異幾率相同；

步驟3.1.6：生成下一代個體；

步驟3.2：選取適應度值較好的個體；

步驟4：獲取最優(yōu)個體；

步驟5：輸出結果。

4 實驗仿真

根據利用實時交通信息建立的模型在云計算冷鏈物流配送車輛路徑優(yōu)化服務平臺中的處理過程如圖3所示。

圖3 模型仿真工作原理圖Fig.3 Schematic diagram of the model simulation work

為了驗證云計算環(huán)境下求解的有效性，本文以鎮(zhèn)江恒偉物流公司的冷藏車向客戶運送冷藏土豆條為例。配送中心編號為”0”，客戶i的需求量qi，卸貨時間si，客戶之間位置如表1及要求服務時間范圍如表2所示。配送車輛在最大載重量為4.5t，車輛從配送中心出發(fā)，假設車輛固定成本f＝1 000，單位運輸成本c0＝4，車內溫度為－10℃，車外溫度為30℃，車輛使用液態(tài)氮為制冷劑，每千克液氮價格假設為4.5元，則a＝0.91，b＝4.5，S＝16，K＝1，Δt＝50，懲罰成本為5元/分鐘，設冷藏車要向8個客戶配送土豆條。設定種群大小N為30，交叉概率Pc為0.7，變異概率Pm為0.05，最大迭代次數T為500。

表1 各客戶點的距離Tab.1 Distance of each customer

表2 客戶時間窗范圍及需求量Tab.2 Scope of the customer time windows and the demand of goods

根據配送中心對車輛配送成本和配送時間的關注程度不同設置不同的比重，模擬云中心實時路況信息，實驗環(huán)境為同一個局域網內4臺PC機組成。情況1：令W1＝0，W2＝1，得到最優(yōu)路徑：0－6－7－3－1－4－2－8－5，總成本為1 620元，總里程數為72 km，車輛行駛時間為2.17小時，計算時間為10.79 s；情況2：令W1＝1，W2＝0，得到的最優(yōu)路徑：0－5－6－7－2－4－3－1－8，車輛行駛時間為1.84小時，總成本為1 736元，總里程數為76 km，計算時間為11.56 s。計算結果均在有效的時間范圍內得出最優(yōu)路徑，同時，根據對對車輛配送成本和配送時間的關注程度不同，所計算結果的時間和花費也不一樣，同時，在W1＝0，W2＝1時采用不同個數的處理機，算法執(zhí)行的時間也不一樣，在一定程度上處理器個數越多，其計算時間越短。如表3所示。

表3 不同個數處理器執(zhí)行時間比較Tab.3 Comparison of different processors execution time

5 結束語

文中介紹了冷鏈物流相對常溫物流的特殊性，分析了采用云計算進行冷藏車輛實時路徑優(yōu)化的意義。利用云計算技術通過統(tǒng)一的接口獲取實時路徑優(yōu)化所需的實時多源信息，建立了冷鏈物流配送車輛路徑優(yōu)化的應用服務架構。本文并在該架構下，獲取實時交通信息，分析冷藏車輛的行駛速度和路況，計算配送的總時間，同時對冷藏配送的固定成本、運輸成本、能源成本、貨損成本、懲罰成本等進行分析，以配送的總時間和成本為依據建立了冷鏈物流配送車輛路徑優(yōu)化模型；根據并行計算是實現(xiàn)云計算應用的關鍵技術，本文利用利用粗粒度并行遺傳算法對模型進行求解，仿真結果驗證了基于云計算冷鏈物流車輛路徑優(yōu)化方法的有效性，提高了配送服務效率。

[1]劉云霞，彭鴻廣，曹玉華，等.不確定信息的物流配送實時車輛優(yōu)化調度策略[J].浙江科技學院學報，2008，20（4）：289－291，320.LIU Yun-xia，PENG Hong-gang，CAO Yu-hua.Strategy of vehicle optimal scheduling about logistics delivery based on indeterminate information,Journal of Zhejiang University of Science and Technology，2008，20（4）：289－291，320.

[2]白世貞，丁旭.動態(tài)行程時間車輛路徑規(guī)劃問題研究[C].//第十三屆中國管理科學學術年會論文集，2011：53－58.

[3]蘇云，劉澤勤.冷鏈物流配送現(xiàn)狀及其能耗分析[C].//第五屆中國冷凍冷藏新技術新設備研討會論文集，2011：22－25.

[4]陳全，鄧倩妮.云計算及其關鍵技術[J].計算機應用，2009，29（9）：2562－2567.CHEN Quan，DENG Qian-ni.Cloud computing and its key techniques[J].Journal of Computer Applications，2009，29（9）：2562－2567.

[5]武金瑛.一種粗粒度并行遺傳算法及其應用[J].計算力學報，2002，19（2）：148－153.WU Jin-ying.A parallel genetic design method with coarse grain[J].Chinese Journal of Computational Mechanics，2002，19（2）：148－153.

[6]易榮貴，羅大庸.基于遺傳算法的物流配送路徑優(yōu)化問題研究[J].計算機技術與發(fā)展，2008，18（6）：13－15，19.YI Rong-gui，LUO Da-yong.Study of the optimizing of physical distribution routing problem based on genetic algorithm [J].China Journal of Highway and Transport，2008，18（6）：13－15，19.

[7]Ana Osvald a，Lidija Zadnik Stirn b.A vehicle routing algorithm for the distribution of fresh vegetables and similar perishable food.Received 26 March 2006;received in revised form 19 July 2007;accepted 20 July 2007;Available online 2 August，2007.

[8]Ying,Wang,Xi,Chen.Research on Vehicle Routing Problem of Cold Chain Logistics[C].//2010 International Conference on Multimedia Information Networking and Security.2010：329－334.

[9]王祥生，馬壽峰.實時路況信息下配送路徑的優(yōu)化[J].工業(yè)工程，2008，11（1）：113－116，125.WAG Xiang-sheng，MA Shou-feng.Optimization of delivery routes based upon real-time traffic information[J].Industrial Engineering Journal，2008，11（1）：113－116，125.

[10]唐健，史文中，孟令奎，等.基于遺傳算法的時相關動態(tài)車輛路徑規(guī)劃模型[J].武漢大學學報：信息科學版，2008，33（8）：875－879.TANG Jian，SHI Wen-zhong，MENG Ling-kui. Timedependent dynamic vehicle routing based on genetic algorithm[J].Geomatics and Information Science of Wunan University，2008，33（8）：875－879.