例題

已知配送中心P0向5個用戶Pj配送貨物，其配送路線網(wǎng)絡、配送中心與用戶的距離以及用戶之間的距離如圖所示。圖中括號內(nèi)的數(shù)字表示客戶的需求量(單位：T),線路上的數(shù)字表示兩結點之間的距離，配送中心有2T卡車和4T兩種車輛可供使用，試利用節(jié)約里程法制定最優(yōu)的配送方案。

解題步驟

1.計算網(wǎng)絡結點之間的最短距離。

2.計算節(jié)約里程（根據(jù)最短距離結果，計算出各用戶之間的節(jié)約里程）。例：P1P2之間的節(jié)約里程=P0P1+P0P2-P1P2=8+8-12=4

3.將節(jié)約里程進行分類，按從大到小的順序排列。

4.確定單獨配送線路，按節(jié)約里程大小排序，組成線路圖。

（1）初始方案：如圖示：從配送中心P0分別向各個客戶進行配送，對每一客戶分別單獨派車送貨，共有5條線路，總行程39*2=78公里，需2t貨車4輛，4t貨車1輛。

（2）修正方案1。按照節(jié)約里程由大到小的順序，連接P2，P3，P4，形成巡回路線P0-P2-P3-P4-P0的配送線路，如圖所示，共有3條配送線路，總行程為（8+4+5+7）+（10+8）*2=60，需要兩輛4t車，一輛2t車。

（3）修正方案2。按照節(jié)約里程由大到小的順序，連接P1.P5,形成巡回線路P0-P1-P5-P0的配送線路，如圖所示，共有2條配送線路?？傂谐虨椋?+4+5+7）+（8+10+16）=58，需要兩輛4t車。

5.最終配送線路方案：

A:P0-P2-P3-P4-P0

B:P0-P1-P5-P0

運輸總距離：

S=S(A)+S(B)=(4+5+7+8)+(10+8+16)=58

運量：

Q(A)=Q2+Q3+Q4=1.7+0.9+1.4=4t

Q(B)=Q5+Q1=2.4+1.5=3.9t

節(jié)省總里程：

10+8+2=20