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

王　佳　池　潔　王　勇

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

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

中圖分類號(hào):U116.2文獻(xiàn)標(biāo)識(shí)碼: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)中一個(gè)重要的環(huán)節(jié),是物流節(jié)點(diǎn)送達(dá)收貨人的過(guò)程。滿足貨運(yùn)要求的前提下,如何選擇配送線路是非常重要的,線路優(yōu)化的目的在于保證運(yùn)輸安全的前提下,使配送線路和運(yùn)輸時(shí)間最優(yōu)。

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

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

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

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

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

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

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

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

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

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

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

fv,φ=p=7.30

當(dāng)K=1時(shí):

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時(shí):

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時(shí):

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

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

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

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

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

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

浮動(dòng)車法調(diào)查計(jì)算表如表2。

(1)先計(jì)算向南行情況

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

=×60=×60=19.02km/h

(2)再計(jì)算向北行情況

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

=×60=×60=18.44km/h

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

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

由v配送到v,v,v三個(gè)配送點(diǎn),并回到v,這條路線的時(shí)間最短為33.41min,最佳配送路徑為:

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

上述路線說(shuō)明,配送車按照上述路線行走,使得配送線路的配送時(shí)間最短。

4配送路線與配送時(shí)間類比

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

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

5結(jié)束語(yǔ)

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

參考文獻(xiàn):

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

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

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

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