前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Jsprit和自研车辆路径规划求解器的介绍

Jsprit和自研车辆路径规划求解器的介绍

作者头像
用户1621951
发布2022-08-25 20:05:31
2.3K0
发布2022-08-25 20:05:31
举报
文章被收录于专栏:数据魔术师

前言

哈啰,又见面啦

大家在编写启发式算法程序解决NP难问题时

有没有觉得会很耗时间呀

今天小编给大家介绍

两个可以解决各类VRP问题的工具(即VRP求解器)

一起来看看吧

1 求解器介绍

1.1 Jsprit

1.1.1 Jsprit简介

Jsprit 是一个基于 java 的开源工具包,用于解决旅行商问题 (Traveling Salesman Problem,简称TSP) 和多种车辆路径问题(Vehicle Routing Problem, 简称VRP)。Jsprit是轻量级、灵活且易于使用的VRP求解工具,其基于一个通用的元启发式(meta-heuristic)算法框架。

其实,以前数据魔术师早就有推文介绍过Jsprit这个工具啦,想了解的童鞋可以看看:车辆路径优化问题求解工具Jsprit的简单介绍与入门。这篇推文小编觉得已经讲得非常详细、非常全面了。但是为了统一,小编这次也会简单地再次介绍一下这个工具。

Jsprit官方网站与下载地址:

http://jsprit.github.io/

https://github.com/graphhopper/jsprit/

1.1.2 Jsprit可以解决的车辆路径规划问题

根据官网介绍,Jsprit可以解决:

1、带容量限制的VRP(Capacitated VRP)

2、多场站VRP(VRP with Multiple Depots)

3、带时间窗的VRP(VRP with Time Windows)

4、带回程的VRP(VRP with Backhauls)

5、多车型VRP(VRP with Heterogeneous Fleet)

6、取送货VRP(VRP with Pickups and Deliveries) 

7、时间依赖型VRP(Time-dependent VRP)

8、旅行商问题(Traveling Salesman Problem)

9、Dial-a-Ride问题(Dial-a-Ride Problem)

1.1.3 其他特点

• 众多依赖包导入,可能对新手不友好;

• 需要编程基础;

• 模块化工具,构造问题方便易懂;

• 强大的可视化工具。

强悍的可视化工具

1.2 团队自研VRP求解器

1.2.1 自研求解器简介

此求解器由华中科技大学秦虎教授和南京大学罗志兴副教授共同研发,可用于求解多种车辆路径问题、三维装箱问题以及这两个问题的结合问题。在保障高效的性能同时,自研求解器提供丰富的接口方便用户实现自定义的约束条件和目标函数,做到了性能、通用性、拓展性之间的平衡

目前自研求解器尚未对外公开(如需试用请联系秦虎教授),但是通过小编的讲解,相信大家也能掌握大致的使用方法。

1.2.2 自研求解器可以解决的问题

主要是针对车辆路径问题和装箱问题这两大问题,具体的细分问题在github上没有明确的给出;但是根据其帮助文档提供的可用约束来看,小编估计这个求解器应该可以涵盖几乎所有车辆路径问题和装箱问题,包括但不限于jsprit可以解决的问题。很多Jsprit无法解决的车辆路径规划问题,自研VRP Solver可以解决;并且,对新场景下的车辆路径规划问题,可以基于自研VRP Solver预留的接口来做定制化开发

1.2.3 算法特点

求解速度快

自研车辆路径优化求解器集成了多种元启发式算法(meta-heuristics)框架,内嵌了多种不同维度的、高效率的、高质量的搜索算子(operators)。自研求解器不断地被改进迭代,随着客户需求不断地进化。在元启发式算法的基础上,使用了前缀运算、哈希映射、动态规划等高效率的改进方法,算法运行速度极快,可以在非常理想的时间内得到优异的计算结果。

通过模拟多种需求场景,对大量规模不等的算例进行测试后的结果表明:对于小规模算例,此算法的运行时间可以达到秒级,甚至毫秒级;对于大规模算例,运行时间也可以达到在数分钟之内。

拓展性能强

自研VRP Solver适用于大量的应用场景,拓展性强,主要体现在两方面:

(1)支持约束条件和目标函数的拔插

算法会根据约束条件和目标函数的不同,在计算中进行相关变量和条件的拔插。大大减少了不必要的变量迭代,降低了程序的计算压力,提升了整体的性能。

(2)允许用户根据需要实现自定义约束条件和目标函数

出于对用户需求多样性和随机性的考虑,算法不仅支持多种优化目标、约束条件的任意组合,其中包括但不限于容量约束、时间窗约束、运行时间约束等等,还支持用户自定义约束条件和目标函数。用户可以根据实际需求对约束条件和目标函数进行自定义,进而获得优质的解决方案。

解的质量高

自研VRP Solver所获得的解的质量比较高。在后面的推文中,我们也会将Jsprit和自研VRP Solver的解进行性能比较。

具体而言,对于一个给定的车辆路径优化问题,自研VRP Solver能够做到:用户根据给定的格式规范输入一定的参数、数据,指明所求解问题的优化目标、约束条件后,经过调用自研VRP Solver,在较短的时间内输出一个质量极高的路径规划方案。其中,约束条件可以和优化目标任意组合,以构建出所期望的应用场景。

1.2.4 其他特点

• 使用json上传数据

• 数据格式简单,基本一看就懂

• 不需要编程基础

• 云端计算

没错,我们自研VRP Solver的使用完全不需要编程基础,包你一看就会哦。

2 工具使用

2.1 Jsprit的使用(JAVA)

2.1.1 资源导入

Jsprit和外部依赖库的资源还是找以前的推文哦,小编就是从那里下载的。

车辆路径优化问题求解工具Jsprit的简单介绍与入门

因为使用的是JAVA语言,所以推荐使用Idea或eclipse作为IDE。之前那篇推文使用的是eclipse来进行导入演示的,那这次小编就展示一下Idea的操作吧。

• 首先,依次点击File-open,选择Jsprit的源代码,然后再点击OK就可以了。

• 下一步就是外部依赖包的引入了,依次点击File-Project Structure

• 进入界面,点击左边的Library,再次点击左上角的+号

• 然后在跳出来的界面选择java

• 在跳出的界面中,选择外部数据库里的jar包,然后点击OK就可以啦。可以按住ctrl按钮一次性选择多个jar包哦。

2.1.2 编写代码

代码的编写大家可以参考Jsprit的官网,和以前的那篇推文。小编就根据官网和之前推文的程序谈谈自己的理解吧。

http://jsprit.github.io/

车辆路径优化问题求解工具Jsprit的简单介绍与入门

第一步,构建问题。

首先是要描述任务类型,Jsprit提供了两种,分别是涉及1个节点的Service和涉及两个节点的shipment。每个任务都可以自定义装载维度、时间窗、需要的技能等,具体如下图所示。

代码语言:javascript
复制
Service service =  Service.Builder.newInstance("serviceId")
          .setName("myService")
          .setLocation(Location.newInstance(5,7))
          .addSizeDimension(0,5).addSizeDimension(1,20)
          .addRequiredSkill("electric drill")
          .setTimeWindow(TimeWindow.newInstance(20,35))
          .build();// specify shipment - which involves two stops
代码语言:javascript
复制
Shipment shipment = Shipment.Builder.newInstance("shipmentId")
          .setName("myShipment")
          .setPickupLocation(Location.newInstance(2,7)).setDeliveryLocation(Location.newInstance(10,2))
          .addSizeDimension(0,9).addSizeDimension(1,50)
          .addRequiredSkill("loading bridge").addRequiredSkill("electric drill")
          .build();

接着需要描述车型。

首先我们可以使用vehicleType定义一种车辆类型,里面可以存放一些共用的属性。然后,对于每一辆车,我们也可以自定义它的出发位置、车型种类、拥有的技能、是否回到起始点等。

代码语言:javascript
复制
VehicleTypeImpl vehicleType = VehicleTypeImpl.Builder.newInstance("vehicleType")
          .addCapacityDimension(0,30).addCapacityDimension(1,100)
          .build();
代码语言:javascript
复制
VehicleImpl vehicle1 = VehicleImpl.Builder.newInstance("vehicle1Id")
          .setType(vehicleType)
          .setStartLocation(Location.newInstance(0,0)).setEndLocation(Location.newInstance(20,20))
          .addSkill("loading bridge").addSkill("electric drill")
          .build();
代码语言:javascript
复制
VehicleImpl vehicle2 = VehicleImpl.Builder.newInstance("vehicle2Id")
          .setType(vehicleType)
          .setStartLocation(Location.newInstance(5,0))
          .setReturnToDepot(false)
          .addSkill("loading bridge")
          .build();

最后,初始化问题构造器,并把上述内容都添加进问题的构造器中。通过构造器,我们可以设置路线的花费类型(如欧几里得还是曼哈顿距离),也可以定义车辆数量是否拥有上限。

代码语言:javascript
复制
VehicleRoutingProblem.Builder vrpBuilder =  VehicleRoutingProblem.Builder.newInstance();
代码语言:javascript
复制
vrpBuilder.addJob(service).addJob(shipment).addVehicle(vehicle1).addVehicle(vehicle2));
代码语言:javascript
复制
vrpBuilder.setFleetSize(FleetSize.FINITE);
代码语言:javascript
复制
VehicleRoutingProblem problem =  vrpBuilder.build();

第二步,生成算法。

Jsprit可以通过问题自动构建合适的算法,构建过程如下。

代码语言:javascript
复制
VehicleRoutingAlgorithm algorithm = Jsprit.createAlgorithm(problem);

第三步,生成解。

然后可以在此基础上找到候选解中的最优解。

代码语言:javascript
复制
Collection<VehicleRoutingProblemSolution> solutions = algorithm.searchSolutions();
代码语言:javascript
复制
VehicleRoutingProblemSolution bestSolution = Solutions.bestOf(solutions);

第四步,展示解。

得到解之后,可以调用一些方法来展示解。

首先是这个SolutionPrinter.print()方法,可以展示所有路线的具体情况,比较细节。

代码语言:javascript
复制
//现实求解的结果详情
SolutionPrinter.print(problem, bestSolution, SolutionPrinter.Print.VERBOSE);

然后,借助Plotter和GraphStreamViewer这两个工具,可以对得到的解进行可视化的展示。

Plotter输出:

GraphStreamViewer输出(动态):

2.2 自研VRP Solver的使用(基于JSON)

这次小编将会以CVRP为例,向大家展示自研求解器的使用方法。

2.2.1 编写json文件

相比于Jsprit来说,自研求解器的封装程度更高。具体在使用方面,使用者不需要编程基础;而只要将VRP问题编写成一个JSON文档就可以了。我们来看看JSON文件的格式吧:

调用车辆路径问题求解器的json由以下部分组成,打星号的是有默认值,不是必须填的:

• Data: 数据容器。

• Parameter: 算法参数。

• Constraint: 问题约束条件和目标函数列表。

• ConstructionOperator: 构造初始解算子。

• Greedy: 提供可用的车辆信息。

• LocalSearchOperator: 邻域搜索算子。

• VehicleReductionOperator*: 减少车辆数量算子。

• InitialSolution*: 指定的初始解,既可以是一个完整的合法解,也可以是一个部分合法解。

• Nodes: 指定的初始解中尚未服务的顾客节点,假如InitialSolution未指定,则Nodes包含所有需要被服务的顾客节点。

• Algorithm*:指定求解器运行的算法,如果缺省,则采用默认算法。

• GateAssign*:将路径分配给仓库月台算法。

下面就跟着小编一起来看看,

如果是一个简单的CVRP问题,

那么JSON文件要如何来编写吧。

总的来说,一个简单的CVRP问题由以下几部分组成。

Data

顾名思义,Data里存放的就是后面会使用到的数据,主要是大段的数据或者是重复使用的数据,这可以增加代码的复用性和美观。

如图,在本次的Data中,嵌套着4个内容。“NumberOfNodes“指的是节点总数;“NumberOfVehicles”指车型种类数目;”DoubleArrays“指浮点数组;”DoubleMatrices“指浮点矩阵。

而这些数组或矩阵都会被”0“、”1“这样的数字标识,在后面的代码中,输入对应的数字就可以调用这些Data数据,这在后面还会再提到。

Parameter

这里主要存放着一些求解时的参数,不填就是默认值,这里我们可以先不填它。

如果没有必要其实不用改!

Constraints

顾名思义,这里就是放约束条件的地方啦,其实目标函数也是放在这里。

这次我们放了一个容量约束和一个最短路径的目标,“Name”指约束或目标函数的名字;

然后“NumberOfNodes”与“NumberOfVehicles”的意思是和上面Data一样的,咦,为什么要再写一遍?

没错,因为可以只针对部分节点进行约束。

在本次调用方法中,“Demands”是数组,记载每个节点的货物需求;“Capacities”这里也是数组,记载每个车型的容量;“DistanceMatrix”是矩阵,记载每个节点之间的距离,大小为N*N。

然后我们可以看到,“Demands”、“Capacities”、“DistanceMatrix”的右边都只写了一个数字,这就是上面提到的调用方法,这里根据自身的数据格式(数组还是矩阵)调用数字所对应的Data内容

还剩一个“UnitCosts”指的是每个车型每单位距离的花费,这里只有一辆车,单位花费为1。

我们自研求解器支持的约束有多少呢?

截张图感受一下

后面还有很多哦,这里就不占过多的篇幅了。

ConstructionOperator

这是用来设置构造初始解的算子。这在帮助文档中已经写得很明白了。

这里“NumberOfNodes”可以省略,默认节点全选。

Greedy

用来提供可用的车辆信息。主要内容是一共用了几种车、几个仓库、每辆仓库所使用的车辆种类、数目等等。

“LocalSearchOperator”

是指邻域搜索算子,可以是很多邻域搜索算子的组合。这方面不同的搭配可能会影响到后续的解,所以一定要多多尝试。

如图,调用方法比较简单

目前求解器支持的邻域搜索算子如下。

“Nodes”

顾名思义,就是用来存放节点的设置的。

这里我们只用写Customers的部分就够了,代表需要服务的客户节点。

好了,以上就是一个普通的CVRP问题的Json格式,相信大家对于Json文件的编写格式已经有了大致的了解。

2.2.2 使用网站api上传json文件

接着,我们可以通过pow、postman等软件工具(小编这次使用的是postman),将我们写好的json文件post到一个网站接口。目前,这个网站地址还尚未公开。

图为postman软件的界面,这个软件可以完成对网站的一系列请求。

• 首先点击左上角的小三角,将请求设为“POST”;

• 然后依次点击下方的Body、raw,将右边的文件格式改为JSON

• 接着将json文件内容复制到body中后,点击“send”按钮,我们的代码会在服务端被解释、处理、最终以json代码的形式把得出的解返回给我们。

怎么样?

是不是很方便呢。

小编补充一下,其实使用网站的api也可以不靠这些软件的帮助,完全是可以自己用代码实现的,这里小编就展示下用Python的实现方法。

代码语言:javascript
复制
import requestsimport jsonimport os
def get_json(filename):    # 以可读形式打开文件    with open(filename, 'r') as f:        # 读取这个文件中的所有内容,并且读取的结果返回为python的dict对象        input_json = json.load(f)        # json.dumps()将一个Python数据结构转换为JSON        input_json = json.dumps(input_json)        # 填写请求包的头部信息        headers = {'Content-type': 'application/json'}        # 使用requests模块发送 HTTP 请求,这里是post请求        r = requests.post("http://localhost/vrp/", data=input_json, headers=headers)        # 将返回的json转为字符串        r_json = str(r.json())        print(r_json)        # eval()函数用来执行一个字符串表达式,并返回表达式的值,这里应该是转化为一个字典        r_json = eval(r_json)        # 为输出结果创建文件并命名        output_file_name_list = filename.split('/')        output_file_name = output_file_name_list[0] + '/output/' + output_file_name_list[2].replace('.json',                                                                                                    '_output.json')        with open(output_file_name, 'w') as fw:            fw.write(json.dumps(r_json, indent=2))

if __name__ == '__main__':    '''    os.walk()方法用于通过在目录树中游走输出在目录中的文件名    下面的参数"B-VRP/input"是要遍历的目录的地址, 返回的是一个三元组(root,dirs,files)。  root 所指的是当前正在遍历的这个文件夹的本身的地址      dirs 是一个 list,内容是该文件夹中所有的目录的名字(不包括子目录)    files 同样是 list,内容是该文件夹中所有的文件(不包括子目录)    '''    g = os.walk("B-VRP/input")    for path, dir_list, file_list in g:        for file_name in file_list:            final_path = os.path.join(path, file_name)  # 连接路径名            print(final_path)            get_json(final_path)    # get_json('/Users/graham/Downloads/B-n31-k5.json')
代码语言:javascript
复制

相信大家一定理解了。

2.2.3 解读返回的JSON

我们还是以之前的CVRP问题为例,讲讲返回回来的Json各个参数的含义。CVRP问题返回的Json文件主要有4部分。

• “Feasibility”告诉你这个问题是否是可解的,一般是True。

• “NumberOfRoutes”指路线数量。

•“Cost”是指的总花费,而因为我们之前设置的单位路程花费为1,因此这里就是总路程。

• “Routes”包含所有车的路线数据,每辆车的路线数据又是由以下部分组成的。

这里我们只有一条路线

• "VehicleIndex":车辆编号;

• “Type”:车辆种类,这里因为小编只用了一种车型,因此这个参数没有意义;如果问题中有多种车型的话,这里也会显示相应的车型编号。

• “TripIndex”:路线编号;

• “Constraints”:保存着本路线的约束与目标函数。

这里的参数前面大都提到过,唯一不一样的是Sequence,它保存的是车辆行驶过程中的情况。

对于“CapacityConstraint”来说,保存的是车辆的累计装载量“Load”,本次装载数量“Number”,以及本次经过的节点“ID”。

这次测试我们每个节点只有一件货物

因此“Number”参数没有意义

如果每个节点有多件货物的话

这里会显示相应的货物件数

对于“MinimizeDistance”来说,Sequence这里保存的是本次到访的节点编号“ID”、累计花费“Cost”、累计距离“Distance”

由于在输入Json中

我们设置车辆单位距离花费为1

因此这里“Cost”和“Distance”的数量是一样的

•“NumberOfNodes”:路线经过的节点数,咦,记得之前在输入Json时一共31个节点,怎么这里经过了38个节点?我们先看看后面。

• “Sequence”:点开Sequence内容,这里保存的是本路线依次经过的节点。

我们可以发现,原来我们的仓库节点被反反复复经过了好几次,原来这些点都算在了“NumberOfNodes”经过的节点数中。

• “Split”:表示客户节点的需求是否可拆分,这里是“False”,表示不可拆分,也就是一个客户节点的需求要被一辆车一次性满足。

本次测试我们只使用了一辆车、一条路线,这是因为之前在“Parameter”参数设置中,小编将“multitrip”设置为了True。

如果这里改成False的话,相当于“True”情况里每返回一次仓库就算是一段新路线了。有兴趣的同学可以自己试试呀。

小结

通过上述内容,相信大家对于这两个求解器也有了一定的理解。讲了这么多,小伙伴们是不是也想知道这两个求解器的性能到底孰优孰劣呀。后面推文我们将进行Jsprit与自研求解器关于VRPTW问题求解的比较,敬请期待。

小编特意准备了一个CVRP算例的输入输出的jason文件。

有兴趣的小伙伴可以移步留言区获取下载方式。

END


文案:王金远(华中科技大学管理学院本科一年级)

指导老师:秦虎老师(华中科技大学管理学院)

排版:程欣悦

如对文中内容有疑问,欢迎交流。PS:部分资料来自网络。


如有需求,可以联系:

秦虎老师(华中科技大学管理学院,tigerqin1980@qq.com)

王金远 (华中科技大学管理学院本科一年级,1002448017@qq.com)

程欣悦(1293900389@qq.com)

欢迎大家加入数据魔术师粉丝群,我们的活动将会通过粉丝群优先发布, 学习资料将通过粉丝群分享。

欲入群,请转发此文,然后扫描下方二维码联系数据魔术师小助手

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-08-16,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 数据魔术师 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
容器服务
腾讯云容器服务(Tencent Kubernetes Engine, TKE)基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务,覆盖 Serverless、边缘计算、分布式云等多种业务部署场景,业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者,主导开源项目Crane,全面助力客户实现资源优化、成本控制。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档