`
shaojiashuai123456
  • 浏览: 262670 次
  • 性别: Icon_minigender_1
  • 来自: 吉林
社区版块
存档分类
最新评论

jsprit学习笔记

 
阅读更多

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

jsprit简介

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

基本概念

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

jsprit的结果(solution)结构如图 solution

Ruin And Rebuild流程

Rebuild流程

Rebuild流程

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

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方法 searchSolutions

例子程序

git示例程序

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

 

分享到:
评论

相关推荐

    Java学习笔记学习笔记

    Java学习笔记Java学习笔记Java学习笔记Java学习笔记Java学习笔记Java学习笔记Java学习笔记Java学习笔记Java学习笔记Java学习笔记Java学习笔记Java学习笔记Java学习笔记Java学习笔记Java学习笔记Java学习笔记Java学习...

    希沃白板学习笔记.pdf

    希沃白板学习笔记.pdf希沃白板学习笔记.pdf希沃白板学习笔记.pdf希沃白板学习笔记.pdf希沃白板学习笔记.pdf希沃白板学习笔记.pdf希沃白板学习笔记.pdf希沃白板学习笔记.pdf希沃白板学习笔记.pdf

    Springcloud学习笔记.md

    Springcloud学习笔记.md,Springcloud学习笔记.md,Springcloud学习笔记.md,Springcloud学习笔记.md,Springcloud学习笔记.md,Springcloud学习笔记.md,Springcloud学习笔记.md,Springcloud学习笔记.md,Spring...

    人工智能学习笔记,人工智能学习笔记

    人工智能学习笔记,人工智能学习笔记,人工智能学习笔记人工智能学习笔记,人工智能学习笔记,人工智能学习笔记人工智能学习笔记,人工智能学习笔记,人工智能学习笔记人工智能学习笔记,人工智能学习笔记,人工智能...

    云的学习笔记-云的学习笔记系统-云的学习笔记系统源码-云的学习笔记管理系统-基于ssm的云的学习笔记系统-ssm-java代码

    云的学习笔记-云的学习笔记系统-云的学习笔记系统源码-云的学习笔记管理系统-云的学习笔记管理系统java代码-云的学习笔记系统设计与实现-基于ssm的云的学习笔记系统-基于Web的云的学习笔记系统设计与实现-云的学习...

    云的学习笔记-云的学习笔记系统-云的学习笔记系统源码-云的学习笔记管理系统-基于Web的云的学习笔记系统设计与实现-java代码

    云的学习笔记-云的学习笔记系统-云的学习笔记系统源码-云的学习笔记管理系统-云的学习笔记管理系统java代码-云的学习笔记系统设计与实现-基于ssm的云的学习笔记系统-基于Web的云的学习笔记系统设计与实现-云的学习...

    CCNA学习笔记 CCNA学习笔记

    CCNA学习笔记 CCNA学习笔记 CCNA学习笔记

    nginx学习笔记(软件+学习笔记)

    nginx学习笔记(软件+学习笔记) 仅供学习交流! 后续会持续分享相关资源,记得关注哦! nginx学习笔记(软件+学习笔记) 仅供学习交流! 后续会持续分享相关资源,记得关注哦! nginx学习笔记(软件+学习笔记) ...

    2022吴恩达机器学习笔记汇总(共10章节).zip

    2022吴恩达机器学习笔记汇总(共10章节).zip2022吴恩达机器学习笔记汇总(共10章节).zip2022吴恩达机器学习笔记汇总(共10章节).zip2022吴恩达机器学习笔记汇总(共10章节).zip2022吴恩达机器学习笔记汇总(共10章节).zip...

    docker学习笔记.md

    docker学习笔记,docker学习笔记,docker学习笔记,docker学习笔记,docker学习笔记,docker学习笔记,docker学习笔记,docker学习笔记,docker学习笔记,docker学习笔记,docker学习笔记,docker学习笔记,docker学习笔记,...

    ssh学习笔记1 ssh学习笔记1

    ssh学习笔记1 ssh学习笔记1 ssh学习笔记1 ssh学习笔记1 ssh学习笔记1 ssh学习笔记1 ssh学习笔记1

    PHP个人学习笔记

    PHP个人学习笔记

    java学习笔记.zip

    java学习笔记java学习笔记.zipjava学习笔记.zipjava学习笔记.zipjava学习笔记.zipjava学习笔记.zipjava学习笔记.zipjava学习笔记.zipjava学习笔记.zipjava学习笔记.zipjava学习笔记.zipjava学习笔记.zipjava学习笔记...

    contiki 学习笔记

    Contiki学习笔记:进程、事件、etimer关系 Contiki 实例: Contiki学习笔记:创建两个交互进程 Contiki 主函数剖析: Contiki学习笔记:main函数剖析 Contiki学习笔记:启动一个进程process_start Contiki学习笔记...

Global site tag (gtag.js) - Google Analytics