什么是插入法

插入法又称“最远插入法”，原本是Mole和Jameson于1976年所提出，用于求解车辆路线问题（Vehicle Routing Problem,VRP）的方法，其结合最邻近法与节省法的观念，依序将顾客点插入路径中以构建配送路线。该方法首先将节省值的观念应用于循序路线建立上，首先以離场站最远的需求点作为路线的种子点，再根据最邻近点插入法的概念，以插入值最小者作为下一个插入点，最后再用一般化节省值公式，以其中节省值最大者來决定插入的位置，重复进行选取与插入的步骤，直到超过車辆容量或时窗限制时，再建立另一条路线。

Solomon于1983年将此方法应用于求解时窗限制车辆路线问题（vehicle routing problems with time windows，VRPTW），以时间及距離为标准的多重判断，挑选插入成本最小的顾客來插入路线中。因为时间因素加入，而使原问题的顾客的等待时间缩短。

Potvin和Rousseau(1993)发现平行插入法或循序插入法的使用时机，要随着问题的特性来决定，亦即顾客位置采群集(Cluster)分布或随机(Random)分布。

插入法的步骤

插入法包含二个步骤：

步骤1：选取距离配送中心最远的顾客点为起点，从其它剩余的顾客点中，根据最邻近法决定下一个被插入的顾客点。

步骤2：以节省法决定该顾客点应被插入的位置，在车辆容量限制下，重复进行选取与插入的步骤，当无法再扩大充路径时，则再建立另一路线，直至所有顾客都被排入路径中。

参考文献

1.0 1.1 1.2 夏新海.物流配送车辆调度优化研究.武汉理工大学,2004年

2.0 2.1 刘建宏.含时窗限制式卡车与拖车途程问题之研究(D).国立中央大学,2005年