時間窗約束下帶逆向物流的冷鏈物流車輛路徑優化研究

宋志蘭，黃　歡，張　壯

（云南財經大學　物流學院，云南　昆明　650221）

時間窗約束下帶逆向物流的冷鏈物流車輛路徑優化研究

宋志蘭，黃歡，張壯

（云南財經大學物流學院，云南昆明650221）

針對冷鏈物流配送路徑的特性，將時間窗約束下的逆向物流車輛配送路徑方法引入冷鏈物流配送路徑優化問題中，在冷鏈物流配送路徑問題中同時考慮送貨和取貨，不僅考慮車輛固定成本和運輸成本，還考慮了在配送過程中貨物的損耗成本、能源消耗成本以及違反客戶時間窗帶來的懲罰成本、信用損失等成本，建立了使得服務時間滿足顧客時間窗約束的帶逆向物流的冷鏈物流配送成本模型。最后以某生鮮食品連鎖店為例，運用建立的模型進行路徑規劃，驗證了模型的可行性。

冷鏈物流；時間窗；逆向物流；配送路徑優化

1　引言

隨著物流業的快速發展，配送環節作為物流系統中的重要環節，對提高整個物流系統運作效率越來越重要。消費者對食品的關注點不再是簡單的數量問題，人們更多的關注鮮活農產品質量問題，這就使得冷鏈物流配送中心在提高自身利潤的同時必須確保配送產品的安全性、準時性。在傳統的冷鏈物流配送中，配送車輛只是單純的送貨（取貨）。單向的配送路徑不僅使得配送成本高，顧客服務周期長，同時還加重了車輛的碳排放量。配送路徑的合理選擇，可以有效降低企業配送成本，提高顧客滿意度，實現綠色物流，從而提高經濟效益和社會效益。

車輛路徑優化問題（Vehicle Routing Problem，VRP）是指在一系列約束條件（如配送車輛的數量和最大載重量、配送時間等）下，針對顧客的一系列要求（送貨量、送貨時間），制定合理的配送路徑，以實現運輸成本最低、貨物損失最少等問題。本文研究帶逆向物流的車輛路徑問題，即當有嚴格的送貨和取貨時間要求時，冷鏈配送中心同時給多個客戶送貨并同時取貨的雙向冷鏈物流配送問題。

國內外專家學者主要從以下兩個方面來研究冷鏈物流車輛路徑：

（1）時間窗約束下冷鏈物流車輛路徑優化研究。陳夢等［1］針對我國冷鏈物流配送成本高的問題，在增加制冷成本和貨損成本的基礎上建立了軟時間窗下冷鏈物流配送路徑優化模型，并運用遺傳算法證實了模型的可行性。劉琳［2-3］從節約物流總成本角度構建了時間窗冷鏈物流配送模型，并運用節約法得出最優解。Michael Saint-Guil-lain等［4］提出利用多目標動態規劃模型來優化基于時間窗的車輛路徑問題。Wei Shi和Balseiro SR等［5-6］采用蟻群算法解決滿足時間窗條件下的車輛路徑優化問題。繆小紅等［7］進一步探索了冷鏈物流配送優化方案，并用改進遺傳算法給出了問題的最優解。韓印等［8］考慮了道路交通狀況對冷鏈物流車輛送貨成本和車輛路徑的影響，并運用節約里程法進行求解。以上文獻都只是局限于單程送貨路徑優化研究，未考慮回程取貨問題。

（2）時間窗約束下集送貨同時的車輛路徑優化研究。程文科［9］分別從無時間窗約束和有時間窗約束兩個角度構建了帶回程取貨的逆向物流車輛路徑優化模型并運用遺傳法得出最優解。Sumaiya Iqbal等［10］分析了軟時間窗下多目標車輛路徑優化問題，并運用蜂群法對模型進行求解。閔嘉寧等［11］將時間窗約束轉化為里程約束進行集送貨車輛路徑分析。Sally Kassem等［12］運用啟發式算法和模擬退火算法構建了集送貨同時進行的閉環物流網絡。Zhang Tao等［13］運用蟻群算法和禁忌搜索方法得出了時間窗下同時送貨和取貨的車輛路徑模型最優解。

以上文獻考慮了送貨和集貨同時進行，但均集中于遺傳算法、蜂群法、蟻群算法等，并未考慮節約里程法的運用。

雖然國內外有大量的相關研究，為冷鏈物流車輛路徑優化研究提供了一定的理論依據，但大多數研究偏向于對時間窗約束下冷鏈物流車輛路徑優化研究和時間窗約束下集送貨同時的車輛路徑優化研究，并集中偏向于用蟻群算法、遺傳算法和多目標動態規劃算法等解決問題，忽視了節約里程法在時間窗約束下帶逆向物流的冷鏈物流車輛路徑優化中的應用。節約里程法的基本思想是以實現客戶目標為前提對車輛路徑進行合理優化，本文研究在時間窗約束下帶逆向物流的冷鏈物流車輛路徑優化問題，解決在實踐中需要同時送貨和取貨的車輛路徑優化問題。通過用節約里程法合理優化傳統配送路徑，使得配送中心在節約配送成本的同時，提高客戶滿意度和減少碳排放等環保效益與經濟效益相統一的多目標。

2　時間窗約束下帶逆向物流的冷鏈物流車輛路徑模型建立

2.1模型假設

本文建立帶逆向物流的配送路徑模型，主要運用于單個配送中心向多個客戶配送，所有車輛均從配送中心出發，按時完成全部客戶的送貨和取貨任務后回到配送中心。為了簡化模型，對模型做如下假設：

（1）配送中心的坐標已知；（2）配送中心有足夠的車輛來滿足送貨和取貨的需求；（3）車輛在取送貨全程以勻速行駛；（4）車輛必須在規定時間窗下同時完成送貨和取貨任務；（5）每輛車的裝載量不能超過其本身的最大限量；（6）單位運輸距離的運輸成本相同；（7）每位客戶的需求量（包括送貨需求量、取貨量）與地理坐標、服務時間均已知；（8）客戶嚴格要求貨物的送達時間。

2.2模型建立

本文中配送總成本模型包括配送車輛的固定成本（主要指車輛租金、車輛損耗和人員工資）、配送過程中的運輸成本（主要指油耗成本、制冷成本）、配送過程中冷凍消耗成本、客戶服務時間成本（主要指裝卸貨時間成本）以及違反客戶要求時間窗增加的懲罰成本（包括企業因此而損失的信譽成本）等。

假設有n個客戶，M輛型號相同的冷鏈配送車，貨車的最大載重量為Q。

（1）配送車輛固定成本。車輛租金、車輛損耗以及駕駛員的工資等構成了車輛的固定成本，由此可得M輛車的固定總成本Cg為：

式中，Cg—M輛車的總固定成本，g—冷鏈配送車的固定成本；M—冷鏈配送車的數量。

（2）與運輸距離相關的配送車輛變動成本。車輛的運輸變動成本包括油耗成本以及在運輸過程中的制冷成本。與客戶的多少和路程的遠近有關，行駛的路程越遠運輸成本就越高，則總運輸成本為M輛車的總運輸成本之和，即：

式中，Cy—M輛車的總運輸成本；Cm—第m輛車的運輸成本；Cr—第m輛車的制冷成本；Cd—單位運輸距離的運輸成本；CR—單位運輸距離的制冷成本；dij—客戶i與客戶j之間的距離；Xijm—決策變量，當第m輛車從i點到j點時為1，否則為0。

（3）與時間相關的貨損成本與制冷成本。冷鏈車輛取送貨過程中，不僅會有燃油費、過路過橋費等直接與運輸距離有關的變動成本，還包括與運輸時間密切相關的貨物損失成本和制冷所消耗的能源成本。貨物的損失成本、制冷成本均與運輸時間成正比，記這部分的損失記為Cd，則：

式中，Cmd—第m輛車的貨物損失成本；Cmz—第m輛車的制冷能源消耗成本；v—運輸速度；β—單位時間內貨物的損耗成本；γ—單位時間內制冷設備消耗的能源成本；Yjm—決策變量。若第m輛車服務j客戶時，Yjm為1；否則Yjm為0。

（4）違反時間窗產生的懲罰成本。若第i個客戶要求的到達時間段為如果到達第i個客戶的時間早于ai，則需要等待至ai，等待就會產生一定的機會成本；如果到達第i個客戶的時間介于ai和bi之間，則為準時達到。如果到達第i個客戶的時間超過bi，則為遲到，則客戶會拒絕接受貨物，并要求按配送物的等價價值賠償，此時懲罰成本為配送物價值與企業信用損失之和。具體的計算公式為：

（5）配送車輛總成本。通過對以上相關成本的分析，建立帶逆向物流的冷鏈配送車輛路徑總成本

上式中，i=0，1，2，...，n；j=0，1，2，...，n；m=1，2，3，式（9）表示路徑數量不超過車輛總數；式（10）表示送貨的重量不超過M輛車的最大載貨量；式（11）表示取貨的重量不超過M輛車的最大載貨量；式（12）表示每條路線取送的貨物總和不超過貨車的載重量；式（13）和式（14）表示配送車輛起點和最后返回目的地都是配送中心；式（15）表示每一個客戶點有且只有一輛車在配送。

3　模型算法及算例分析

3.1模型算法的基本思路

本文采用了啟發式解法中的節約里程法，此法的優點是將送貨和取貨結合起來安排路線，提高車輛的重復使用率，降低配送成本，其關鍵在于送貨和取貨同時進行，不僅考慮車輛容量約束，還考慮顧客時間窗約束，即時間窗的上限者應優先安排配送。兩客戶點間的節省值Sij：

Sij表示節點Pj到節點Pi兩節點的節省值，dki表示節點Pk到節點Pi的距離。

在帶有時間窗的配送路線安排中，首先是送貨和取貨同時進行，同時考慮時間窗的要求，從節點i到節點j節約的信用成本與運輸到達時間和顧客要求的時間相關。第二是考慮節約成本的大小，涉及到的相關節約成本分別為節約的運輸成本、節約的貨損成本。節約的運輸成本、貨損成本均與節約距離正相關，即：

從節點i到節點j節約的貨損成本為：

從節點i到節點j節約的貨損成本為：

從節點i到節點j節約的總成本：

3.2節約里程法的操作步驟

第一步：計算出所有兩個客戶節省值Sij，并按大小排序；

第二步：將所有客戶的送貨（取貨）時間按先后順序排序；

第三步：找出時間限制最早的客戶，作為第一條線路的第一位客戶，在所有Sij中找出相應的客戶，求出在選定的最大節約值的路徑中，若不滿足顧客規定的時間窗，通過比較如果大于那么選擇此客戶為下一個路徑節點；反之，重新選擇顧客，直到找到滿足節約總成本最大的客戶作為第一條路徑的第二個客戶。即使得

第四步：重復第三步，直至這條路線達到時間窗或是車容量的限制，便求出第一條路徑的全部客戶；

第五步：刪除已經安排的配送客戶，在剩下的客戶中重復第三步和第四步，便可求出其余線路的送貨路徑。

4　算例分析

4.1相關數據說明

某生鮮食品加工廠向10家連鎖店配送冷凍食品，各連鎖店有嚴格的送取貨時間。配送中心有額定載重量為3.5t的送貨車，行駛速度30km/h，運輸成本Cd是1元/km，能源成本（主要指油耗成本和制冷成本）γ是20元/h，貨損成本系數β是80/h，機會成本α1是2元/min。當前市場食品價格P是3 000元/t，懲罰系數α2是5元/ min，信用損失系數CS為30%。配送中心的配送網絡圖如圖1所示，圖中P0為配送中心，P1到P10分別指10家需要送貨的連鎖店；括號內的數字表示需要配送的數量，負號表示需求取回量；線路上的數字表示道路距離。10個連鎖店的裝卸時間以及客戶對送/取貨時間要求見表1。

表1　10個連鎖店的裝卸貨作業時間、送貨時間要求

圖1　配送中心的配送網絡圖

4.2配送路徑求解與分析

第一步：首先根據配送中心的配送網絡圖計算各節點之間的最短距離，計算結果見表2。

表2　配送中心與10家連鎖店的最短配送距離（單位：km）

第二步：根據最短距離的計算結果，計算出各節點之間的節約里程Sij，并按節約值的大小進行排序，見表3。

表3　配送路線節約行程排序表

第三步：將10家連鎖店的時間要求按時間先后順序排序，結果見表4。

表4　對10家連鎖店要求的時間按先后順序排列

第四步：計算第一條路線A。

按照時間窗要求，將時間最早的連鎖店排在第一條路線A上。即P6是A線路上的第一個客戶，由于P6的需求量是1.5t（小于3.5t），所以繼續計算A線路上的第二個客戶，通過表3，找到最大的節約里程S65，并且可以準時到達P5，懲罰成本Cm（x5）為0元，節約里程S65為9km，節約運輸成本為9元，節約貨損成本為30元，節約總成本39，而P5的需求量為1.4t，沒有超過最大載重量Q，繼續求A線路上的第三個客戶。以此類推，最后求得A線路P0—P6—P5—P4—P0，見表5。

表5　路線A的配送路徑表

第五步：重復第四步，求得B線路：P0—P10—P1—P2—P3—P0，線路C：P0—P8—P9—P7—P0。最終可計算出既滿足10家連鎖店要求的送貨時間，且滿足總節約成本最大化的配送路徑，如圖2所示。

圖2　10家連鎖店配送優化網絡圖

各個線路配送活動中所消耗的各項費用見表6。總成本為1 259.7元，相比目前配送中心的配送成本1 534元［2］，降低了17.8%；同時，客戶滿意度達到100%，滿載率達到89.5%，均遠高于同行業平均水平，且保證了農產品新鮮度，實現了經濟效益和環保效益的共同協調發展。

表6　車輛路徑優化模型各項費用

5　結語

本文將帶時間窗約束下的逆向物流車輛配送路徑方法引入冷鏈物流配送路徑優化問題中，在冷鏈物流配送路徑問題中考慮送貨和取貨同時進行，不僅考慮車輛固定成本和運輸成本，還考慮了在配送過程中貨物的損耗成本、能源消耗成本以及違反客戶時間窗帶來的懲罰成本、信用損失等成本，建立了使得服務時間滿足顧客時間窗約束的帶逆向物流的冷鏈物流配送成本模型。同時使得冷鏈物流配送過程中最大程度上節約配送成本，提高了配送效率，增加了客戶滿意度，實現了綠色物流和社會可持續發展。節約里程算法的優點是將送貨和取貨結合起來同時安排路線，提高車輛的重復使用率，降低配送成本，減少碳排放。本文不足之處在于僅限節約里程法的運用，且未考慮到因客戶緊急訂單，需要插隊提前送貨或取貨的情況，后續將會對本局限作進一步研究。

［1］陳夢，曾陽，唐驛，等.食品冷鏈物流配送路徑優化問題研究［J］.物流工程與管理，2015，37（1）∶145-147.

［2］劉琳.冷鏈物流配送路徑優化模型及改進算法［J］.科技信息，2011，（10）.

［3］劉琳.冷鏈物流配送路徑優化模型及控制算法［D］.煙臺∶煙臺大學，2012.

［4］Michael Saint-Guillain，Yves Deville，Christine Solnon.A Multistage Stochastic Programming Approach to the Dynamic and Stochastic VRPTW［J］.Integration of AI and OR Techniques，2015，90（75）∶357-374.

［5］Wei Shi，Thomas Weise.An Initialized ACO for the VRPTW［J］. Intelligent Data Engineering and Automated Learning，2013，82（6）∶93-100.

［6］Balseiro，Loiseau，Ramonet.An Ant Colony Algorithm Hybridized with Insertion Heuristics for the Time Dependent Vehicle Routing Problem with Time Windows［J］.Omr and Oraon Rarh，2011，38（6）∶954-966.

［7］繆小紅，周新年，林森，等.第三方冷鏈物流配送路徑優化研究［J］.運籌與管理，2011，20（4）∶32-38.

［8］韓印，師攀.基于道路狀況的冷鏈物流配送路徑優化［J］.物流科技，2015，（6）∶90-93.

［9］程文科.帶回程取貨的逆向物流車輛路徑問題研究［D］.北京∶北京交通大學，2007.

［10］Sumaiya Iqbal，M Kaykobad，M Sohel Rahman.Solving the multi-objective Vehicle Routing Problem with Soft Time Windows with the help of bees［J］.Swarm and Evolutionary Computation，2015，24∶50-64.

［11］閔嘉寧，金成.基于改進節約算法的集送貨車輛路徑優化［J］.物流科技，2015，（6）∶44-48.

［12］Kassem Chen.Solving Reverse Logistics Vehicle Routing Problems with TimeWindows［J］.Journal of Advanced Manufacturing Technology，2013，68（1）∶57-68.

［13］Tao Zhang，W Art Chao Valitwongse，Yue-Jie Zhang.Integrated Ant Colony and Tabu Search Approach for Time Dependent Vehicle Routing Problems with Simultaneous Pickup and Delivery［J］.Journal of Combinatorial Optimization，2014，28（1）∶288-309.

Study on Reverse Logistics Considered Cold-chain Logistics Vehicle Routing Optimization with Time Window Constraint

Song Zhilan，Huang Huan，Zhang Zhuang
（School of Logistics， Yunnan University of Finance Economics， Kunming 650221， China）

In this paper， in view of the characteristics of the cold chain logistics distribution routes， we introduced the reverse logisticsvehicle routing process with time window constraint into the cold chain logistics vehicle routing problem， taking into consideration cargodelivery and pick-up， the fixed vehicle cost and the transportation， the loss cost， energy cost， penalty cost and reputation cost in the event ofbreaking the time window of the customers in the cargo delivery process， built the reverse logistics considered cold chain logistics distributioncost model aiming at satisfying the time window constraint of the customers， and at the end， demonstrated the feasibility of the model throughan empirical case study.

cold chain logistics； time window； reverse logistics； distribution route optimization

U116.2；F224

A

1005-152X（2016）03-0118-05

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

2016-02-14

宋志蘭（1967-），女，山西太原人，碩士，副教授，碩士生導師，物流學院物流工程系主任，主要研究方向：生產物流系統規劃設計及裝備概念研發、商業物流系統規劃設計及裝備概念研發。