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

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

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

4、車一趟為幾個門店循環(huán)送貨。這樣從一個門店到另一個門店之間也要找到成本最低的線路，因此同樣采用實(shí)訓(xùn)第1部分的方法，找到了兩兩門店之間的成本最低線路并計(jì)算出了數(shù)值?，F(xiàn)在，計(jì)劃調(diào)度員要規(guī)劃從配送中心出發(fā)為各個門店循環(huán)送貨后最終回到配送中心的送貨路線總規(guī)劃圖并且總送貨成本要最低。OF（1500）D（400）C（800）B（1500）A（700）E（1400）G（600）J（600）H（800）I（500）879107104388配送中心到各門店及兩兩門店之間的成本最低線路數(shù)值表OA10AB94BC795CD814105DE8181496EF8181715137FG313121011116GH41413

5、11121282HI10111517181817119IJ7481315151510118實(shí)訓(xùn)組織形式：學(xué)生獨(dú)立完成實(shí)訓(xùn)過程。實(shí)訓(xùn)資料：1、配送中心與位于城中心門店之間的網(wǎng)絡(luò)路線圖，圖中O代表配送中心，A代表門店，V1V4代表要經(jīng)過的關(guān)鍵節(jié)點(diǎn)（如主要道路的交叉路口、立體交叉互通樞紐等），連線邊上的數(shù)值代表每一路段送貨運(yùn)行的最低成本值。OAV4V2V3V131321871142、配送中心的配送網(wǎng)絡(luò)，見下圖。圖中O點(diǎn)為配送中心，AJ 為要送貨的門店，共 10 個門店。括號內(nèi)為配送貨物重量（單位：公斤），線路邊上的數(shù)字為配送中心送貨到各門店的最低成本值。工作流程：計(jì)算配送中心與某一個門店之間的最小成

6、本線路計(jì)算配送中心到其它門店及兩兩門店之間的最小成本線路數(shù)值（此步驟采用與上一步驟相同的計(jì)算方法均可計(jì)算出來，考慮實(shí)訓(xùn)時間限制，計(jì)算過程從略，直接給出數(shù)據(jù)表）規(guī)劃從配送中心出發(fā)（最后還要回到配送中心），在貨車載重及單趟送貨總成本限制下單趟可送貨門店最多的線路把計(jì)算出的各條送貨線路標(biāo)示出來，形成一X送貨路徑規(guī)劃圖。實(shí)訓(xùn)步驟：1、 根據(jù)實(shí)訓(xùn)資料1給出的配送中心與城中心門店之間的網(wǎng)絡(luò)路徑圖，找出配送中心（O點(diǎn)）到這個門店（A點(diǎn)）之間成本最低線路并算出成本值。OAV4V2V3一步：O點(diǎn)是原始已解節(jié)點(diǎn)，從配送中心O點(diǎn)出發(fā)，可以走V1、V2兩個節(jié)點(diǎn)，由于OV13、OV211，因此

7、選擇走OV1線路，V1成為已解節(jié)點(diǎn)，見下圖。OAV4V2V3二步：與O、V1兩個已解節(jié)點(diǎn)相連的未解節(jié)點(diǎn)有V2、V3、V4，可選擇的送貨路線為：O-V1-V4、O-V1-V3、O-V2，相應(yīng)的送貨成本值為：O-V1-V43+14O-V1-V33+710O-V211O-V1-V4線路的成本最少，因此V4成為已解節(jié)點(diǎn)，見下圖。OAV4V2V3三步：與O、V1、V4三個已解節(jié)點(diǎn)相連的未解節(jié)點(diǎn)有V2、V3、A，可選擇的送貨路線為：O-V1-V4-A、O-V1-V4-V3、O-V1-V3、O-V2，相應(yīng)的送貨成本值為：O-V1-V4-A3+1+812O-

8、V1-V4-V33+1+37O-V1-V33+710O-V211O-V1-V4-V3線路的成本最少，因此V3成為已解節(jié)點(diǎn)，見下圖。OAV4V2V3四步：與O、V1、V4、V3四個已解節(jié)點(diǎn)相連的未解節(jié)點(diǎn)有V2、 A，可選擇的送貨路線為：O-V1-V4-V3-A、O-V1-V4-V3-V2、O-V1-V3-A、O-V1-V3-V2、O-V2，相應(yīng)的送貨成本值為：O-V1-V4-V3-A3+1+3+411O-V1-V4-V3-V23+1+3+18O-V1-V3-A3+7+414O-V1-V3-V23+7+111O-V211O-V1-V4-V3-V2線路的成本最少，因此V2成

9、為已解節(jié)點(diǎn)，見下圖。OAV4V2V3五步：與O、V1、V4、V3、V2五個已解節(jié)點(diǎn)相連的未解節(jié)點(diǎn)只有A，可選擇的送貨路線為：O-V1-V4-V3-A、O-V1-V4-V3-V2-A、O-V1-V3-A、O-V1-V3-V2-A、O-V2-A、O-V1-V4-A，相應(yīng)的送貨成本值為：O-V1-V4-V3-A3+1+3+411O-V1-V4-V3-V2-A3+1+3+1+210O-V1-V3-A3+7+414O-V1-V3-V2-A3+7+1+213O-V2-A11+213O-V1-V4-A3+1+812O-V1-V4-V3-V2-A線路的成本最少，因此這條線路是配送中心

10、與該門店之間成本最低的送貨線路，線路的送貨成本數(shù)值為10，見下圖。OAV4V2V3后通過與實(shí)訓(xùn)情境中里程最短路線O-V1-V4-A的成本比較一下，里程最短路線的成本為12，成本最小路線O-V1-V4-V3-V2-A的成本為10。2、 該配送中心除為該門店送貨外，還為其他地區(qū)的9個門店送貨，按照實(shí)訓(xùn)第1部分的方法，計(jì)劃調(diào)度員找到了配送中心到每個門店的成本最低線路，但配送中心的送貨資源有限，不能為每個門店單獨(dú)送貨，只能一輛車一趟為幾個門店循環(huán)送貨。這樣從一個門店到另一個門店之間也要找到成本最低的線路。通過一段時間的努力，計(jì)劃調(diào)度員找到了配送中心到每個門店的成本最低線路及兩

11、兩門店之間的成本最低線路并計(jì)算出了數(shù)值。配送中心的現(xiàn)有送貨限制為：只有額定載重分別為 2噸和 4噸兩種廂式貨車可供送貨（即送貨路線上各客戶的貨物總重小于2噸的使用2噸的車型，超過2噸的用4噸的車型，但送貨路線上各門店的貨物總重最多不超過4噸）考慮到達(dá)門店裝卸后交付時間、送貨路上時間、綜合成本等因素，每輛車每次送貨的成本不能超過30。第一步： 配送中心到各門店及兩兩門店之間的成本最低線路數(shù)值表OA10AB94BC795CD814105DE8181496EF8181715137FG313121011116GH4141311121282HI10111517181817119IJ74813151515

12、10118根據(jù)“配送中心到各門店及兩兩門店之間成本最低線路的數(shù)值表（見上表）”和節(jié)約法的基本原理，計(jì)算出兩兩門店之間的節(jié)約成本。計(jì)算方法是：i,j是任意相鄰兩門店節(jié)點(diǎn)Oi=a，OJ=b，ij=c，則 ij節(jié)約的成本為：a+b-c 。例如：A，B兩點(diǎn)的節(jié)約成本為，OA+OB-AB10+9-415。計(jì)算結(jié)果填入下表中。AB15BC811CD4710DE03310EF00039FG000015GH0000045HI94000125IJ1381000009J4、根據(jù)上表中的出兩兩門店之間的節(jié)約成本計(jì)算結(jié)果，按節(jié)約成本大小順序排列到下表中。序號連接點(diǎn)節(jié)約里程序號連接點(diǎn)節(jié)約里程1AB1513FG52AJ1

13、313GH53BC1113HI54CD1016AD44DE1016BI46AI916FH46EF919BE36IJ919DF39AC821GI29BJ822CJ111BD722EG112CE622FI15、有了以上計(jì)算數(shù)據(jù)后就可以對初始的送貨路線進(jìn)行優(yōu)化了。下圖是初始方案，從配送中心分別向各個門店節(jié)點(diǎn)送貨，共有10條送貨路線，總成本數(shù)為148，需載重2噸的貨車10輛。如下圖所示。OF（1500）D（400）C（800）B（1500）A（700）E（1400）G（600）J（600）H（800）I（500）8791071043886、按節(jié)約成本的大小順序 A-B,A-J,B-C, 同時取消OB、

14、O-A路線, 形成巡回路線 ,如下圖所示。這時配送路線共有 7 條，各條線路總成本為 109，需要載重2噸的貨車6輛，4噸的貨車 1 輛。見下圖（圖中綠色線條代表選中的線路，紅色線條代表取消的線路，后續(xù)各圖均同）。由圖可知 , 規(guī)劃的配送路線 1 ，裝載貨物3.6噸，成本為 27。OF（1500）D（400）C（800）B（1500）A（700）E（1400）G（600）J（600）H（800）I（500）877104388544配送路線17、按節(jié)約成本大小順序 , 應(yīng)該是 C-D 和 D-E,C-D 有可能并到二次解線路 1 中 , 但目前配送路線 1 已裝載貨物3.6噸運(yùn)行成本為 27 公

15、里，考慮到單車載重量和線路成本限制 ( 每條線路成本不超過 30) , 配送路線 1 不能再增加送貨門店 , 為此連接 D-E, 組成配送線路 2, 如下圖所示。其裝載重量為1.8噸, 成本 22。此時，共有配送線路 6 條，總成本99，需載重 2 噸的貨車 5 輛，4噸的貨車 1 輛。OF（1500）D（400）C（800）B（1500）A（700）E（1400）G（600）J（600）H（800）I（500）877104388544配送路線16配送路線28、下面的節(jié)約成本大小順序是 A-I、E-F, 由于門店 A 己組合到配送線路 1 中，該線路不再增加新門店，故不連接 A-I; 連接 E

16、-F 并入配送線路 2 中，并取消 O-E 線路，此時配送線路共有 5 條 , 如下圖所示。線路 2 的裝載量為 3.3噸, 運(yùn)行成本為 29。此時，共有配送線路5條，總運(yùn)行成本為90，需載重 2噸的貨車 3 輛 ,4噸的貨車 2 輛。OF（1500）D（400）C（800）B（1500）A（700）E（1400）G（600）J（600）H（800）I（500）877104387544配送路線16配送路線29、按節(jié)約成本順序，接下來應(yīng)該是 I-J,A-C,B-J,B-D,C-E, 但這些連接已包含在配送線路 1 或 2 中 , 不能再組合成新的線路。再下來是 F-G, 可組合在配送線路 2 中

17、，如下圖所示。此時，線路 2 的裝載量為 3.9噸 , 運(yùn)行成本為 30 , 這樣共有 4 條線路 , 總成本為85 , 需載重 2噸貨車 2 輛 ,4噸的貨車 2 輛。OF（1500）D（400）C（800）B（1500）A（700）E（1400）G（600）J（600）H（800）I（500）877104367544配送路線16配送路線210、接下來的節(jié)約成本順序?yàn)?G-H, 由于受裝載量及線路里程的限制，不再組合到線路 2 中，故連接 H-I 組成配送線路 3, 如下圖所示 , 其裝載量為 1.3噸, 運(yùn)行成本為23 , 此時，形成最終方案，如下圖。共有三條配送線路，總成本為80 , 需載重