配送線路優(yōu)化設(shè)計(jì)實(shí)訓(xùn)(精.選)

1、實(shí)訓(xùn)0501:配送線路優(yōu)化設(shè)計(jì)實(shí)訓(xùn)實(shí)訓(xùn)目標(biāo)：1、能根據(jù)給出的配送中心與單個(gè)客戶之間的路線圖及圖中各節(jié)點(diǎn)之間的綜合成本數(shù)值， 找到配送中心與單個(gè)客戶之間的成本最小路線并計(jì)算出此路線成本的數(shù)值。2、能夠在配送中心現(xiàn)有送貨車(chē)輛能力及實(shí)際送貨成本限定的前提下，規(guī)劃出配送中心 往各個(gè)客戶送貨綜合成本最低的送貨網(wǎng)絡(luò)路徑圖。實(shí)訓(xùn)內(nèi)容：1、某配送中心與某單個(gè)客戶之間成本最小路線規(guī)劃及最小成本數(shù)值計(jì)算2、在配送中心現(xiàn)有車(chē)輛送貨能力及車(chē)輛單趟送貨成本有限定的前提下，為配送中 心向多個(gè)客戶送貨規(guī)劃若干條送貨線路，并使各條線路的總成本數(shù)最小。環(huán)境要求：普通多媒體機(jī)房教室情境描述：實(shí)訓(xùn)第1部分情境：某連鎖超市的配送中心

2、位于城市邊緣的郊區(qū)，但超市的一家門(mén)店位于 繁華的城市中心區(qū)，因此負(fù)責(zé)送貨路線規(guī)劃的計(jì)劃調(diào)度員要規(guī)劃出配送中心到這個(gè)門(mén)店的送貨成 本最低的路線。最初按交通圖所示里程最短的線路進(jìn)行送貨，見(jiàn)下圖：圖中O代表配送中心，A代表門(mén)店，V1 V4代表要經(jīng)過(guò)的關(guān)鍵節(jié)點(diǎn)（如主要道路的交 叉路口、立體交叉互通樞紐等），連線邊上的數(shù)值代表每一路段的里程，圖中綠線連接的O-V1-V4-A為里程最短線路。但很快發(fā)現(xiàn)里程最短并不意味著成本最低，因?yàn)槔锍套疃踢@條路有一條新建的大橋（圖中V4點(diǎn)與A點(diǎn)之間黑色加粗部分） 來(lái)回都要收取通行費(fèi)，這條路是城區(qū)主干道且建成時(shí)間較長(zhǎng)通行條件較差，越往城中心走道路擁堵越嚴(yán)重，每趟送貨產(chǎn)生的

3、油耗、車(chē)輛送貨時(shí)間占用、送貨人員工作時(shí)間等綜合成本超出了正常水平，并且多次發(fā)生沒(méi)按門(mén)店的要求時(shí)間送達(dá)的情況。因此計(jì)劃調(diào)度員對(duì)每一條能從O到A的線路都進(jìn)行了實(shí)地勘察記錄，并綜合考慮每條送貨線路的里程、時(shí)間、車(chē)輛耗損，得出了每條線路每一個(gè)路段的送貨運(yùn)行成本，匯總出 了一張從配送中心到此門(mén)店的送貨路徑數(shù)據(jù)圖?，F(xiàn)在計(jì)劃調(diào)度員要依據(jù)此圖，找出配送中心與該門(mén)店之間送貨成本最低路徑。實(shí)訓(xùn)第2部分情境：該配送中心除為該門(mén)店送貨外，還為其他地區(qū)的9個(gè)門(mén)店送貨，按照實(shí)訓(xùn)第1部分的方法，計(jì)劃調(diào)度員找到了配送中心到每個(gè)門(mén)店的成本最低線路，但配送中心的送貨資源有限， 不能為每個(gè)門(mén)店單獨(dú)送貨，只能一輛車(chē)一趟為幾個(gè)門(mén)店循環(huán)

4、送貨。這樣從一個(gè)門(mén)店到另一個(gè)門(mén)店之間也要找到成本最低的線路，因此同樣采用實(shí)訓(xùn)第1部分的方法，找到了兩兩門(mén)店之間的成本最低線路并計(jì)算出了數(shù)值。現(xiàn)在，計(jì)劃調(diào)度員要規(guī)劃從配送中心出發(fā)為各個(gè)門(mén)店循環(huán)送貨后最終回到配送中心的送貨路線總規(guī)劃圖并且總送貨成本要配送中心到各門(mén)店及兩兩門(mén)店之間的成本最低線路數(shù)值表0A10AB94BC795CD8 I14I 105DE8181496EF8 :18r 1715137FG3 I13I 121011116G IH4141311121282HI10111517181817119IJ7481315151510118最低。實(shí)訓(xùn)組織形式： 學(xué)生獨(dú)立完成實(shí)訓(xùn)過(guò)程。圖中0代表配送中

5、心，A代表門(mén)店,實(shí)訓(xùn)資料：1、配送中心與位于城中心門(mén)店之間的網(wǎng)絡(luò)路線圖,，連V1 V4代表要經(jīng)過(guò)的關(guān)鍵節(jié)點(diǎn)（如主要道路的交叉路口、立體交叉互通樞紐等） 線邊上的數(shù)值代表每一路段送貨運(yùn)行的最低成本值。2、配送中心的配送網(wǎng)絡(luò)， 見(jiàn)下圖。圖中0點(diǎn)為配送中心，A J為要送貨的門(mén)店，共10 個(gè)門(mén)店。括號(hào)內(nèi)為配送貨物重量（單位：公斤），線路邊上的數(shù)字為配送中心送貨到各門(mén)店的最低成本值。工作流程：計(jì)算配送中心與某一個(gè)門(mén)店之間的最小成本線路T計(jì)算配送中心到其它門(mén)店及兩兩門(mén)店之間的最小成本線路數(shù)值（此步驟采用與上一步驟相同的計(jì)算方法均可計(jì)算出來(lái)，考慮實(shí)訓(xùn)時(shí)間限制，計(jì)算過(guò)程從略，直接給出數(shù)據(jù)表）7規(guī)劃從配送中心出

6、發(fā)（最后還要回到配送 中心），在貨車(chē)載重及單趟送貨總成本限制下單趟可送貨門(mén)店最多的線路7把計(jì)算出的各條 送貨線路標(biāo)示出來(lái)，形成一張送貨路徑規(guī)劃圖。實(shí)訓(xùn)步驟：1、根據(jù)實(shí)訓(xùn)資料1給出的配送中心與城中心門(mén)店之間的網(wǎng)絡(luò)路徑圖，找出配送中心（0點(diǎn)）到這個(gè)門(mén)店（A點(diǎn)）之間成本最低線路并算出成本值。步:0點(diǎn)是原始已解節(jié)點(diǎn)，從配送中心0點(diǎn)出發(fā)，可以走VI、V2兩個(gè)節(jié)點(diǎn)，由于0V1= 3、0V1線路，V1成為已解節(jié)點(diǎn)，見(jiàn)下圖。0V2= 11，因此選擇走第二步：與0 V1兩個(gè)已解節(jié)點(diǎn)相連的未解節(jié)點(diǎn)有V2、V3、V4,可選擇的送貨路線為：0-V1-V4、0-V1-V3、0-V2，相應(yīng)的送貨成本值為：0-V1-V4

7、= 3+1 = 40-V1-V3 = 3+7 = 100-V2= 110-V1-V4線路的成本最少，因此V4成為已解節(jié)點(diǎn)，見(jiàn)下圖。1V1V483370A1124V2V31第三步:與0V1、V4三個(gè)已解節(jié)點(diǎn)相連的未解節(jié)點(diǎn)有V2、V3、A,可選擇的送貨路線為：0-V1-V4-A、0-V1-V4-V3、0-V1-V3、0-V2,相應(yīng)的送貨成本值為：0-V1-V4-A = 3+1+8= 120-V1-V4-V3 = 3+1+3= 70-V1-V3 = 3+7 = 100-V2= 110-V1-V4-V3線路的成本最少，因此 V3成為已解節(jié)點(diǎn)，見(jiàn)下圖。1V1V483370A1124V2V31第四步：與0

8、 V1、V4、V3四個(gè)已解節(jié)點(diǎn)相連的未解節(jié)點(diǎn)有 V2、A，可選擇的送貨路線為：0-V1-V4-V3-A、0-V1-V4-V3-V2、0-V1-V3-A、0-V1-V3-V2、0-V2,相應(yīng)的送貨成本值為:0-V1-V4-V3-A = 3+1+3+4= 110-V1-V4-V3-V2 = 3+1+3+1 = 80-V1-V3-A = 3+7+4= 140-V1-V3-V2 = 3+7+1= 110-V2= 11O-V1-V4-V3-V2線路的成本最少，因此V2成為已解節(jié)點(diǎn)，見(jiàn)下圖。1ViV48337OA1124V2V31第五步:與OV1、V4、V3 V2五個(gè)已解節(jié)點(diǎn)相連的未解節(jié)點(diǎn)只有 A可選擇的

9、送貨路線為：O-V1-V4-V3-A、O-V1-V4-V3-V2-A、O-V1-V3-A、O-V1-V3-V2-A、0-V2-A、0-V1-V4-A , 相應(yīng)的送貨成本值為：O-V1-V4-V3-A = 3+1+3+4= 11O-V1-V4-V3-V2-A = 3+1+3+1+2= 10O-V1-V3-A = 3+7+4= 14O-V1-V3-V2-A = 3+7+1+2= 13O-V2-A= 11+2 = 13O-V1-V4-A = 3+1+8= 12O-V1-V4-V3-V2-A線路的成本最少，因此這條線路是配送中心與該門(mén)店之間成本最低的 送貨線路，線路的送貨成本數(shù)值為10,見(jiàn)下圖。最后通

10、過(guò)與實(shí)訓(xùn)情境中里程最短路線O-V1-V4-A的成本比較一下，里程最短路線的成本為12,成本最小路線 O-V1-V4-V3-V2-A的成本為10。2、該配送中心除為該門(mén)店送貨外，還為其他地區(qū)的9個(gè)門(mén)店送貨，按照實(shí)訓(xùn)第1部分的方法，計(jì)劃調(diào)度員找到了配送中心到每個(gè)門(mén)店的成本最低線路，但配送中心的送貨資源有限，不能為每個(gè)門(mén)店單獨(dú)送貨，只能一輛車(chē)一趟為幾個(gè)門(mén)店循環(huán)送貨。這樣從一個(gè)門(mén)店到另一個(gè)門(mén)店之間也要找到成本最低的線路。通過(guò)一段時(shí)間的努力， 計(jì)劃調(diào)度員找到了配送中心到每個(gè)門(mén)店的成本最低線路及兩兩門(mén)店之間的成本最 低線路并計(jì)算出了數(shù)值。配送中心的現(xiàn)有送貨限制為：只有額定載重分別為2噸和4噸兩種廂式貨車(chē)可

11、供送貨 （即送貨路線上各客戶的貨物總重小于2噸的使用2噸的車(chē)型，超過(guò)2噸的用4噸的車(chē)型，但送貨路線上各門(mén)店的貨物總重最多不超過(guò) 4噸）考慮到達(dá)門(mén)店裝卸后交付時(shí)間、送貨路上時(shí)間、綜合成本等因素，每輛車(chē)每 次送貨的成本不能超過(guò) 30。步:配送中心到各門(mén)店及兩兩門(mén)店之間的成本最低線路數(shù)值表OA10 :AB94BC795CD8 114M05DE8181496EF8 I181715137FG3 113M21011116G IH4141311121282HI10 :11151718181711 19 1IJ7481315151510118根據(jù)“配送中心到各門(mén)店及兩兩門(mén)店之間成本最低線路的數(shù)值表（見(jiàn)上表）”

12、和節(jié)約法的基本原理，計(jì)算出兩兩門(mén)店之間的節(jié)約成本。計(jì)算方法是：i,j是任意相鄰兩門(mén)店節(jié)點(diǎn) Oi=a，OJ=b, ij=c，則i j節(jié)約的成本為：a+b-c。例如：A, B兩點(diǎn)的節(jié)約成本為， OA+OB-AB =10+9-4 = 15。計(jì)算結(jié)果填入下表中。AB15BC8 1111 CD4710DE03310EF0 101 039FG000015GH0000045HI9 I4I 000125IJ1381000009J4、根據(jù)上表中的出兩兩門(mén)店之間的節(jié)約成本計(jì)算結(jié)果，按節(jié)約成本大小順序排列到下 表中。序號(hào)連接點(diǎn)節(jié)約里程序號(hào)連接點(diǎn)節(jié)約里程1A B1513F G52A J1313G H53B C1113

13、H I54C D1016A D44D E1016B I46A I916F H46E F919B E36I J919D F39A C821G I29B J822C J111B D722E G112C E622F I15、有了以上計(jì)算數(shù)據(jù)后就可以對(duì)初始的送貨路線進(jìn)行優(yōu)化了。下圖是初始方案，從配送中心分別向各個(gè)門(mén)店節(jié)點(diǎn)送貨，共有10條送貨路線，總成本數(shù)為 148,需載重2噸的貨車(chē)10輛。如下圖所示。6、按節(jié)約成本的大小順序鏈接A-B,A-J,B-C, 同時(shí)取消O B O-A路線,形成巡回路線，如下圖所示。這時(shí)配送路線共有7條，各條線路總成本為109，需要載重2噸的貨車(chē)6輛，4噸的貨車(chē)1輛。見(jiàn)下圖（圖

14、中綠色線條代表選中的線路，紅色線條代表取消的線路，后續(xù)各圖均同）。由圖可知，規(guī)劃的配送路線1 ，裝載貨物3.6噸，成本為27 。7、按節(jié)約成本大小順序，應(yīng)該是C-D和D-E,C-D有可能并到二次解線路1中，但目前配送路線1已裝載貨物3.6噸運(yùn)行成本為27公里，考慮到單車(chē)載重量和線路 成本限制（每條線路成本不超過(guò)30 ）,配送路線1不能再增加送貨門(mén)店,為此連接D-E,組成配送線路2,如下圖所示。其裝載重量為1.8噸,成本22。此時(shí)，共8、下面的節(jié)約成本大小順序是 A-I、E-F,由于門(mén)店A己組合到配送線路 1中，該 線路不再增加新門(mén)店，故不連接 A-I;連接E-F并入配送線路2中，并取消0-E線 路，此時(shí)配送線路共有 5條，如下圖所示。線路2的裝載量為3.3噸，運(yùn)行成本為 29。此時(shí)，共有配送線路 5條，總運(yùn)行成本為 90，需載重2噸的貨車(chē)3輛,4噸 的貨車(chē)2輛。9、按節(jié)約成本順序，接下來(lái)應(yīng)該是l-J,A-C,B-J,B-D,C-E,但這些連接已包含在配送線路1或2中,不能再組合成新的線路。再下來(lái)是F-G,可組合在配送線路2中,如下圖所示。此時(shí)，線路 2的裝載量為3.9噸，運(yùn)行成本為30 ,這樣共有4條線 路，總成本為85 ,需載重2噸貨車(chē)2輛,4噸的貨車(chē)2輛。10、接下來(lái)的節(jié)約成本順序?yàn)?G-H,由于受裝載量及線路里程的限制，不再組合到線路2中，故連接H-I組成配送線路3,如下圖