-
時間節點
鎖定
時間節點是一個很抽象和應用很廣泛的概念,通俗的説就是某個大環境中的一個點或者一段,好比公交車線路中的一個站台。
- 中文名
- 時間節點
- 外文名
- time nodes
- 提出者
- 克拉克與懷特
- 提出時間
- 1964年
- 問 題
- 求解車輛巡迴問題
時間節點計算公式
此方法是克拉克(Clarke)與懷特(White)於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所示:
時間節點主要步驟
1、先以一部貨車負責一個客户,幾個貨車就負責幾位客户為條件,對於其路線的成本作其個別的運算,計算其個別成本。
2、將其路線組合後計算總成本後,將路線互相掉換。
3、通過上面二步,再進行一次運算,並統計所有的組合可能及結果,看其最低的成本路線是何解。