插入法

1.什么是插入法

插入法又称“最远插入法”,原本是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]

2.插入法的步骤[1]

插入法包含二个步骤:

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

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