jsprit学习笔记--主要策略

jsprit的策略:

(1)ruin (破坏）

a.随机破坏 (RuinRadom.java) , 随机删除路径上的节点

b.最差破坏 (RuinWorst.java) , 选取代价最大的n个节点

c.聚类破坏（RuinClusters.java) 通过ruin/DBSCANCluster.java计算聚类距离, 逻辑：循环10次，对于一个路线，选集选择2个节点，查看距离，计算平均距离和最小距离，距离半径=（平均距离-最小距离）*(0.5+random(0,1)) , 聚类某辆车的节点，删除某个聚类所有节点

注意:Jsprit.java中对 聚类策略 进行了jobneighborhoods的初始化, 计算每个节点，距离最近的n个节点

 

(2)recreate (恢复)

a. 单点最优恢复 (BestInsertion.java)

   首先根据节点的优先级排序

  对于一个节点,根据 "节点位置选取" 逻辑，选取最优位置

  选取最优的位置插入该节点

  执行插入操作

b.全局最优恢复(RegretInsertion.java)

  遍历每个节点

  对于一个节点，根据 "节点位置选取"逻辑，选取最优位置和次优位置

  对于一个节点，根据score.java中的公式，计算插入的打分

  把所有节点都查看一遍后，得到打分最高的插入节点和位置

  执行插入操作

(3)acceptor (接受新解)

               

节点位置选取

  VehicleTypeDependentJobInsertionCalculator.java

  如果插入的路线有车辆，则使用此车辆,如果支持切换车，使用其他车型车辆

  如果插入的车辆是空车，则拿出所有可用车辆

  遍历所有车辆， 在ServcieInsertionCalculator.java中，对待插入节点，进行限制判断，查看是否可以插入

  找到打分最高的的插入位置并返回