基于中國郵路問題的配送線路規劃

王林琳 鮑 進

摘要:煙草配送到戶的特點是停留點分布分散,配送車輛需穿行于城市的每一條街道,與郵遞員的工作特點非常相似。以運籌學上的中國郵路問題為模型,對某煙草配送公司的配送線路進行規劃,用定量的方法提高行駛路線的精確性和標準化程度,爭取以更少的車輛、人力和里程數完成更大的服務量。

關鍵詞:煙草配送;線路規劃;中國郵路問題模型;歐拉回路

中圖分類號:U116.2文獻標識碼:A

Abstract: The characteristic of tobacco distribution is that customers are everywhere, and delivery vehicles are through in every street of the city. It is very similar with the work of postman. Based on chinese postman problem, we have researched into the route programming of a tobacco distribution company in order to improve the accuracy and standardization of the routing with quantitative methods and complete more services with less manpower and mileage.

Key words: tobacco distribution; route planning; Chinese post problem model; euler circuit

0引言

中國郵路問題是我國管梅谷教授于1962年首先研究的,可以總結為:一個郵遞員每次送信,從郵局出發,必須至少依次經過他負責投遞范圍的每一條街道,待完成任務后仍然回到郵局,問他如何選擇投遞路線,從而使自己所走的路程最短[1-2]?

本案例中的煙草配送公司負責濟南市5個區(含郊區)及濟南市所轄5縣市的卷煙配送工作,包括大型超市、便利店、酒店、零售攤點等各種類型客戶。公司的配送原則是配送到戶,這些停留點的分布相當分散,遍布于城市的每個角落。配送車輛穿行于城市的每一條街道,將每一條香煙送到客戶手中,由此聯想到了郵遞員的工作。因此,選擇運籌學上的中國郵路問題來建立模型,進行路線的規劃。另外,這種方法比較簡便易懂,也容易為司機所接受。

本案例主要針對該公司配送四部的工作情況進行分析,對其配送路線進行重新規劃,從而達到以更少的車輛、人力和里程數,完成更大的服務量的目的。

1配送四部的情況簡介

配送四部目前備有5輛金杯車,5名司機和5名配送人員,其所負責的客戶主要分布在歷下區和歷城區的市區部分,北面到大明湖北路,南至市中區的土屋路,西起順河高架橋,東至姚家莊,如圖1所示。

6種顏色代表一周6個工作日每天的工作范圍;每個范圍里又劃分10個小區域,5輛車每天分別負責2個小區的配送工作。

目前,該公司的線路規劃已進入第三期工程,在統籌調度上已趨于合理化,但通過調研仍是發現了幾點問題,如整體分區的形狀不夠標準化,不同部門的車輛甚至會出現重復線路的情況;某些小區域上的具體行駛路線沒有進行定性定量的規劃,仍是司機憑經驗拍腦袋決定,這就有可能造成不必要的行駛浪費。

2路徑優化的總體思路

為了解決上述問題,結合線路規劃過程中的一些制約因素以及公司的實際情況,我們提出了路徑優化的總體思路如下:

2.1初步確定每輛車每天的平均配送戶數

通過這個約數限制出路徑規劃的大致范圍,即一輛車一天所能配送的最大范圍。表1是配送四部5輛車一周6個工作日每天配送的客戶數量統計表。

由表1可以看出每輛車的服務戶數彈性很大,最小值為45戶,最大值亦可以達到78戶,因此我們姑且假設優化后每輛車每天的平均配送戶數達到最大值78戶。后期通過模型驗證是否能夠達到該數值。

另外,在實際的配送過程中,每個攤點并不一定每星期都訂貨,也就是說,某天配送的小區內會有個別攤點不在配送范圍內,不做停留。

2.2郵路問題模型的建立

運用中國郵路問題的模型,對行駛路徑進行全面規劃。本案例截取和平路和文化路之間的一段區域,該區域原本是由四部的1號車用一周6個工作日完成配送任務。采用郵路問題建模對行駛路徑進行規劃,從行駛里程數和工作時間兩方面比較規劃前后的差別。

圖2為和平路和文化路之間的燕子山小區的電子地圖,藍點為統計獲得的配送停留點的標記。以該小區為例說明如何借助郵路模型來進行規劃。

郵路問題的基本原理是每條邊上最多重復一次;在圖中每個回路上,有重復的邊的長度不超過回路總長的一半。分兩步來完成:

Step1:確定一個連通圖G

圖3是抽象出來的該小區的幾條街道的示意圖。數字表示街道的長度,由濟南電子地圖上采集,取其約數,單位為公里。紅星為選擇的車輛出入口。

連通圖是指一個圖中每一對頂點之間至少存在一條鏈;鏈的概念是圖中點、邊連續交替序列,頂點可重復,邊不重復。為了使截取的路徑滿足上述要求,需進行第二步。

Step2:求出歐拉回路

歐拉回路是指連通圖G中,若存在一條回路,經過每邊一次且僅一次。很顯然,在圖中若要遍歷所有街道,經過每邊僅一次不可能達到要求,因此要構建重復走的路徑。方法如下:

(1)找出圖中的奇點,并兩兩相連;奇點是指次為奇數的點。任何圖中奇點的個數都為偶數個。其中次是指端點的邊的個數稱為該點的次;

(2)連接兩奇點的虛線長度不超過回路總長的一半。

如圖4所示,“×”表示奇點;虛線代表重復走的路徑;括號里的數字表示給每一小段街道排上的序號,方便后面走法的表示。它與圖3中的里程數是一一對應的。

從紅星處進入,遍歷所有街道從紅星處返回。走法不唯一,只要滿足上述方法的要求即可,最終確定的一種走法為:(1)—(2)—(3)—(4)—(4)—(5)—(2)—(6)總里程數為3.87公里。其余地區的配送路線以此類推,分別算出行駛里程數。

2.3模型數據整理

上述計算完成后統計行駛里程數,進而換算出配送時間,找出節約量,從而對每天的配送戶數做進一步的調整。

這里要提到兩個概念,配送里程數和輔助里程數。配送里程數是指從到達配送區域開始至走出配送區域為止的距離,也就是我們歐拉回路的總長。輔助里程數是指從公司到配送區域和從配送區域返回公司的這兩段空程的距離。

和平路和文化路兩條主干道之間原本是1輛車6天的工作量,由于每天配送戶數的增加,工作時間減少為4天,其行駛里程數如表2所示。

正常行駛的平均速度為30km/h,在配送的過程中行駛的平均速度約為2km/h,由此可以計算出配送與來回空程的時間。

如:第一天配送時間:8.16/2=4.08h輔助時間:20.49/30=0.68h

匯總后4天的行駛時間如表3所示。從中可見,該條線路每天的工作時間除第4天外,都不夠8小時?？紤]到私事寬放以及每天從倉庫發貨的時間,仍有很大的挖掘潛力。

若繼續增加每天的配送戶數,調整各天配送任務的路線,有望將總天數減為3天,節省了一半的工作時間。

進行線路規劃時,并不是所有的街道都適合建立郵路模型,有時建立模型反而增加了行車路線的復雜度,應根據實際情況靈活解決。另外,在做到局部優化的時候還要考慮到一些約束條件,如:避免將主干道劃入連通圖,主干道上保持右轉彎;盡量避免跨街送貨或者逆向行駛,降低司機和貨車的行駛風險等[3]。

3結束語

本文針對煙草配送的特點選擇了中國郵路問題作為模型,對其配送線路進行規劃。規劃后,配送四部的車輛由原來的5輛縮減為3輛,工作時間由原來的6天縮減為5天。采用該方法最重要的一點是簡單易行,在項目報告會上引起中層領導的興趣,在跟司機的溝通中阻力不大,具有一定的實用價值。

參考文獻:

[1] 胡運權. 運籌學基礎及應用[M]. 哈爾濱:哈爾濱工業出版社,2002.

[2] 趙剛. 物流運籌[M]. 成都:四川人民出版社,2002.

[3] 陳志紅. 運輸組織技術[M]. 北京:人民交通出版社,2003.