節約里程法

節約里程法是用來解決運輸車輛數目不確定的問題的最有名的啟發式算法。又稱節約算法或節約法，可以用並行方式和串列方式來最佳化行車距離。

基本介紹

• 中文名：節約里程法
• 別稱：節約算法或節約法
• 作用：解決運輸車輛數目不確定的問題
• 類型：啟發式算法

核心思想

節約里程法核心思想是依次將運輸問題中的兩個迴路合併為一個迴路，每次使合併後的總運輸距離減小的幅度最大，直到達到一輛車的裝載限制時，再進行下一輛車的最佳化。最佳化過程分為並行方式和串列方式兩種。

基本規定

利用節約法確定配送路線的主要出發點是，根據配送中心的運輸能力和配送中心到各個用戶以及各個用戶之間的距離來制定使總的車輛運輸的噸公里數最小的配送方案。另還需滿足以下條件；（1）所有用戶的要求；（2）不使任何一輛車超載；（3）每輛車每天的總運行時間或行駛里程不超過規定的上限；（4）用戶到貨時間要求。

基本思想

為達到高效率的配送，使配送的時間最小距離最短成本最低，而尋找的最佳配送路線。

典型例題

例題：已知配送中心P0向5個用戶Pj配送貨物，其配送路線網路、配送中心與用戶的距離以及用戶之間的距離如下圖所示，配送中心有3台2t卡車和2台4t兩種車輛可供使用。利用節約里程法制定最優的配送方案。

節約里程法例題用圖

第一步，作運輸里程表，列出配送中心到用戶及用戶間的最短距離。

第二步，按節約里程公式求得相應的節約里程數。

第三步，將節約里程按從大到小順序排列。

第四步，根據載重量約束與節約里程大小，順序連線各客戶結點，形成兩個配送線。

P2P3－P3P4－P2P4－P4P5－P1P2－P1P5－P1P3－P2P5－P3P5－P1P4

得出結果：

配送線路一：

運量=1.7+0.9+1.4=4t

運行距離=8+4+5+7=24km

用一輛4t車運送，節約距離為18km

配送線路二：

運量=2.4+1.5=3.9t<4t

運行距離=8+10+16=34km

用一輛4t車運送，節約距離為2km

初始方案：配送線路5條，需要車5輛，配送距離=39*2=78km

最佳化後的方案：2條配送路線,2輛4t車，配送距離=24+34=58km