節省法

出自 MBA智库百科(https://wiki.mbalib.com/)

節省法（Saving Method）

　　克拉克（Clarke）與懷特（Wright）於1964年提出該方法以求解車輛巡迴問題，其思想在於按節省值（較短路徑與原路徑之差）由大至小排序，在車輛容量限制下，依序將對應的兩顧客點排入路徑中，直至所有顧客都被排入路徑為止。該方法的實質要求就是節省路線成本。

　　節省法是記憶保持量測量實驗方法。德國心理學家艾賓浩斯創製。具體做法是： 首先讓個體學習某種材料(如無意義音節)到恰好能背誦的程度，這時停止學習並記下所用的時間;間隔一段時間後，再讓個體重新學習同樣的材料，同樣也是在達到恰好能背誦的程度時停止學習，再次記下所用的時間;最後，比較兩次學習所用的時間(或學習次數)，通過公式計算個體的記憶保持量，即節省分數。

　　Solomon於1983年將此法應用於求解時間窗約束的車輛巡迴問題，關鍵在於當節省值較大的兩顧客點被排入路徑時，除需考慮車輛容量限制外，更需要考慮到時間窗的限制，也就是時間窗上界較早者，應優先被配送，並檢驗其時間可行性，此方法的優點是提高車輛的利用率，而兩節點間的節省值的計算公式與意義如下所示：

　　s(i,j)= d(i,0)+ d(0,j)− d(i,j)

　　其中d(i,0)代表顧客i至場站的距離，d(i,j)則代表顧客i至j的距離。計算兩節點i與j間的節省值s(i,j)時，應先計算原路徑中各往返路徑的總和，再以之與較短路的總路徑和相比較；兩節點的原路徑與較短路，如下圖所示：

　　1、先以一部貨車負責一個客戶，幾個貨車就負責幾位客戶為條件，對於其路線的成本作其個別的運算，計算其個別成本。

　　2、將其路線組合後計算總成本後，將路線互相掉換。

　　3、通過上面二步，再進行一次運算，並統計所以的組合可能及結果，看其最低的成本路線是何解。