基于節(jié)約里程法結(jié)合時(shí)間窗約束的物流配送線路優(yōu)化合肥

1、基于節(jié)約算法結(jié)合時(shí)間約束的物流配送線路優(yōu)化基于節(jié)約算法結(jié)合時(shí)間約束的物流配送線路優(yōu)化合肥綠和農(nóng)業(yè)生鮮品配送線路的優(yōu)化目錄背景及綠和農(nóng)業(yè)概況01合肥綠和農(nóng)業(yè)生鮮品配送線路存在的問(wèn)題02VRP優(yōu)化策略03結(jié)論與展望04背景及綠和農(nóng)業(yè)概況11.1 背景 近年來(lái)隨著物流業(yè)的快速發(fā)展，物流企業(yè)為了能夠在激烈的市場(chǎng)競(jìng)爭(zhēng)中保持優(yōu)勢(shì)地位，都在想方設(shè)法降低物流配送成本，提高自身競(jìng)爭(zhēng)力。如何規(guī)劃配送路線，減少不必要的人員、時(shí)間和金錢的浪費(fèi)，使運(yùn)輸成本降到最低是一個(gè)有待解決的科學(xué)問(wèn)題，而基于各種算法研究車輛路徑規(guī)劃問(wèn)題( Vehicle Routing Problem)是目前比較常見(jiàn)的思路。 當(dāng)前，效率低下的生鮮物

2、流已成為阻止我國(guó)果蔬商品生產(chǎn)和流通產(chǎn)業(yè)化發(fā)展的瓶頸。為突破這一瓶頸，研究生鮮物資的物流配送問(wèn)題已迫在眉睫。配送車輛路徑問(wèn)題是一個(gè)NP-hard問(wèn)題。1.2 綠和農(nóng)業(yè)概況 安徽綠和農(nóng)業(yè)科技有限公司坐落在安徽省最大的農(nóng)產(chǎn)品批發(fā)市場(chǎng)周谷堆農(nóng)產(chǎn)品批發(fā)市場(chǎng)旁。公司專業(yè)從事蔬菜種植、禽畜養(yǎng)殖和為酒店、工廠、學(xué)校、企事業(yè)單位、政府機(jī)關(guān)食堂、生鮮超市等進(jìn)行新鮮蔬菜、水果、肉類、糧油等農(nóng)副產(chǎn)品一站式配送服務(wù)。 綠和農(nóng)業(yè)將以特有的新鮮、安全、快速、高效的優(yōu)勢(shì)，合理的價(jià)格，取得廣大企業(yè)用戶的青睞。在我們的服務(wù)領(lǐng)域，我們的專業(yè)程度、技術(shù)服務(wù)水平、衛(wèi)生監(jiān)督、產(chǎn)品質(zhì)量以及先進(jìn)的服務(wù)理念已經(jīng)得到客戶的充分認(rèn)可，從而保障我們

3、與客戶保持長(zhǎng)期友好的合作關(guān)系。 宗旨：公司的宗旨是第一時(shí)間產(chǎn)地直供、減少中間環(huán)節(jié)，為客戶創(chuàng)造價(jià)值。我們替您買菜，當(dāng)天配送，我們只做蔬菜的搬運(yùn)工。讓消費(fèi)者買菜不用再去菜市場(chǎng)挑挑揀揀，只要在家做等“收菜”即可。讓消費(fèi)者足不出戶就能品嘗到新鮮、健康、營(yíng)養(yǎng)的蔬菜。 配送優(yōu)勢(shì)：農(nóng)產(chǎn)品物流是以農(nóng)業(yè)產(chǎn)出物為對(duì)象,通過(guò)農(nóng)產(chǎn)品產(chǎn)后加工、包裝、儲(chǔ)存、運(yùn)輸和配送等物流環(huán)節(jié),做到農(nóng)產(chǎn)品保值增值,最終送到消費(fèi)者手中。由于農(nóng)產(chǎn)品本身特 質(zhì),以及產(chǎn)銷地域廣闊分散的特點(diǎn)，對(duì)農(nóng)產(chǎn)品物流規(guī)劃、方式和手段提出了比較高的要求,這個(gè)物流過(guò)程是目前農(nóng)產(chǎn)品實(shí)現(xiàn)市場(chǎng)價(jià)值的關(guān)鍵環(huán)節(jié)。作為現(xiàn)代物流的新業(yè)態(tài)，農(nóng)產(chǎn)品物流統(tǒng)一組織貨源,進(jìn)行檢驗(yàn)檢疫、

4、整理清洗、分檢包裝,根據(jù)定單要求直接送到消費(fèi)者手中，完成農(nóng)產(chǎn)品從“田間”到“餐桌”的全程服務(wù)，具有安全、高效、便利的特點(diǎn)。 合 肥 綠 和 農(nóng) 業(yè) 生 鮮 品 配 送 路 線 存 在 的 問(wèn) 題合 肥 綠 和 農(nóng) 業(yè) 生 鮮 品 配 送 路 線 存 在 的 問(wèn) 題22.1 生鮮品配送線路現(xiàn)狀 生鮮配送線路缺乏規(guī)劃，效率較低 合肥綠和農(nóng)業(yè)生鮮配送幾十家門店，本著追求高效配送效率和最低配送成本的原則出發(fā)，以合肥政務(wù)區(qū)大區(qū)為配送區(qū)塊作業(yè)，每日凌晨按照前一日超市的銷售反饋，裝配好生鮮品，在凌晨5:00-8:00時(shí)段內(nèi)送到各門店。各門店分布在合肥政務(wù)區(qū)城市的角角落落，主要都圍繞一些居民區(qū)而建，路況復(fù)雜多

5、變。 綠和農(nóng)業(yè)配送中心安排車輛送貨時(shí)，考慮了車輛載貨的核定重量以及門店分布得區(qū)域，因此常由一輛車輛負(fù)責(zé)某一區(qū)域的門店生鮮配送。門店配送的先后由配送中心事先制訂好，但是其制定的方法是以配送中心出發(fā)后最近的門店開(kāi)始配送，而后配送距離上一家最近的門店，直至最后配送完一家門店返回配送中心。因冷藏車的送貨路線合理性有限，冷藏車到達(dá)門店后，很容易與其他送貨車輛發(fā)生沖突，互相干擾貨物進(jìn)出路徑和搬運(yùn)優(yōu)先次序等。這樣的局面常常造成冷藏車用較長(zhǎng)時(shí)間滯留在一家門店等待卸貨的情況，既浪費(fèi)寶貴的生鮮貨物配送時(shí)間，又極大的浪費(fèi)了運(yùn)輸設(shè)備的效能。部分司機(jī)為了和其他送貨車輛爭(zhēng)搶卸貨時(shí)間，甚至還提前將生鮮品卸貨至門店貨倉(cāng)門口，

6、等待門店工作人員收貨，造成生鮮品長(zhǎng)時(shí)間暴露在外，大大降低了生鮮品的品質(zhì)。2.2 現(xiàn)有的配送方案分析 由于合肥綠和農(nóng)業(yè)旗下的門店有很多，本文選取位于合肥政務(wù)區(qū)市天鵝湖的10家門店進(jìn)行研究。 合肥政務(wù)區(qū)市天鵝湖綠和農(nóng)業(yè)生鮮品配送中心與門店之間的距離門店P(guān)0天鵝湖店懷寧路店?yáng)|流路店翡翠路店聚云路店南二環(huán)路店高河西路店潛山路店休寧路店祁門路店P(guān)00106811710117811天鵝湖店100824866662懷寧路店680612410124412東流路店826084610648翡翠路店11412808241082聚云路店784480810448南二環(huán)路店1061062806844高河西路店116121

7、0410601082潛山路店76461048100210休寧路店86448448208祁門路店11212828421080 合肥政務(wù)區(qū)市天鵝湖綠和農(nóng)業(yè)門店的貨物需求量及時(shí)間窗 按當(dāng)前合肥政務(wù)區(qū)華潤(rùn)配送規(guī)劃的原則，即以最為靠近配送中心的門店開(kāi)始送貨，以下門店距離一門店最近來(lái)進(jìn)行下一門店的送貨，直至送完為止回到配送中心，這10家店目前的配送情況如下: 配送路線為:P。配送中心懷寧路店聚云路店潛山路店休寧路店一東流路店天鵝湖店南二環(huán)路店翡翠路店祁門路店一一高河西路店P(guān)。配送中心 配送里程:6+4+4+2+4+2+6+2+2+2+11=45公里 從配送里程來(lái)看，配送路線規(guī)劃總體比較短，但是由于路線規(guī)劃

8、時(shí)沒(méi)有考慮到門店的時(shí)窗要求，因此車輛到達(dá)門店時(shí)往往需要等待比較長(zhǎng)的時(shí)間才能卸貨，因此車輛在門店的停留的時(shí)間平均長(zhǎng)達(dá)26分鐘。由于配送時(shí)間的增加，還導(dǎo)致制冷成本隨之上升。所以需要一定的路線優(yōu)化使總成本達(dá)到最低。門店翡翠路店懷寧路店?yáng)|流路店潛山路店聚云路店南二環(huán)路店高河西路店休寧路店天鵝湖店祁門路店需求量（噸）0.080.10.120.050.080.150.060.050.10.02門店要求的時(shí)間5：45-6:306:10-7:005:45-6:156:50-7:505:40-6:357:25-8:006:30-7:107:15-8:005:20-5:406:40-7:20門店可接受的時(shí)間5:4

9、0-6:456:00-7:005:30-6:156:40-7:505:30-6:357：10-8：106:30-7:107:00-8:005:00-5:406:35-7：30 VRP優(yōu)化策略33.1 VRP 求解的方法 綜合過(guò)去有關(guān)車輛路線問(wèn)題的求解方法，可以分為精確算法(exact algorithm)與啟發(fā)式解法(heuristics) (1)精確算法 精確算法一般會(huì)隨著問(wèn)題規(guī)模的增大而呈現(xiàn)數(shù)據(jù)量增大的情況，計(jì)算成本比較大，因此很難有效解決大規(guī)模的VRP問(wèn)題，實(shí)際應(yīng)用范圍有限。（2)啟發(fā)式算法 由于VRP是NP-hard問(wèn)題，這類問(wèn)題的大型實(shí)例很難以用精確算發(fā)求解，多年來(lái)很多專家對(duì)此類車輛

10、運(yùn)輸問(wèn)題進(jìn)行了研究，提出了各種各樣的啟發(fā)式方法。啟發(fā)式算法包括構(gòu)造算法蟻群算法遺傳算法節(jié)約里程法 節(jié)約里程法基本原理是幾何學(xué)中三角形一邊之長(zhǎng)必定小于另外兩邊之和。設(shè)為配送中心，分別向用戶a和b送貨。我們用a和b之間的距離為lab，送貨方案只有兩種即配送中心向用戶a, b分別送貨和配送。比較兩種配送方案: 方案1:配送路線為 ，配送距離為 方案2:配送路線 ，配送距離為 我們用 表示節(jié)約里程數(shù)，即方案2比法案1節(jié)約的配送里程: 根據(jù)節(jié)約法的基本思想，如果一個(gè)配送中心P。分別向m個(gè)客戶配送貨物，在汽車載重能力允許的前提下，每輛汽車的配送線路上經(jīng)過(guò)的客戶個(gè)數(shù)越多，里程節(jié)約量越大，配送線路越合理。00

11、0pbpapball2200pbapabballlabbaablllyaby 節(jié)約里程法運(yùn)算速度較快，特別是在小規(guī)模的配送路徑優(yōu)化問(wèn)題中，節(jié)約里程法的優(yōu)化解與最優(yōu)解更加接近，其在實(shí)際應(yīng)用中也能得到較滿意的結(jié)果，合肥綠和農(nóng)業(yè)對(duì)超市配送規(guī)模較小，所以本文將以節(jié)約里程法對(duì)綠和農(nóng)業(yè)配送車輛路徑進(jìn)行優(yōu)化。3.2有時(shí)間窗約束的VRP 時(shí)間約束問(wèn)題大體分為兩種，一種是“允許延時(shí)”的“軟時(shí)間窗”問(wèn)題，一種是“不允許延時(shí)”的“硬時(shí)間窗”問(wèn)題。在建立懲罰成本模型時(shí)，設(shè)門店a可接受的時(shí)間窗Ma , Na ，門店要求的時(shí)間窗ma, na。根據(jù)配送車輛到達(dá)門店的時(shí)間，可以分三種情況:配送車輛在門店要求的時(shí)間之前到達(dá)。（

12、在Ma，ma)內(nèi)到達(dá)，在Ma之前到達(dá)）配送車輛在門店要求的時(shí)間內(nèi)到達(dá)（在ma, na內(nèi)到達(dá)，無(wú)懲罰成本）配送車輛在門店要求的時(shí)間后到達(dá)（在(na,Na內(nèi)到達(dá)，在Na之后到達(dá)）綜上所述，懲罰函數(shù)可以表示為aaaaabaaaaaaabaaaaaMXmXMaPqXmnXmNXaPqnXNXXP,)(,0n,)(,)(a式中Xa是生鮮品送達(dá)門店的時(shí)間; a和是懲罰系數(shù); P(Xa)是懲罰成本; P是生鮮單位價(jià)值; qb是每個(gè)門店生鮮需求量。3.3綠和農(nóng)業(yè)生鮮品配送中心車輛路徑優(yōu)化方案 3.3.1車輛路徑問(wèn)題模型建立(1)模型建立的約束條件門店的數(shù)量固定且位置己知;門店的生鮮品需求量一定;生鮮品送達(dá)時(shí)間

13、窗一定;每輛車的行駛時(shí)間不得超過(guò)司機(jī)工作的時(shí)間;每家門店且只能由一輛車一次性完成送貨;每條配送線路各門店的需求量之和不得超過(guò)車輛的最大核載量。車輛由配送中心出發(fā)，有序到達(dá)各門店后返回配送中心。 (2)軟時(shí)間窗約束下的模型建立 運(yùn)輸成本 生鮮品的制冷成本 綜上所述，我們構(gòu)建的生鮮品配送車輛路徑問(wèn)題的目標(biāo)函數(shù)： ababhabhlCXcmambnh111 mambnhbzbhabzbhbhTqcttcXc11121)(abhabhXpccMinz 利用節(jié)約里程法結(jié)合時(shí)間窗約束，我們將帶有時(shí)間窗約束的合肥綠和農(nóng)業(yè)VRP求解步驟歸納如下: 第一步，將門店按時(shí)間窗先后順序排序; 第二步，計(jì)算配送中心到各

14、門店的節(jié)約里程數(shù); 第三步，從配送中心發(fā)車，首先將時(shí)間窗要求最早的門店作為第一個(gè)配送對(duì)象，然后將節(jié)約總成本最大的門店加入路線，成為第二個(gè)配送對(duì)象; 第四步，重復(fù)第三步，直至所有的門店都被排入路線內(nèi)。 帶有時(shí)間窗約束的合肥綠和農(nóng)業(yè)VRP具體求解過(guò)程如下: 第一，根據(jù)門店要求的時(shí)間進(jìn)行先后排序 第二，利用式 計(jì)算各門店間的節(jié)約里程數(shù)。abbaabllly天鵝湖店懷寧路店?yáng)|流路店翡翠路店聚云路店南二環(huán)路店高河西店潛山路店休寧路店祁門路店需求量（噸）0.10.080.120.080.10.060.020.050.050.15門店要求的時(shí)間5:20-5:405:40-6:355:45-6：155:45-

15、6:306:10-7:006:30-7:106:40-7:206:50-7:507:15-8:007:25-8:00門店可接受的時(shí)間5:00-5:405:30-6:355:30-6:155:40-6:456：00-7:006:30-7:106:35-7:306:40-7:507:00-8:007:10-8:10 合肥政務(wù)區(qū)市天鵝湖綠和農(nóng)業(yè)門店間的節(jié)約里程數(shù)門店天鵝湖店懷寧路店?yáng)|流路店翡翠路店聚云路店南二環(huán)路店高河西路店潛山路店休寧路店祁門路店天鵝湖店0 8161791415111219懷寧路店80859657105東流路店1680111112991211翡翠路店1751101019188112

16、0聚云路店991110098101110南二環(huán)路店1461219901591417高河西路店155918815081120潛山路店1179810980138休寧路店1210121111141113011祁門路店19511201017208110 第三，由于天鵝湖路店要求的時(shí)間最早，因此以天鵝湖路店作為第一個(gè)配送點(diǎn)，配送車輛到達(dá)的時(shí)間為5:30，接下來(lái)的門店選擇 最終的配送路線為Po配送中心天鵝湖路店?yáng)|流路店一休寧路店聚云路店懷寧路店高河西路店祁門路店南二環(huán)路店一-翡翠路店潛山路店-P。配送中心 配送里程:8+4+2+8+4+12+2+4+2+10+7=63公里 配送時(shí)間:63公里40公里/小時(shí)

17、+10分鐘10603.2小時(shí) 運(yùn)輸成本:63公里0.7元/公里=44.1元 制冷成本:3.2小時(shí)12元/小時(shí)+202.5元/噸0.81=55.7元 懲罰成本:0 配送總成本:44.1+55.7=99.8元按照優(yōu)化前的路線計(jì)算的話 配送時(shí)間:45公里40公里/小時(shí)+26分鐘1060=5.5小時(shí) 運(yùn)輸成本:45公里0.7元/公里=31.5元 制冷成本:5.5小時(shí)12元/小時(shí)+202.5元/噸0.81=106.5元配送總成本:31.5+106.5=138元配送路徑優(yōu)化前后數(shù)值比較 因此，與合肥綠和農(nóng)業(yè)生鮮配送中心當(dāng)前的配送路線相比較，配送總成本節(jié)約了138-99.8=38.2元。數(shù)值當(dāng)前配送路徑優(yōu)化

18、后配送路徑配送里程（公里）4563配送時(shí)間（小時(shí)）5.53.2運(yùn)輸成本（元）31.544.1制冷成本（元）106.555.7懲罰成本（元）不計(jì)0配送成本（元）13899.84.結(jié)論與展望 近年來(lái)，人們對(duì)物流配送路徑的研究逐步深入。同時(shí)生鮮品行業(yè)發(fā)展不但重視冷鏈物流中的各個(gè)環(huán)節(jié)控制，也開(kāi)始重視各節(jié)點(diǎn)的協(xié)調(diào)與合作，盡可能作到冷鏈物流無(wú)縫鏈接。通過(guò)對(duì)生鮮品配送特點(diǎn)的認(rèn)識(shí)，構(gòu)建了包含運(yùn)輸成本、制冷成本和懲罰成本的線路模型，并采用節(jié)約算法，對(duì)該模型進(jìn)行了優(yōu)化，以期在最大化節(jié)約成本和時(shí)間窗約束的條件下，確定合適的配送線路;最終通過(guò)相應(yīng)實(shí)例，證明了該配送線路優(yōu)化模型的有效性。本文中的優(yōu)化措施因?yàn)榇嬖诩僭O(shè)，所

19、以需要合肥綠和農(nóng)業(yè)連鎖超市在實(shí)際操作過(guò)程中進(jìn)行一些調(diào)整。通過(guò)優(yōu)化之后來(lái)使運(yùn)輸成本降低。1.2 綠和農(nóng)業(yè)概況 安徽綠和農(nóng)業(yè)科技有限公司坐落在安徽省最大的農(nóng)產(chǎn)品批發(fā)市場(chǎng)周谷堆農(nóng)產(chǎn)品批發(fā)市場(chǎng)旁。公司專業(yè)從事蔬菜種植、禽畜養(yǎng)殖和為酒店、工廠、學(xué)校、企事業(yè)單位、政府機(jī)關(guān)食堂、生鮮超市等進(jìn)行新鮮蔬菜、水果、肉類、糧油等農(nóng)副產(chǎn)品一站式配送服務(wù)。 綠和農(nóng)業(yè)將以特有的新鮮、安全、快速、高效的優(yōu)勢(shì)，合理的價(jià)格，取得廣大企業(yè)用戶的青睞。在我們的服務(wù)領(lǐng)域，我們的專業(yè)程度、技術(shù)服務(wù)水平、衛(wèi)生監(jiān)督、產(chǎn)品質(zhì)量以及先進(jìn)的服務(wù)理念已經(jīng)得到客戶的充分認(rèn)可，從而保障我們與客戶保持長(zhǎng)期友好的合作關(guān)系。 節(jié)約里程法運(yùn)算速度較快，特別是

20、在小規(guī)模的配送路徑優(yōu)化問(wèn)題中，節(jié)約里程法的優(yōu)化解與最優(yōu)解更加接近，其在實(shí)際應(yīng)用中也能得到較滿意的結(jié)果，合肥綠和農(nóng)業(yè)對(duì)超市配送規(guī)模較小，所以本文將以節(jié)約里程法對(duì)綠和農(nóng)業(yè)配送車輛路徑進(jìn)行優(yōu)化。 節(jié)約里程法運(yùn)算速度較快，特別是在小規(guī)模的配送路徑優(yōu)化問(wèn)題中，節(jié)約里程法的優(yōu)化解與最優(yōu)解更加接近，其在實(shí)際應(yīng)用中也能得到較滿意的結(jié)果，合肥綠和農(nóng)業(yè)對(duì)超市配送規(guī)模較小，所以本文將以節(jié)約里程法對(duì)綠和農(nóng)業(yè)配送車輛路徑進(jìn)行優(yōu)化。 帶有時(shí)間窗約束的合肥綠和農(nóng)業(yè)VRP具體求解過(guò)程如下: 第一，根據(jù)門店要求的時(shí)間進(jìn)行先后排序 第二，利用式 計(jì)算各門店間的節(jié)約里程數(shù)。abbaabllly天鵝湖店懷寧路店?yáng)|流路店翡翠路店聚云路店南二環(huán)路店高河西店潛山路店休寧路店祁門路店需求量（噸）0.10.080.120.080.10.060.020.050.050.15門店要求的時(shí)間5:20-5:405:40-6:355:45-6：155:45-6:306:10-7:006:30-7:106:4