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

宋志蘭，黃　歡，張　壯

（云南財經(jīng)大學　物流學院，云南　昆明　650221）

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

宋志蘭，黃歡，張壯

（云南財經(jīng)大學物流學院，云南昆明650221）

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

冷鏈物流；時間窗；逆向物流；配送路徑優(yōu)化

1　引言

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

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

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

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

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

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

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

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

2.1模型假設

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

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

2.2模型建立

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

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

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

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

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

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

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

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

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

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

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

3　模型算法及算例分析

3.1模型算法的基本思路

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

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

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

從節(jié)點i到節(jié)點j節(jié)約的貨損成本為：

從節(jié)點i到節(jié)點j節(jié)約的貨損成本為：

從節(jié)點i到節(jié)點j節(jié)約的總成本：

3.2節(jié)約里程法的操作步驟

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

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

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

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

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

4　算例分析

4.1相關數(shù)據(jù)說明

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

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

圖1　配送中心的配送網(wǎng)絡圖

4.2配送路徑求解與分析

第一步：首先根據(jù)配送中心的配送網(wǎng)絡圖計算各節(jié)點之間的最短距離，計算結果見表2。

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

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

表3　配送路線節(jié)約行程排序表

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

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

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

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

表5　路線A的配送路徑表

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

圖2　10家連鎖店配送優(yōu)化網(wǎng)絡圖

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

表6　車輛路徑優(yōu)化模型各項費用

5　結語

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

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

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

［3］劉琳.冷鏈物流配送路徑優(yōu)化模型及控制算法［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］繆小紅，周新年，林森，等.第三方冷鏈物流配送路徑優(yōu)化研究［J］.運籌與管理，2011，20（4）∶32-38.

［8］韓印，師攀.基于道路狀況的冷鏈物流配送路徑優(yōu)化［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］閔嘉寧，金成.基于改進節(jié)約算法的集送貨車輛路徑優(yōu)化［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-），女，山西太原人，碩士，副教授，碩士生導師，物流學院物流工程系主任，主要研究方向：生產(chǎn)物流系統(tǒng)規(guī)劃設計及裝備概念研發(fā)、商業(yè)物流系統(tǒng)規(guī)劃設計及裝備概念研發(fā)。