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

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

3、趟送貨產生的油耗、車輛送貨時間占用、送貨人員工作時間等綜合成本超出了正常水平，并且多次發生沒按門店的要求時間送達的情況。因此計劃調度員對每一條能從 0到A的線路都進行了實地勘察記錄，并綜合考慮每條送貨線路的里程、時間、車輛耗損，得出了每條線路每一個路段的送貨運行成本，匯總出 了一張從配送中心到此門店的送貨路徑數據圖（見實訓資料1）。現在計劃調度員要依據此圖，找出配送中心與該門店之間送貨成本最低路徑。實訓第2部分情境：該配送中心除為該門店送貨外，還為其他地區的9個門店送貨，按照實訓第1部分的方法，計劃調度員找到了配送中心到每個門店的成本最低線路（見實訓資料2），但配送中心的送貨資源有限，不能為每

4、個門店單獨送貨，只能一輛車一趟為幾個門 店循環送貨。這樣從一個門店到另一個門店之間也要找到成本最低的線路，因此同樣采用實訓第1部分的方法，找到了兩兩門店之間的成本最低線路并計算出了數值（見實訓資料2 ）。現在，計劃調度員要規劃從配送中心出發為各個門店循環送貨后最終回到配送中心的送貨路線總規劃圖并且總送貨成本要最低。實訓組織形式：學生獨立完成實訓過程。實訓資料：1、配送中心與位于城中心門店之間的網絡路線圖，圖中0代表配送中心，A代表門店，V1 V4代表要經過的關鍵節點（如主要道路的交叉路口、立體交叉互通樞紐等），連線邊上的數值代表每一路段送貨運行的最低成本值。，線路邊上的數字為配送中心送貨到各公

5、斤）2、配送中心的配送網絡， 見下圖。圖中0點為配送中心，A J為要送貨的門店，共10 個門店。括號內為配送貨物重量（單位： 門店的最低成本值。配送中心到各門店及兩兩門店之間的成本最低線路數值表0A10AB94BC795CD814105DE8181496EF8181715137FG313121011116GH4141311121282HI10111517181817119IJ7481315151510118工作流程：計算配送中心與某一個門店之間的最小成本線路7計算配送中心到其它門店及兩兩門店之間的最小成本線路數值（此步驟采用與上一步驟相同的計算方法均可計算出來，考慮實訓時間限制，計算過程從略，

6、直接給出數據表）7規劃從配送中心出發（最后還要回到配送 中心），在貨車載重及單趟送貨總成本限制下單趟可送貨門店最多的線路7把計算出的各條 送貨線路標示出來，形成一張送貨路徑規劃圖。找出配送中心（0實訓步驟：1、根據實訓資料1給出的配送中心與城中心門店之間的網絡路徑圖, 點）到這個門店（A點）之間成本最低線路并算出成本值。第一步:0點是原始已解節點，從配送中心0點出發，可以走 V1、V2兩個節點，由于 0V仁3、0V2= 11，因此選擇走 0V1線路，V1成為已解節點，見下圖。第二步：與O V1兩個已解節點相連的未解節點有0-V1-V3、0-V2，相應的送貨成本值為：0-V1-V4 = 3+1

7、= 40-V1-V3 = 3+7 = 100-V2= 110-V1-V4線路的成本最少，因此V4成為已解節點,V2、V3、V4,可選擇的送貨路線為:0-V1-V4、見下圖。與0V1、V4三個已解節點相連的未解節點有V2、V3、A,可選擇的送貨路線為:0-V1-V4-V3、0-V1-V3、0-V2,相應的送貨成本值為：0-V1-V4-A = 3+1+8= 120-V1-V4-V3 = 3+1+3= 70-V1-V4-A、0-V1-V3 = 3+7 = 100-V2= 11O-V1-V4-V3線路的成本最少，因此 V3成為已解節點，見下圖。第四步:V2、A，可選擇的送貨路線為:與OV1、V4、V3

8、四個已解節點相連的未解節點有O-V1-V4-V3-A、O-V1-V4-V3-V2、O-V1-V3-A、O-V1-V3-V2、O-V2,相應的送貨成本值為:O-V1-V4-V3-A = 3+1+3+4= 11O-V1-V4-V3-V2 = 3+1+3+1 = 8 0-V1-V3-A = 3+7+4= 14O-V1-V3-V2 = 3+7+1= 11 0-V2= 11 見下圖。O-V1-V4-V3-V2線路的成本最少，因此V2成為已解節點,與 O VI、V4、V3 V2五個已解節點相連的未解節點只有O-V1-V4-V3-A、O-V1-V4-V3-V2-A、0-V1-V3-A、O-V1-V3-V2-

9、A、A可選擇的送貨路線為：O-V2-A、O-V1-V4-A ,第五步:相應的送貨成本值為: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線路的成本最少，因此這條線路是配送中心與該門店之間成本最低的送貨線路，線路的送貨成本數值為10，見下圖。最后通過與實訓情境中里程最短路線0-V1-V4-A的成本比較一下，里程最短路線的成本為12,

10、成本最小路線 O-V1-V4-V3-V2-A的成本為10。2、該配送中心除為該門店送貨外，還為其他地區的9個門店送貨，按照實訓第1部分的方法，計劃調度員找到了配送中心到每個門店的成本最低線路，但配送中心的送貨資源有限，不能為每個門店單獨送貨，只能一輛車一趟為幾個門店循環送貨。這樣從一個門店到另一個門店之間也要找到成本最低的線路。通過一段時間的努力， 計劃調度員找到了配送中心到每個門店的成本最低線路及兩兩門店之間的成本最低線路并計算出了數值。配送中心的現有送貨限制為：只有額定載重分別為2噸和4噸兩種廂式貨車可供送貨 （即送貨路線上各客戶的貨物總重小于 2噸的使用2 噸的車型，超過2噸的用4噸的車

11、型，但送貨路線上各門店的貨物總重最多不超過4噸）考慮到達門店裝卸后交付時間、送貨路上時間、綜合成本等因素，每輛車每 次送貨的成本不能超過 30。第一步:配送中心到各門店及兩兩門店之間的成本最低線路數值表0A10AB94BC795CD814105DE8181496EF8181715137FG313121011116GH4141311121282HI10111517181817119IJ7481315151510118根據“配送中心到各門店及兩兩門店之間成本最低線路的數值表（見上表）”和節約法的基本原理，計算出兩兩門店之間的節約成本。計算方法是：i,j是任意相鄰兩門店節點 Oi=a，OJ=b, i

12、j=c，則i j節約的成本為：a+b-c。例如：A B兩點的節約成本為， OA+OB-AB =10+9-4 = 15。計算結果填入下表中。AB15BC811CD4710DE03310EF00039FG000015GH0000045HI94000125IJ1381000009J4、根據上表中的出兩兩門店之間的節約成本計算結果，按節約成本大小順序排列到下表中。序號連接點節約里程序號連接點節約里程1A B1513F G52A J1313G H53B C1113H I54C D1016A D44D E1016B I46A I916F H46E F919B E36I J919D F39AC821G I2

13、9BJ822C J111B D722E G112C E622F I15、有了以上計算數據后就可以對初始的送貨路線進行優化了。下圖是初始方案，從配送中心分別向各個門店節點送貨，共有10條送貨路線，總成本數為 148,需載重2噸的貨車10輛。如下圖所示。O B O-A路線,形成巡回路109，需要載重2噸的貨車紅色線條代表取消的線路，3.6噸，成本為27 。6、按節約成本的大小順序鏈接 A-B,A-J,B-C, 同時取消 線，如下圖所示。這時配送路線共有 7條，各條線路總成本為 6輛，4噸的貨車1輛。見下圖（圖中綠色線條代表選中的線路， 后續各圖均同）。由圖可知，規劃的配送路線1 ，裝載貨物C-D

14、和 D-E,C-D 噸運行成本為27 成本限制（每條線路成本不超過30 ）,接D-E,組成配送線路2,配送路線1如下圖所示。其裝載重量為1.8噸,成本22。此時，共7、按節約成本大小順序，應該是 但目前配送路線1已裝載貨物3.6有可能并到二次解線路1中，公里，考慮到單車載重量和線路 不能再增加送貨門店，為此連，需載重2噸的貨車3輛,4噸l-J,A-C,B-J,B-D,C-E,但這些連接已包含在配送8、下面的節約成本大小順序是A-I、E-F,由于門店A己組合到配送線路1中，該線路不再增加新門店，故不連接A-I;連接E-F并入配送線路2中，并取消0-E線路，此時配送線路共有 5條，如下圖所示。線路2的裝載量為3.3噸，運行成本為 29。此時，共有配送線路5條，總運行成本為 90的貨車2輛。9、按節約成本順序，接下來應該是線路1或2中，不能再組合成新的線路。再下來是 F-G,可組合在配送線路2中, 如下圖所示。此時，線路 2的裝載量為3.9噸，運行成本為30 ,這樣共有4條線 路，總成本為85 ,需載重2噸貨車2輛,4噸的貨車2輛。10、接下來的節約成本順序為G-H,由于受裝載量及線路里程的限制，不再組合到線路