配送線路優(yōu)化設(shè)計實訓

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

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

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

4、最低線路， 但配送中 心的送貨資源有限， 不能為每個門店單獨送貨， 只能一輛車一趟為幾個門店循環(huán)送貨。 這樣 從一個門店到另一個門店之間也要找到成本最低的線路，因此同樣采用實訓第 1 部分的方 法，找到了兩兩門店之間的成本最低線路并計算出了數(shù)值?，F(xiàn)在， 計劃調(diào)度員要規(guī)劃從配送中心出發(fā)為各個門店循環(huán)送貨后最終回到配送中心的送貨路線總規(guī)劃圖并且總送貨成本要最低。8798810O3710600)E1400)H800)F1500)B1500)I500)A700)D400)C800)G600)配送中心到各門店及兩兩門店之間的成本最低線路數(shù)值表OA10AB94BC795CD814105DE8181496E

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

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

7、送中心O點出發(fā)，可以走V1、V2 兩個節(jié)點，由于OV13、OV1線路， V1 成為已解節(jié)點，見下圖。OV211，因此選擇走第二步：與 O、V1 兩個已解節(jié)點相連的未解節(jié)點有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é)點，見下圖。第三步：與 O、V1、V4三個已解節(jié)點相連的未解節(jié)點有V2、V3、A，可選擇的送貨路線為： O-V1-V4-A 、O-V1-V4-V3 、 O-V1-V3、O-V2，相應(yīng)的送貨成本值為：O-V1-V4

8、-A3+1+812O-V1-V4-V3 3+1+3 7O-V1-V33+710O-V211O-V1-V4-V3 線路的成本最少，因此 V3 成為已解節(jié)點，見下圖。1V18337OA1124V2V31第四步：與 O、V1、V4、V3 四個已解節(jié)點相連的未解節(jié)點有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-A 3+1+3+4 11O-V1-V4-V3-V2 3+1+3+18O-V1-V3-A3+7+414O-V1-V3-V2 3+7+1 11O-V211

9、O-V1-V4-V3-V2 線路的成本最少，因此 V2 成為已解節(jié)點，見下圖。1V1V48337OA1124V2V31第五步：與 O、V1、 V4、 V3、V2 五個已解節(jié)點相連的未解節(jié)點只有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-A 3+1+3+4 11O-V1-V4-V3-V2-A 3+1+3+1+210 O-V1-V3-A3+7+414O-V1-V3-V2-A 3+7+1+2 13 O-V2-A11+213O-V

10、1-V4-A3+1+812O-V1-V4-V3-V2-A 線路的成本最少， 因此這條線路是配送中心與該門店之間成本最低的 送貨線路，線路的送貨成本數(shù)值為 10，見下圖。1V18337OA1124V2V31最后通過與實訓情境中里程最短路線 O-V1-V4-A 的成本比較一下， 里程最短路線的成本為 12，成本最小路線 O-V1-V4-V3-V2-A 的成本為 10。2、 該配送中心除為該門店送貨外， 還為其他地區(qū)的 9 個門店送貨， 按照實訓第 1 部分 的方法， 計劃調(diào)度員找到了配送中心到每個門店的成本最低線路，但配送中心的送貨資源有限， 不能為每個門店單獨送貨， 只能一輛車一趟為幾個門店循環(huán)

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

12、05DE8181496EF8181715137FG313121011116GH4141311121282HI10111517181817119IJ7481315151510118根據(jù)“配送中心到各門店及兩兩門店之間成本最低線路的數(shù)值表（見上表） ”和節(jié)約法的基 本原理，計算出兩兩門店之間的節(jié)約成本。計算方法是： i,j 是任意相鄰兩門店節(jié)點 Oi=a ， OJ=b， ij=c ，則 i j 節(jié)約的成本為： a+b-c 。例如： A， B 兩點的節(jié)約成本為， OA+OB-AB 10+9-4 15。計算結(jié)果填入下表中。AB15BC811CD4710DE03310EF00039FG000015GH0

13、000045HI94000125IJ1381000009J4、根據(jù)上表中的出兩兩門店之間的節(jié)約成本計算結(jié)果，按節(jié)約成本大小順序排列到下 表中。序號連接點節(jié)約里程序號連接點節(jié)約里程1AB1513FG52AJ1313GH53BC1113HI54CD1016AD44DE1016BI46AI916FH46EF919BE36IJ919DF39AC821GI29B J822C J111BD722EG112CE622FI15、有了以上計算數(shù)據(jù)后就可以對初始的送貨路線進行優(yōu)化了。下圖是初始方案，從配 送中心分別向各個門店節(jié)點送貨，共有 10 條送貨路線，總成本數(shù)為 148，需載重 2 噸的貨 車 10 輛。如

14、下圖所示。6、按節(jié)約成本的大小順序鏈接 A-B,A-J,B-C, 同時取消 OB、O-A 路線, 形成巡回路 線 , 如下圖所示。這時配送路線共有 7 條，各條線路總成本為 109 ，需要載重 2 噸的貨車 6 輛，4 噸的貨車 1 輛。見下圖 （圖中綠色線條代表選中的線路， 紅色線條代表取消的線路， 后續(xù)各圖均同） 。由圖可知 , 規(guī)劃的配送路線 1 ，裝載貨物噸，成本為 27 。7、按節(jié)約成本大小順序 , 應(yīng)該是 但目前配送路線 1 已裝載貨物噸運行成本為（ 每條線路成本不超過 30 ） , 配送路線 1 不能再增加送貨門店 組成配送線路 2, 如下圖所示。 其裝載重量為噸 , 成本 22

15、 。此時，共有配送線C-D 和有可能并到二次解線路 1 中 ,限制D-E,C-D27 公里，考慮到單車載重量和線路成本, 為此連接D-E,路 68、下面的節(jié)約成本大小順序是A-I 、 E-F, 由于門店 A 己組合到配送線路 1 中，該線路不再增加新門店，故不連接 A-I; 連接 E-F 并入配送線路 2 中，并取消 O-E 線 路，此時配送線路共有 5 條 , 如下圖所示。線路 2 的裝載量為 噸 , 運行成本為29 。此時，共有配送線路 5 條，總運行成本為 90 ，需載重 2 噸的貨車 3 輛 ,4 噸 的貨車 2 輛。9、按節(jié)約成本順序，接下來應(yīng)該是I-J,A-C,B-J,B-D,C-E,但這些連接已包含在配送線路 1 或 2 中 , 不能再組合成新的線路。再下來是 F-G, 可組合在配送線路 2 中，如下圖所示。 此時，線路 2 的裝載量為 噸 , 運行成本為 30 , 這樣共有 4 條線路總成本為 85 , 需載重 2 噸貨車 2 輛 ,4 噸的貨車 2 輛。10、接下來的節(jié)約成本順序為 G-H, 由于受裝載量及線路里程的限制，不再組合到線路 2 中，故連接 H-I 組成配送線路 3, 如下圖所示