车辆路径优化问题求解工具Jsprit的简单介绍与入门
今天小编要为大家介绍一款用于求解车辆路径优化问题（VRP）的工具箱---jsprit。大家可能没听过这个求解工具，小编也是经老师介绍才知道的。这里可以偷偷的告诉大家，老师的团队正在开发一款更厉害的车辆路径优化问题的求解器，将来会与Jsprit做性能比较。大家可以期待一下我们自己的车辆路径优化问题的求解器哦！
jsprit是Github上的一个开源项目，由Stefan Schröder所创建并由GraphHopper主持。这两位发现在车辆路径规划问题应用如此广泛的情况下，极少有开源的工具能够帮助解决带有不同约束的车辆路径规划问题，于是他们就创建并完成了这个项目。
Jsprit是一个开源的工具箱，提供用于求解VRP的工具，基于元启发式算法（meta-heuristics）。
什么是元启发式算法呢？元启发式算法是指一类基于直观或者经验构造的算法，它可以在可接受的花费（指时间或空间）下给出问题一个可行解。许多启发式算法是针对或者是依赖于某一个特定问题的，而元启发式算法则是一些比较通用的启发式策略,通常不借助于某个问题特有的条件，将局部搜索和随机相结合。我们介绍过的蚁群算法、模拟退火算法、遗传算法等都属于元启发式算法。
之所以要做这个背景介绍就是为了告诉大家jsprit不保证能得到最优解。接下来小编将从功能、安装使用、求解性能和质量几个方面为大家简单地介绍这款工具箱。
Jsprit官网： http://jsprit.github.io/ https://github.com/graphhopper/jsprit
01
Jsprit能干什么
据官网介绍，jsprit能够解决下列问题：
- 带容量限制的VRP(Capacitated VRP)
- 多场站VRP(VRP with Multiple Depots)
- 带时间窗的VRP(VRP with Time Windows)
- 带回程的VRP(VRP with Backhauls)
- 多车型VRP(VRP with Heterogeneous Fleet)
- 取送货VRP(VRP with Pickups and Deliveries)
- 时间依赖型VRP(Time-dependent VRP)
- 旅行商问题(Traveling Salesman Problem)
- Dial-a-Ride问题(Dial-a-Ride Problem)
除了以上问题外，jsprit还支持以上问题的混合。jsprit作为一个模块化的工具箱，方便之处在于，这个工具箱求解是通过core模块里的一些组件来构建整个VRP以及构建问题的组成元素，例如一个基本的车辆路径规划问题的代码里有仓库、车辆、客户点这几个元素，那么构造器会把这些元素一个一个构造出来，通过问题的构造器把这些元素加入到这个问题里面，并且告知构造器用这些元素构造一个车辆路径规划问题的代码。
为什么说这样方便使用呢？
一个基本的车辆路径规划问题的代码里面，客户点的属性可能只有坐标和需求量。换句话说，构造器在构造这个客户点的时候，仅仅设置了这个客户点的坐标和需求量，但是除此之外，我们还可以为这个客户点设置一个时间窗，设置服务时间以及设置客户点的服务优先级等等，通过这样对客户点的设置就能够满足不同的问题的需求。同理，对于车辆而言，我们可以用循环语句构建一百个车辆实例存到数组里面。如果要求解一个多车型问题，我们在构造这些车辆的时候设置好不同车型的参数就可以了。
而对于整个问题的约束条件，在问题的构造器里面也可以设置，例如设置总的服务时间，设置是否带有回程等等。
简单地说就是构造器既能够实例化一个个元素，也能设置和修改这些元素的属性从而能够满足不同问题的约束条件，这也就是为什么它能够支持以上问题的混合。
小编实践后发现，这个工具箱除了上手快，使用方便以外，对于解的可视化也做得很好，能够非常详细和直观地表达解的情况和结果。
02
如何使用Jsprit
Jsprit有三个比较核心的部件，分别是jsprit-core、jsprit-analysis、jsprit-io
jsprit-core从名字上我们就可以知道这个绝对是核心中的核心，里面包含了一些构造器。
jsprit-analysis提供了将求解的结果进行可视化的工具箱，主要依赖于jfree绘图并通过graphstream进行图形流的处理和展示。这两个都是免费的工具，需要到网上下载响应版本的jar包并在项目里加载，后续会给大家介绍。
jsprit-io则是对求解的过程等进行记录和输出。
此外还有jsprit-instances和jsprit-examples，这两部分我们在自己求解问题的时候并不需要用到，但是在学习的时候能够给我们一些帮助。
jsprit-instances里面有两个部分，一个是instance，另一个则是读取算例的代码，存放在一个src文件夹中。instance里面有不同约束的VRP的一些经典算例，基本都是txt格式的文件，而src文件夹里面则是一些代码，这些代码的作用是创建一个构造器然后读入instance里面的算例，构造算例里面的元素。大家可以利用这些代码来读入这些算例或者是与这些算例的格式相同的算例，这样就不用自己写读入文件的代码了。
jsprit-examples正如它的名字一样，里面都是一些简单的运用这个工具箱的例子，如果大家环境搭好了而且配置正确的话，examples里面的代码是可以直接跑的，这一部分的作用就是用简单的例子向大家展示这个工具箱是怎么工作的。
好了，啰嗦了这么多，我们来动手试试吧。
Step1
下载并解压项目代码
jsprit是用JAVA语言写的，小编推荐用eclipse平台来跑JAVA代码嗷，大家可以直接到官网下载（for free），然后到项目地址
https://github.com/graphhopper/jsprit下载，这里可以下载zip再进行解压。
Step2
下载并解压外部依赖包
这一步我们需要下载一些jsprit依赖的外部包，需要的依赖包以及包的版本可以从项目的介绍里看的到，大家只需要到网上搜索下载下来然后解压就好了，小编建议大家把这些包和上面下载解压的文件放在一个目录里以便于管理，为了方便大家操作，小编已经替大家收集好了这些包，跟源代码打包到一起了，大家直接下载使用就可以了。
Step3
在Eclipse里面创建一个项目并导入上述步骤中下载的包
然后就在eclipse里面新建一个项目。
在新建的项目代码文件夹里加载jsprit的工具包。在src文件夹右键->import->General->File System->Browse
然后找到刚才的解压包解压的位置，找到jsprit-core等包，一直点进去jsprit-core\src\main\java，然后选中左侧的java文件夹，再点击finish就可以了。
下一步就是外部依赖包的引入了，这里我们以slf4j这个包为例子，这里假设大家都已经下载并解压了slf4j这个包，然后在我们新建的java项目上右键->Build Path->Add External Archives，接下来会跳出来一个选择框，找到解压的位置，一直点进去直到看到有这些jar包，导入slf4j-api-1.7.25.jar和slf4j-jdk14-1.7.25.jar两个包。其它的包依次导入就可以了。
Step4
写代码
在准备好上面这些东西之后，我们就可以开始愉快地写代码了。
上述提到有几个核心的组件，这里我们以解某个VRP为例，看看如何使用这些组件，为了方便大家理解，我们先用图大概地给大家介绍一下这几个组件是怎么合作的。
（可能大家还是有点懵，下面我们把代码放上来，结合代码大家体会一下）
package maintest;
import com.graphhopper.jsprit.analysis.toolbox.GraphStreamViewer;
import com.graphhopper.jsprit.analysis.toolbox.GraphStreamViewer.Label;
import com.graphhopper.jsprit.analysis.toolbox.Plotter;
import com.graphhopper.jsprit.core.algorithm.VehicleRoutingAlgorithm;
import com.graphhopper.jsprit.core.algorithm.box.Jsprit;
import com.graphhopper.jsprit.core.problem.Location;
import com.graphhopper.jsprit.core.problem.VehicleRoutingProblem;
import com.graphhopper.jsprit.core.problem.job.Service;
import com.graphhopper.jsprit.core.problem.solution.VehicleRoutingProblemSolution;
import com.graphhopper.jsprit.core.problem.vehicle.VehicleImpl;
import com.graphhopper.jsprit.core.problem.vehicle.VehicleImpl.Builder;
import com.graphhopper.jsprit.core.problem.vehicle.VehicleType;
import com.graphhopper.jsprit.core.problem.vehicle.VehicleTypeImpl;
import com.graphhopper.jsprit.core.reporting.SolutionPrinter;
import com.graphhopper.jsprit.core.util.Solutions;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Scanner;
public class thetest {
/**
* @param args
*/
static int[][] customerNode ;//记录客户点信息
static int capacity = 0;//车辆容量
static int xdepot = 0;//仓库横坐标
static int ydepot = 0;//仓库纵坐标
static int numberOfCustomer = 0;
final static int WEIGHT_INDEX = 0;
public static void main(String[] args) {
//创建输出文件
File dir = new File("output");
if (!dir.exists()) {
System.out.println("creating directory ./output");
boolean result = dir.mkdir();
if (result) System.out.println("./output created");
}
String path = "data/examples.txt";
readData(path);
buildProblem();
}
public static void readData(String path) {
//读入数据
try {
Scanner cin = new Scanner(new BufferedReader(new FileReader(path)));
numberOfCustomer = cin.nextInt();
cin.next();
capacity = cin.nextInt();
xdepot = cin.nextInt();
ydepot = cin.nextInt();
customerNode = new int[numberOfCustomer][3];
for(int i = 0;i<numberOfCustomer;i++) {
cin.nextInt();
for(int j = 0;j<3;j++) {
customerNode[i][j] = cin.nextInt();
}
}
cin.close();
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}
public static void buildProblem() {
//建立一个求解器类型实例，为vehicleType
VehicleTypeImpl.Builder vehicleTypeBuilder = VehicleTypeImpl.Builder.newInstance("vehicleType").addCapacityDimension(WEIGHT_INDEX, capacity);
VehicleType vehicleType = vehicleTypeBuilder.build();
//建立一个求解器实例，名称为vechicle，坐标为读入的坐标，设定求解器的类型
Builder vehicleBuilder = VehicleImpl.Builder.newInstance("vehicle");
vehicleBuilder.setStartLocation(Location.newInstance(xdepot, ydepot));
vehicleBuilder.setType(vehicleType);
VehicleImpl vehicle = vehicleBuilder.build();
//声明服务点的集合
Collection<Service> serviceNode = new ArrayList<Service>();
//读入各服务点的数据
for(int i = 0; i < numberOfCustomer;i++) {
Service serviceNodeTemp = Service.Builder.newInstance(""+i).addSizeDimension(WEIGHT_INDEX, customerNode[i][2]).setLocation(Location.newInstance(customerNode[i][0], customerNode[i][1])).build();
serviceNode.add(serviceNodeTemp);
}
//实例化一个VRP的builder，并将中心点和服务点加入后实例化。
VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder.newInstance();
vrpBuilder.addVehicle(vehicle);
vrpBuilder.addAllJobs(serviceNode);
VehicleRoutingProblem problem = vrpBuilder.build();
//为问题获取算法
VehicleRoutingAlgorithm algorithm = Jsprit.createAlgorithm(problem);
//记录解的集合记录，并寻找最优解
Collection<VehicleRoutingProblemSolution> solutions = algorithm.searchSolutions();
VehicleRoutingProblemSolution bestSolution = Solutions.bestOf(solutions);
//现实求解的结果详情
SolutionPrinter.print(problem, bestSolution, SolutionPrinter.Print.VERBOSE);
//将求解的结果进行可视化
new Plotter(problem,bestSolution).plot("output/plot.png","simple example");
new GraphStreamViewer(problem, bestSolution).labelWith(Label.ID).setRenderDelay(200).display();
}
}经过以上四个Step,我们就能使用这个工具箱来求解一个带容量约束的车辆路径规划问题了。接下来，我们来看看运行的结果是怎么样的，首先我们来看看core.reporting这个组件给出的求解信息
- 通过以上内容大家可以看到给出的求解信息还是非常的详细的。
- 解的详细结果打印的格式是统一的，但是这个VRP的代码里面并不涉及顾客服务时间窗。
- 大家可以看到求解的迭代次数，求解时间为7.68秒，总路程为524.6111466425074，注意这里用的是欧氏距离，在构建问题的时候可以将cost设为曼哈顿距离。
- 共使用了五辆车辆，并在detail中给出了每个车辆的路径，这个结果可以用jsprit-io组件写出为xml文件，但是这个工具箱更秀的是它能直接将上述路线直接生成路线图并输出，请看：
是不是很省事？图画出来也还不错，你以为这就完了？还记得上文导入的外部包里有一个graphstream吗，这个东西可以动态地呈现整个运输过程，来看看效果图吧
怎么样，是不是很酷炫？而且上述可视化只需要两行代码，就能还你一幅酷炫的路线图。
02
与Cplex求解对比
上述是一个简单的入门的例子，前文提到这个工具箱是基于元启发式算法的，在上述算例中，得到的解是算例的最优解，那它跟例如Cplex这样的求解器在求解性能上会差多少呢，这里我们以一个带时间窗的车辆路径规划问题的代码为例来比较一下两者的求解结果。由于篇幅关系，这里就只放用该求解器求解带时间窗的车辆路径规划问题的代码，用Cplex求解的代码以及用到的算例和外部依赖包等等都会给大家。
代码如下：
import com.graphhopper.jsprit.analysis.toolbox.GraphStreamViewer;
import com.graphhopper.jsprit.analysis.toolbox.Plotter;
import com.graphhopper.jsprit.analysis.toolbox.GraphStreamViewer.Label;
import com.graphhopper.jsprit.core.algorithm.VehicleRoutingAlgorithm;
import com.graphhopper.jsprit.core.algorithm.box.Jsprit;
import com.graphhopper.jsprit.core.problem.Location;
import com.graphhopper.jsprit.core.problem.VehicleRoutingProblem;
import com.graphhopper.jsprit.core.problem.job.Service;
import com.graphhopper.jsprit.core.problem.solution.VehicleRoutingProblemSolution;
import com.graphhopper.jsprit.core.problem.vehicle.VehicleImpl;
import com.graphhopper.jsprit.core.problem.vehicle.VehicleImpl.Builder;
import com.graphhopper.jsprit.core.problem.vehicle.VehicleType;
import com.graphhopper.jsprit.core.problem.vehicle.VehicleTypeImpl;
import com.graphhopper.jsprit.core.reporting.SolutionPrinter;
import com.graphhopper.jsprit.core.util.ManhattanCosts;
import com.graphhopper.jsprit.core.util.Solutions;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Scanner;
public class Vrptw_test {
static int capacity;
static int xdepot;
static int ydepot;
static int numberOfCustomer = 30;//这里选取30个客户点
final static int WEIGHT_INDEX = 0;
static int[][] customerNode;//用户点数据
public static void main(String[] args) {
String path = "data/c104.txt";
readData(path);
buildProblem();
}
public static void readData(String path) {
//读入数据
try {
Scanner cin = new Scanner(new BufferedReader(new FileReader(path)));
xdepot = cin.nextInt();
ydepot = cin.nextInt();
capacity = cin.nextInt();
customerNode = new int[numberOfCustomer][6];
for(int i = 0;i<numberOfCustomer;i++) {
cin.nextInt();
for (int j = 0;j<6;j++) {
customerNode[i][j] = cin.nextInt();
}
}
cin.close();
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}
public static void buildProblem() {
//实例化问题的类型
VehicleTypeImpl.Builder vehicleTypeBuilder = VehicleTypeImpl.Builder.newInstance("vehic
leType")
.addCapacityDimension(WEIGHT_INDEX, capacity).setCostPerWaitingTime(1.);
VehicleType vehicleType = vehicleTypeBuilder.build();
Builder vehicleBuilder = Builder.newInstance("vehicle");
//设置中心的坐标
vehicleBuilder.setStartLocation(Location.newInstance(xdepot, ydepot));
//最长时间
vehicleBuilder.setLatestArrival(1351);
vehicleBuilder.setType(vehicleType);
//实例化构造器
VehicleImpl vehicle = vehicleBuilder.build();
//构建并实例化所有的客户点
Collection<Service> serviceNode = new ArrayList<Service>();
for(int i = 0;i<numberOfCustomer;i++) {
Service temp = Service.Builder.newInstance(""+i)
.addTimeWindow(customerNode[i][3],customerNode[i][4])
.addSizeDimension(WEIGHT_INDEX, customerNode[i][2])
.setServiceTime(customerNode[i][5])
.setLocation(Location.newInstance(customerNode[i][0], customerNode[i][1]))
.build();
serviceNode.add(temp);
}
//构造问题
VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder.newInstance();
vrpBuilder.addVehicle(vehicle);
vrpBuilder.addAllJobs(serviceNode);
vrpBuilder.setFleetSize(VehicleRoutingProblem.FleetSize.INFINITE);
//vrpBuilder.setRoutingCost(new ManhattanCosts());//这一行是设置花费为曼哈顿距离
VehicleRoutingProblem problem = vrpBuilder.build();
//根据问题寻找算法和solution
VehicleRoutingAlgorithm algorithm = Jsprit.createAlgorithm(problem);
Collection<VehicleRoutingProblemSolution> solutions = algorithm.searchSolutions();
//寻找BestSolution
VehicleRoutingProblemSolution bestSolution = Solutions.bestOf(solutions);
//打印求解过程和结果
SolutionPrinter.print(problem, bestSolution, SolutionPrinter.Print.VERBOSE);
//绘图
new Plotter(problem,bestSolution).setLabel(Plotter.Label.ID).plot("output/plot2.png","mtw");
new GraphStreamViewer(problem, bestSolution).labelWith(Label.ID).setRenderDelay(300).display();
}
}
然后我们先来看一下调用Cplex给出的求解结果
再来看看这个工具箱给出的求解结果，为了减少篇幅，这里贴部分结果
很遗憾，虽然这个工具箱的速度比Cplex要快得多，但是精确度上还是差得还是有点远的。当然我们可以修改工具箱源代码里面的迭代次数，这样有可能会达到一个更优的解，但是这样做也会增加求解的时间，这个取舍就取决于使用者了，由于篇幅和时间的原因，这里不可能作大量的测试。
小结
虽然这个工具箱不一定能找到最优解，而且使用前需要导入许多外部依赖包，也要求使用者要有一点JAVA编程的基础，但是这个工具箱的一大优点是它的可视化做的很好，解的详细信息也可以很直观地表示出来，各个组件是模块化的，掌握和理解起来不会太难。小编觉得最好的理解和学习方式是读代码，作者在Github上面也给出了很多代码实例供大家学习。总的来说小编还是觉得这个东西不错的，起码在使用上还是比Cplex方便一些的，正所谓技多不压身，各位可以学一学，看一看啦。