插入法 发表评论(0) 编辑词条

插入法（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：选取距离配送中心最远的顾客点为起点，从其它剩余的顾客点中，根据最邻近法决定下一个被插入的顾客点。

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