物流中配送路線選擇的優(yōu)化分析

王　佳　池　潔　王　勇

摘要:配送線路的正確選擇,有利于提高企業(yè)的服務(wù)質(zhì)量,降低成本。通過實際調(diào)研,繪制城市道路的距離網(wǎng)絡(luò)圖,并通過交通工程中的浮動車法計算網(wǎng)絡(luò)圖的時間權(quán)值,繪制配送時間網(wǎng)絡(luò)圖。運(yùn)用運(yùn)籌學(xué)中的動態(tài)規(guī)劃算法分別計算配送路線及配送時間的最優(yōu)線路,并比較說明相應(yīng)的實際問題。

關(guān)鍵詞:浮動車法;網(wǎng)絡(luò)圖;動態(tài)規(guī)劃;最優(yōu)線路

中圖分類號:U116.2文獻(xiàn)標(biāo)識碼:A

Abstract: The rightness of choosing distribution routes will be beneficial to enhance the service quality, and reduce the cost. Through practical research, mapping the urban road network graph, and through the floating vehicle method in traffic engineering to calculate the time right in the network, and mapping the distribution time network. Calculated optimal delivery time routes and deliver paths optimal routes by dynamic programming algorithm in operational research, and compared the corresponding practical problems.

Key words: floating vehicle method; network graph; dynamic programming; optimal routes

0引言

物流配送是物流系統(tǒng)中一個重要的環(huán)節(jié),是物流節(jié)點送達(dá)收貨人的過程。滿足貨運(yùn)要求的前提下,如何選擇配送線路是非常重要的,線路優(yōu)化的目的在于保證運(yùn)輸安全的前提下,使配送線路和運(yùn)輸時間最優(yōu)。

貨物配送的重點就是如何將車輛進(jìn)行有效利用,使得在配送時間和距離都相對最優(yōu)的情況下配送到客戶手中。由于規(guī)定了裝卸點位置,力求多裝快跑,節(jié)約時間和費用,提高效率,最經(jīng)濟(jì)就是兩點間最佳運(yùn)行路線。采用運(yùn)籌學(xué)方法統(tǒng)籌考慮配送路線和配送時間,尋求最經(jīng)濟(jì)運(yùn)行線路是非常必要的。本文應(yīng)用相應(yīng)算法并通過對濟(jì)南市區(qū)配送線路的調(diào)查,計算相應(yīng)的最佳配送線路,并進(jìn)行對比說明一定問題。

1線路優(yōu)化方法概述

假設(shè)某配送中心負(fù)責(zé)b個接貨點V=v,v,…,v,v為配送站,G=V,E,W由城市道路構(gòu)成的網(wǎng)絡(luò)圖,V=V∪Yv,E,W分別表示城市道路構(gòu)成得邊集,以及道路長度(或時間)構(gòu)成的權(quán)集。

這類問題可用動態(tài)規(guī)劃方法求解:第一步,將問題劃分為m個階段(階段數(shù)劃分根據(jù)接貨點數(shù)而定);第二步,狀態(tài)變量v,S,v∈V,v表示送貨車從v走到v,S表示到v之前所經(jīng)過的接貨點集合,SV;第三步,此處決策表示由一個接貨點v走到另一個接貨點v;第四步,最優(yōu)指標(biāo)函數(shù)fv,S=fvSv+pk=1,2,…,m,其中,Sv表示除i之外的接貨點,p表示v和v兩點間最短距離;邊界條件為fv,φ

=p, j=1,2,…,m。進(jìn)而求得來回且經(jīng)過要求的點,使得路程最短。

2實際中配送路線的線路優(yōu)化

現(xiàn)有批娛樂設(shè)備,打算由運(yùn)輸車從濟(jì)南長途汽車總站配送到大明湖、趵突泉和千佛山三個旅游景點,并回到長途汽車總站,試計算一條最短配送路線使得來回所走的路程最短。我們經(jīng)過實際測算得到圖1。

對圖1進(jìn)一步說明如下,v:長途汽車總站,v:三孔橋,v:天橋,v:人民商場,v:大明湖,v:趵突泉,v:省中醫(yī),v:青龍橋,v:千佛山。針對上述路線圖,求配送車從v(長途汽車總站)出發(fā)途經(jīng)V

=v,v,v返回v,求最短環(huán)游路線及路徑。

解依據(jù)動態(tài)規(guī)劃方法原理,由邊界條件可知:

fv,φ=p=3.95; fv,φ=p=4.22

fv,φ=p=7.30

當(dāng)K=1時:

fv,v=fv,φ+p=4.22+3.16=7.38

fv,v=fv,φ+p=7.30+6.24=13.54

fv,v=fv,φ+p=3.95+3.16=7.11

fv,v=fv,φ+p=7.30+3.08=10.38

fv,v=fv,φ+p=3.95+6.24=10.19; fv,v=fv,φ+p=4.22+3.08=7.30

當(dāng)K=2時:

fv,v,v=minfv,v+p, fv,v+p=min10.38+3.16, 7.30+6.24=13.54

fv,v,v=minfv,v+p, fv,v+p=min13.54+3.16, 10.19+3.08=13.27

fv,v,v=minfv,v+p, fv,v+p=min7.38+6.24, 7.11+3.08=10.19

當(dāng)K=3時:

fv,v,v,v=minfv,v,v+p, fv,v,v+p, fv,v,v+p

=min13.54+3.95, 13.27+4.22, 10.19+7.30=17.49

由此,通過動態(tài)規(guī)劃的追溯方法得到由v出發(fā)配送貨物到v,v,v這三個配送點,并最終回到v出發(fā)點,這條路線的路程最短的最優(yōu)路徑,即距離17.49km,這條路線為:

v→v→v→v→v→v→v→v→v→v或v→v→v→v→v→v→v→v→v→v

上述路線說明,配送車按照上述路線行走,使得配送線路的路程最短。

3實際中配送時間的線路優(yōu)化

3.1配送時間調(diào)查表的繪制及計算。對于上述線路圖1,通過浮動車法并應(yīng)用相應(yīng)公式計算各段路程時間。首先對長途車站到天橋間距離l為1.42km的線路進(jìn)行調(diào)查,并繪制調(diào)查記錄表,表1中各列含義為:T:出發(fā)時間,t:行程時間,X:迎面駛來的車輛數(shù),Y:超越測試車的車輛數(shù),Y:測試車超越的車輛數(shù),Y:超越測試車車輛數(shù)與測試車超越車輛數(shù)之差,且表中序號1～6表示測試車向南行駛,序號1′～6′表示測試車向北行駛。調(diào)查表如表1。

浮動車法調(diào)查計算表如表2。

(1)先計算向南行情況

q===19.78輛/min=1 187輛/h;=t-=4.56-=4.56-0.08=4.48min

=×60=×60=19.02km/h

(2)再計算向北行情況

q===20.33輛/min=1 220輛/h;=t-=4.62-=4.62min

=×60=×60=18.44km/h

計算由長途車站到天橋時間為4.48min,而返回的時間為4.62min,取平均值當(dāng)作行程時間為4.55min。

3.2配送時間網(wǎng)絡(luò)圖的建立及計算。圖2中各節(jié)點與圖1中相同,同樣應(yīng)用浮動車法求得了其他路段的行程時間,如圖2所示。

由v配送到v,v,v三個配送點,并回到v,這條路線的時間最短為33.41min,最佳配送路徑為:

v→v→v→v→v→v→v→v或v→v→v→v→v→v→v→v

上述路線說明,配送車按照上述路線行走,使得配送線路的配送時間最短。

4配送路線與配送時間類比

經(jīng)計算得知若按最短距離行走,路線長度為17.49km,但花費的時間是64.65min。而按最短時間為33.41min行走的路線長度為23.41km,顯而易見,如果按最短距離行走,雖然距離比按最短時間行走少了5.92km,但時間卻多花費了31.24min,時間也是效益,節(jié)省時間也相當(dāng)于節(jié)約成本,完全可以利用多花費的時間去再配送一趟物品,這樣雖然多跑了路線,但卻大大提高了車輛的利用率,節(jié)約了配送成本。

對于網(wǎng)絡(luò)優(yōu)化問題,由路程和時間求得最佳路徑是不盡相同的。因此,在生活實踐中應(yīng)綜合考慮時間及路程的最優(yōu)問題,有利于提高車輛的利用率,降低運(yùn)輸成本,使運(yùn)輸效率達(dá)到最高。

5結(jié)束語

配送線路優(yōu)化能有效提高企業(yè)的服務(wù)質(zhì)量、降低成本,充分考慮時間和路程,效果更加明顯。因此,配送線路的優(yōu)化研究對于發(fā)展城市的現(xiàn)代物流業(yè)和提高企業(yè)的核心競爭力具有重要的指導(dǎo)意義。

參考文獻(xiàn):

[1] 池潔,李莉. 物流中配送區(qū)域與配送路線網(wǎng)絡(luò)優(yōu)化法[J]. 運(yùn)籌與管理,2003,12(2):123-126.

[2] 王煒,過秀成. 交通工程學(xué)[M]. 江蘇:東南大學(xué)出版社,2000:23-43.

[3] 陳子俠. 城市卷煙配送線路的網(wǎng)格劃分算法[J]. 上海交通大學(xué)學(xué)報,2003(7):1013-1017.

[4] 曹二保,賴明勇,聶凱,等. 大規(guī)模物流配送車輛調(diào)度問題研究[J]. 湖南大學(xué)學(xué)報,2007,34(12):89-92.