物流中配送路線選擇的優化分析

王　佳　池　潔　王　勇

摘要:配送線路的正確選擇,有利于提高企業的服務質量,降低成本。通過實際調研,繪制城市道路的距離網絡圖,并通過交通工程中的浮動車法計算網絡圖的時間權值,繪制配送時間網絡圖。運用運籌學中的動態規劃算法分別計算配送路線及配送時間的最優線路,并比較說明相應的實際問題。

關鍵詞:浮動車法;網絡圖;動態規劃;最優線路

中圖分類號:U116.2文獻標識碼: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引言

物流配送是物流系統中一個重要的環節,是物流節點送達收貨人的過程。滿足貨運要求的前提下,如何選擇配送線路是非常重要的,線路優化的目的在于保證運輸安全的前提下,使配送線路和運輸時間最優。

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

1線路優化方法概述

假設某配送中心負責b個接貨點V=v,v,…,v,v為配送站,G=V,E,W由城市道路構成的網絡圖,V=V∪Yv,E,W分別表示城市道路構成得邊集,以及道路長度(或時間)構成的權集。

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

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

2實際中配送路線的線路優化

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

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

=v,v,v返回v,求最短環游路線及路徑。

解依據動態規劃方法原理,由邊界條件可知:

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

fv,φ=p=7.30

當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

當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

當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

由此,通過動態規劃的追溯方法得到由v出發配送貨物到v,v,v這三個配送點,并最終回到v出發點,這條路線的路程最短的最優路徑,即距離17.49km,這條路線為:

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

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

3實際中配送時間的線路優化

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

浮動車法調查計算表如表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,取平均值當作行程時間為4.55min。

3.2配送時間網絡圖的建立及計算。圖2中各節點與圖1中相同,同樣應用浮動車法求得了其他路段的行程時間,如圖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配送路線與配送時間類比

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

對于網絡優化問題,由路程和時間求得最佳路徑是不盡相同的。因此,在生活實踐中應綜合考慮時間及路程的最優問題,有利于提高車輛的利用率,降低運輸成本,使運輸效率達到最高。

5結束語

配送線路優化能有效提高企業的服務質量、降低成本,充分考慮時間和路程,效果更加明顯。因此,配送線路的優化研究對于發展城市的現代物流業和提高企業的核心競爭力具有重要的指導意義。

參考文獻:

[1] 池潔,李莉. 物流中配送區域與配送路線網絡優化法[J]. 運籌與管理,2003,12(2):123-126.

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

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

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