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。每个任务都可以自定义装载维度、时间窗、需要的技能等，具体如下图所示。

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

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定义一种车辆类型，里面可以存放一些共用的属性。然后，对于每一辆车，我们也可以自定义它的出发位置、车型种类、拥有的技能、是否回到起始点等。

VehicleTypeImpl vehicleType = VehicleTypeImpl.Builder.newInstance("vehicleType")
          .addCapacityDimension(0,30).addCapacityDimension(1,100)
          .build();

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();

VehicleImpl vehicle2 = VehicleImpl.Builder.newInstance("vehicle2Id")
          .setType(vehicleType)
          .setStartLocation(Location.newInstance(5,0))
          .setReturnToDepot(false)
          .addSkill("loading bridge")
          .build();

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

VehicleRoutingProblem.Builder vrpBuilder =  VehicleRoutingProblem.Builder.newInstance();

vrpBuilder.addJob(service).addJob(shipment).addVehicle(vehicle1).addVehicle(vehicle2));

vrpBuilder.setFleetSize(FleetSize.FINITE);

VehicleRoutingProblem problem =  vrpBuilder.build();

第二步，生成算法。

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

VehicleRoutingAlgorithm algorithm = Jsprit.createAlgorithm(problem);

第三步，生成解。

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

Collection<VehicleRoutingProblemSolution> solutions = algorithm.searchSolutions();

VehicleRoutingProblemSolution bestSolution = Solutions.bestOf(solutions);

第四步，展示解。

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

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

//现实求解的结果详情
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的实现方法。

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')

相信大家一定理解了。

2.2.3 解读返回的JSON

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