插入法
用手机看条目
出自 MBA智库百科(https://wiki.mbalib.com/)
插入法（Insertion Method/Insert Method)）
目錄 |
[編輯]
插入法又稱“最遠插入法”，原本是Mole和Jameson於1976年所提出，用於求解車輛路線問題（Vehicle Routing Problem,VRP）的方法，其結合最鄰近法與節省法的觀念，依序將顧客點插入路徑中以構建配送路線[1]。該方法首先將節省值的觀念應用於循序路線建立上，首先以離場站最遠的需求點作為路線的種子點，再根據最鄰近點插入法的概念，以插入值最小者作為下一個插入點，最後再用一般化節省值公式，以其中節省值最大者來決定插入的位置，重覆進行選取與插入的步驟，直到超過車輛容量或時窗限制時，再建立另一條路線。
Solomon於1983年將此方法應用於求解時窗限制車輛路線問題（vehicle routing problems with time windows，VRPTW）[1]，以時間及距離為標準的多重判斷，挑選插入成本最小的顧客來插入路線中[2]。因為時間因素加入，而使原問題的顧客的等待時間縮短。
Potvin和Rousseau(1993)發現平行插入法或循序插入法的使用時機，要隨著問題的特性來決定，亦即顧客位置採群集(Cluster)分佈或隨機(Random)分佈[2]。
[編輯]
插入法的步驟[1]
插入法包含二個步驟：
步驟1：選取距離配送中心最遠的顧客點為起點，從其它剩餘的顧客點中，根據最鄰近法決定下一個被插入的顧客點。
步驟2：以節省法決定該顧客點應被插入的位置，在車輛容量限制下，重覆進行選取與插入的步驟，當無法再擴大充路徑時，則再建立另一路線，直至所有顧客都被排入路徑中。
[編輯]
