物流系統(tǒng)工程課件第十四講運輸

利用售貨員通過流動卡車銷售啤酒和其它飲料,卡車由當(dāng)?shù)亟?jīng)銷人員所有不希望每天向各客戶提供服務(wù)時花費不必要的時間，行走多余的路程。他們將圖釘固定在地圖上，以確定某推銷員現(xiàn)有客戶的位置。下圖所舉的是一個20個客戶的例子，客戶點的信息已經(jīng)被轉(zhuǎn)換到網(wǎng)絡(luò)地圖上，圖中的坐標(biāo)與距離相關(guān)。我們要找出的是，卡車從倉庫出發(fā)，經(jīng)過所有的客戶點，再回到倉庫，這個運行過程中距離最短的路徑。可以采用感知法求解最短路徑。

例子2物流系統(tǒng)工程課件第十四講運輸X坐標(biāo)飲料客戶和倉庫所在位置的網(wǎng)絡(luò)圖D876543210012345678Y坐標(biāo)3物流系統(tǒng)工程課件第十四講運輸X坐標(biāo)a)飲料客戶和倉庫所在位置的網(wǎng)絡(luò)圖Y坐標(biāo)D876543210012345678X坐標(biāo)b)建議的路徑Y(jié)坐標(biāo)D8765432100123456784物流系統(tǒng)工程課件第十四講運輸內(nèi)容：合理路線和時期表的制定原則行車路線和時刻表的制定方法運輸路線的安排思考題：

你將采取什么措施幫助卡車調(diào)度員接受和使用本章介紹的行車路線和時刻表制定方法?6.4行車路線和時刻表的制定5物流系統(tǒng)工程課件第十四講運輸6.4.1合理路線和時期表的制定原則運用八條原則，經(jīng)過一番周折，決策者(如車輛調(diào)度員)可以制定出合理行車路線和時刻表。這八條原則簡述如下：（1）安排車輛負(fù)責(zé)相互距離最接近的站點的貨物運輸?？ㄜ嚨男熊嚶肪€圍繞相互靠近的站點群進(jìn)行計劃，以使站點之間的行車時間最短。圖6-8a表示的是安排車輛裝運時應(yīng)避免的劃分方式，圖6-8b表示的則是比較合理劃分方式。6物流系統(tǒng)工程課件第十四講運輸（2）安排車輛各日途經(jīng)的站點時，應(yīng)注意使站點群更加緊湊（3）從距倉庫最遠(yuǎn)的站點開始設(shè)計路線（4）卡車的行車路線應(yīng)呈水滴狀（5）盡可能使用最大的車輛進(jìn)行運送，這樣設(shè)計出的路線是最有效的（6）取貨、送貨應(yīng)該混合安排，不應(yīng)該在完成全部送貨任務(wù)之后再取貨。（7）對過于遙遠(yuǎn)而無法歸入群落的站點，可以采用其它配送方式（8）避免時間窗口過短這些原則只是提供了合理路線設(shè)計的準(zhǔn)則，但操作人員還是要處理一些在這些原則中沒有考慮到，而車輛運作中可能出現(xiàn)的限制或例外情況(緊急訂單、繞行等等)。采用這些方法設(shè)計的路線和時刻表比采用其它未經(jīng)仔細(xì)推敲的方法制定的計劃有實質(zhì)性改進(jìn)。7物流系統(tǒng)工程課件第十四講運輸

6.4.2行車路線和時期表的制定方法

1、掃描法

2、節(jié)約法8物流系統(tǒng)工程課件第十四講運輸1.掃描法(TheSweepMethod)

掃描法可闡述如下：

(1)在地圖或方格圖中確定所有站點(含倉庫)的位置。

(2)自倉庫始沿任一方向向外劃一條直線。沿順時針或逆時針方向旋轉(zhuǎn)該直線直到與某站點相交?？紤]，如果在某線路上增加該站點，是否會超過車輛的載貨能力?如果沒有，繼續(xù)旋轉(zhuǎn)直線，直到與下一個站點相交。再次計算累計貨運量是否超過車輛的運載能力(先使用最大的車輛)。如果超過，就剔除最后的那個站點，并確定路線。隨后，從不包含在上一條路線中的站點開始，繼續(xù)旋轉(zhuǎn)直線以尋找新路線。繼續(xù)該過程直到所有的站點都被安排到路線中。

(3)排定各路線上每個站點的順序使行車距離最短。排序時可以使用“水滴”法或求解“流動推銷員”問題的任何算法。9物流系統(tǒng)工程課件第十四講運輸

史密斯卡車運輸公司用廂式貨車從貨主那里取貨。貨物先運回倉庫，集中后以更大的批量進(jìn)行長途運輸。圖6-10列出了典型的一天取貨量，取貨量單位是件。廂式貨車的載貨量是10000件。完成所有取貨任務(wù)一般需要整整一天的時間。公司想知道需要多少條運輸路線(即多少部車)，每條路線上應(yīng)該經(jīng)過哪些站點，每條路線上的站點應(yīng)該怎樣排序。首先，向北畫一條直線，進(jìn)行逆時針方向“掃描”。這些都是隨機決定的。逆時針旋轉(zhuǎn)該直線，直到裝載的貨物能裝上一輛載重10000件貨物的卡車，同時又不超重。一旦所有的站點都分派有車輛，就可以利用“水滴”法安排經(jīng)過各站點的順序。圖6-10b所列出的是最終的路線設(shè)計。例子10物流系統(tǒng)工程課件第十四講運輸

a)b)11物流系統(tǒng)工程課件第十四講運輸2.節(jié)約法(TheSavingsMethod)

節(jié)約法是一種頗為出色的方法，它能夠靈活處理許多現(xiàn)實中的約束條件，對站點數(shù)量不太多的問題能較快算出結(jié)果，且結(jié)果與最優(yōu)解很接近。對僅有幾個約束條件的小型問題，比較研究顯示，利用節(jié)約法得到的結(jié)果平均只比最優(yōu)解高2％，該方法能夠處理有眾多約束條件的實際問題，主要因為它可以同時確定路線和經(jīng)過各站點的順序。節(jié)約法的目標(biāo)是使所有車輛行駛的總里程最短，并進(jìn)而為所有站點提供服務(wù)的卡車數(shù)量最少。該方法首先假設(shè)每一個站點都有一輛虛擬的卡車提供服務(wù)，隨后返回倉庫，如圖6-11a所示。這時的路線里程是最長的。下一步，將兩個站點合并到同一條行車路線上，減少一輛運輸車，相應(yīng)地縮短路線里程。在決定哪些站點要合并到一條路線時，需要計算合并前后節(jié)約的運輸距離。不在一條運輸路線上的兩點(A和B)合并所節(jié)約的距離就是圖6-11a中路線的里程減去圖6-11b中路線的里程，節(jié)約值為S＝dao＋dob-dab12物流系統(tǒng)工程課件第十四講運輸對每對站點都進(jìn)行這樣的計算，并選擇節(jié)約距離最多的一對站點合并在一起，修訂后的路線見圖6-11b。13物流系統(tǒng)工程課件第十四講運輸

繼續(xù)合并過程。除了將單個站點合并在一起外，還可以將某站點并入已經(jīng)包含多個站點的路線上。例如，如圖6-11c，假如將某站點并入位于同一路線上兩點A和B之間，節(jié)約的距離為S=doc+dco+dab-dac-dcb。(c)插入a、b之間14物流系統(tǒng)工程課件第十四講運輸

如果如圖6-11d所示，站點C排在線路最后一站B之后，則節(jié)約的距離為S=doc+dbo-dbc。(d)插入b之后15物流系統(tǒng)工程課件第十四講運輸

如果如圖6-11e所示，站點C排在站點A之前，則節(jié)約的距離為S=dco+doa-dca(e)插入a之前每次合并時都要計算所節(jié)約距離，節(jié)約距離最多的站點就應(yīng)該納入現(xiàn)有路線。假如由于某些約束條件(如路線太長，無法滿足時間窗口的要求，或超過車輛的承載能力)，節(jié)約距離最多的站點不能并入該路線，就要考慮節(jié)約距離次多的站點。重復(fù)該過程直到所有站點的路線設(shè)計都完成。16物流系統(tǒng)工程課件第十四講運輸節(jié)約法的優(yōu)點節(jié)約法強大的處理能力使得它能夠包含實際應(yīng)用中許多重要的約束條件。該方法可以在指定各路線途經(jīng)站點的同時初步確定站點的先后順序。因此，在將站點歸入某條路線之前，應(yīng)該預(yù)先考查加入新站點后路線的情況。此外，還要考慮一系列有關(guān)路線規(guī)劃的問題，如行車時間是否超過允許的最長駕駛時間，是否滿足司機休息時間的要求，是否有足夠載運量的車輛裝載所有的貨物，各站點時間窗口的要求是否滿足等等。不滿足這些條件可能導(dǎo)致該站點不能并入這條路線或者說明該站點在新路線中的排列順序不當(dāng)。接著就要按照最大節(jié)約值原則選取下一個站點，重復(fù)考慮上述問題。因為擴展問題的難度較大，節(jié)約法不能保證將得到最優(yōu)解，但能夠獲得合理解。17物流系統(tǒng)工程課件第十四講運輸案例網(wǎng)路先鋒公司的線路規(guī)劃和送貨日程安排一、方法：

節(jié)約矩陣分析法二、步驟：1、確認(rèn)距離方陣

2、確認(rèn)節(jié)約方陣

3、將客戶劃歸不同運輸線路的運輸工具4、為運輸線路排定為客戶送貨的順序18物流系統(tǒng)工程課件第十四講運輸案例

送貨線路的規(guī)劃和送貨日程的安排是最重要的運營決策。網(wǎng)路先鋒公司的網(wǎng)上商店向客戶提供送貨上門服務(wù)，向客戶承諾半小時以內(nèi)送貨上門。給定一組客戶定單送貨，該公司的目標(biāo)是對送貨工具和線路進(jìn)行規(guī)劃，對送貨日程進(jìn)行安排，以便在滿足承諾送貨要求的同時，盡可能地降低成本。進(jìn)行運輸工具的安排時，典型的目標(biāo)是以下二者的結(jié)合：一是縮短運輸工具的行程和運輸時間，以減少運費；二是避免出現(xiàn)象送貨延誤之類的失誤。下面以網(wǎng)路先鋒公司配送中心經(jīng)理為例，來討論線路規(guī)劃和設(shè)計過程中的問題。當(dāng)客戶在網(wǎng)上訂貨后，配送中心的員工必須將所需貨物裝到卡車上以備運輸，經(jīng)理必須決定哪輛卡車為哪些客戶送貨，并設(shè)定每輛卡車送貨過程中的行駛線路。經(jīng)理還必須確保每輛卡車都不超載而且能按時送貨。19物流系統(tǒng)工程課件第十四講運輸案例一天上午，網(wǎng)路先鋒公司配送中心的經(jīng)理收到了來自13個不同客戶的訂單。配送中心的位置、每個客戶的坐標(biāo)以及每位客戶所訂貨物見表1所示。經(jīng)理一共有4輛卡車，每輛卡車的載重量是200單位。經(jīng)理認(rèn)為，送貨成本與卡車的總行程即兩點之間的距離高度相關(guān)。因此，經(jīng)理決定將不同客戶的送貨分配到每輛卡車上去，并為每輛卡車設(shè)計行駛線路，以達(dá)到減少總運距的目標(biāo)。配送中心的經(jīng)理首先必須決定哪些卡車為哪些客戶送貨，然后再設(shè)計每輛卡車的行駛線路。在最初的任務(wù)完成后，送貨順序安排和運輸流程改進(jìn)便于制定每輛卡車的行駛路線決策。配送中心的經(jīng)理決定使用節(jié)約矩陣分析法進(jìn)行決策。20物流系統(tǒng)工程課件第十四講運輸案例

21物流系統(tǒng)工程課件第十四講運輸案例節(jié)約矩陣分析法易于操作，即使在時間限制或者其他限制存在的情況下，它仍然可以用來決定哪些卡車為哪些客戶送貨。主要步驟包括：第一步：確認(rèn)距離方陣第二步：確認(rèn)節(jié)約方陣第三步：將客戶劃歸不同運輸線路的運輸工具第四步：為運輸線路排定為客戶送貨的順序前三步用于將客戶分配到運輸工具中去，第四步為每輛卡車設(shè)定行駛線路以縮短行程。

22物流系統(tǒng)工程課件第十四講運輸案例1、確認(rèn)距離方陣確認(rèn)距離方陣是要確認(rèn)任何將要經(jīng)過的兩個地點之間的距離。在這里，我們用兩點之間運輸成本代替兩點之間的距離。如果任意兩點之間的運輸成本已知，那么就用它來代替兩點之間的距離。因此，坐標(biāo)系中A、B兩點之間的距離Dist(A、B)可以用公式表示為(假定A、B兩點的坐標(biāo)(xA,yA)，(xB，yB))：每兩個客戶之間的距離以及它們與配送中心的距離見表2。接下來，我們用任意兩個地點之間的距離，來計算節(jié)約方陣。23物流系統(tǒng)工程課件第十四講運輸案例

24物流系統(tǒng)工程課件第十四講運輸案例2、確認(rèn)節(jié)約方陣節(jié)約方陣是指將兩個客戶的訂貨放在一輛卡車上聯(lián)合運送時節(jié)約的累積。節(jié)約可按照距離、時間或者金錢來計算。網(wǎng)路先鋒公司的經(jīng)理按照距離建立了節(jié)約方陣。運輸工具的行程依其所經(jīng)過地點的順序不同來確認(rèn)。配送中心—客戶x-配送中心這一行程始于配送中心，送貨給客人，然后再回到配送中心。節(jié)約S(x，y)表示的含義是將兩個行程：配送中心—客戶x-配送中心；配送中心—客戶y-配送中心，合二為一：配送中心—客戶x-客戶y-配送中心，而節(jié)約的距離。可以用公式計算如下：例如，用表2經(jīng)理計算出S(1，2)=12+8-9=11。網(wǎng)路先鋒公司送貨的節(jié)約方陣見表3。節(jié)約方陣用來將客戶劃歸不同運輸線路的運輸工具。25物流系統(tǒng)工程課件第十四講運輸案例26物流系統(tǒng)工程課件第十四講運輸案例3、將客戶劃歸不同運輸線路的運輸工具經(jīng)理力圖在將客戶劃歸不同運輸工具或運輸線路中使節(jié)約最大化。這一劃分過程要用到一個重復(fù)進(jìn)行的程序。最初每一客戶被劃分到各自獨立的運輸線路中去。如果兩條運輸線路上的運輸總量不超過卡車的最大載重量，那么二者的合并就是可行的，在任何反復(fù)進(jìn)行的步驟上，網(wǎng)絡(luò)先鋒公司的經(jīng)理總是試圖使節(jié)約最大的兩條線合并成一條新的可行的線路。這一過程一直持續(xù)到不能再合并為止。首先，最大的節(jié)約34來自線路6和線路11的合并，而且這種合并是可行的。因為總運量為16+91=107，小于200，因此這兩個客戶被劃歸一條線路，正如表4所示，從而節(jié)約34在下一步中也就無須再考慮了。27物流系統(tǒng)工程課件第十四講運輸案例

28物流系統(tǒng)工程課件第十四講運輸案例

下一個最大的節(jié)約是將客戶7和客戶6合并為一條線路以后的節(jié)約33，由于合并后的運量為107+56=163，小于200，所以這一合并也是可行的，因此，客戶7被添加到線路6中去，正如表5所示。接下來最大的節(jié)約是合并客戶5和線路6得到的節(jié)約29(我們無須考慮合并客戶7和客戶11的節(jié)約32，因為二者都已經(jīng)安排在線路6中了)。但是這一合并卻不能進(jìn)行，因為客戶5的57個單位的貨物如果添加到線路6已有的貨物中去，那么總運量將超過卡車的最大載重量200。