jsprit学习笔记

转载：https://my.oschina.net/u/3173942/blog/1572842

jsprit简介

jsprit是一个开源的解决VRP（车辆路径问题）问题的工具，其中主要使用的是Ruin And Rebuild算法。

基本概念

jsprit中包含几个基本的概念，包括车辆，车辆类型等，以及他们能挂载的诸多属性。 

jsprit的结果（solution）结构如图 

Ruin And Rebuild流程

Rebuild流程

1. 选取现在还未分配的一个服务点
2. 尝试加入每个完整路径中
3. 在每个完整路径中选取一段路径进行插入
4. 比较插入后新增的路径和原始段中路径的长度差
5. 选取一个增量最小的位置返回该位置的增量
6. 全局比较（所有路径中的所有可能插入的段）哪一段路径增量最小，则插入此段

Ruin流程

1. 随机选取一个ruin策略（例如邻近的n个点，开销最大的点等），此处以邻近点为例
2. 随机选取一个服务点，随机产生一个随机数n
3. 将此服务点相邻的n个点进行释放，重新进入未分配的服务店队列

扩展点

1. HardRouteConstraint接口,其中的fulfilled返回一个boolean值，判断服务点是否能进入当前路径。

实现类

• ServiceLoadRouteLevelConstraint(计算capacityDimensions是否满足需求)
• HardSkillConstraint(判断是否有对应的skill)

1. JobUnassignedListener接口,其中的informJobUnassigned方法能获取到服务点未进入路径的原因

tips: jpsrit只会收集到全部的失败原因，而不是针对某一次solution或者某个route的

1. ActivityInsertionCostsCalculator接口,其中的getCosts返回一个double，影响某个服务加入某段路径中的消耗

实现类

• LocalActivityInsertionCostsCalculator(计算新增点增加的开销)

1. SolutionCostCalculator接口,其中的getCosts返回一个double，设置整个solution的开销为整个double值。会影响最后选取的最优结果

实现类

• 在Jsprit.class中的getObjectiveFunction方法中有一个匿名内部类实现，用来计算solution的开销

泳道图

VehicleRoutingAlgorithm中的searchSolutions方法 

例子程序

git示例程序

其中的jsprit模块为例子程序，主要是VrpCore类，直接执行单元测试就可以了。 JspritUtil则是很早之前的一个case，可以不用看。