or-tools简介
示例1：假设一家公司要拜访地图上所有的客户，现在需要规划出总里程最短的方案。其中0为公司，即起点，其他的点为客户，即终点。
使用or-tools的VRP工具来解决示例
要解决以上示例的问题，我们先来了解一下一些基本的概念
数据模型
static class DataModel { //距离矩阵 public final long[][] distanceMatrix = { {0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662}, {548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210}, {776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754}, {696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358}, {582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244}, {274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708}, {502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480}, {194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856}, {308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514}, {194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468}, {536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354}, {502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844}, {388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730}, {354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536}, {468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194}, {776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798}, {662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0}, }; //最大车辆限制 public final int vehicleNumber = 4; //起点 public final int depot = 0; }
:::tips
我们来详细看一下这些参数：
- 距离矩阵distanceMatrix：首先我们可以看到，他是一个二维数组，共有17行17列，对应的是我们地图上的17个点。
以distanceMatrix[0] = {0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662}为例：
可以看到，该数组记录的是0这个点到地图上所有点之间的距离，地图上共17个点，所以该数组的容量就是17，同理我们可以看到其他的一维数组也是这么记录的。
一言蔽之：二维数组的行代表的是点，列代表的是点与点之间的距离。
- 车辆限制vehicleNumber：在我们的建模中，车辆即路线。所以这里是最大路线的限制，要注意这里是给出最大的路线数量限制，而不是指定路线数量限制。假设算法认为两条路线就能规划出最优的结果，那么剩余的路线就会给出总里程为0的值，我们在最终提取结果时把这样的内容删去即可。
- 起点depot：车辆开始的点以及返回的点
:::
距离回调函数
使用距离回调函数，让求解器解析路径距离
final int transitCallbackIndex = routing.registerTransitCallback((long fromIndex, long toIndex) -> { int fromNode = manager.indexToNode(fromIndex); int toNode = manager.indexToNode(toIndex); return data.distanceMatrix[fromNode][toNode]; }); routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);
:::tips
回调函数的作用是让求解器解析我们的数据
参数列表：fromIndex，toIndex
返回值：distanceMatrix[fromNode][toNode]
根据我们上面对二维数组的介绍，可以知道这里返回的就是两点之间的距离
:::
距离维度
维度是求解器用来计算各种数量的对象。我们可以将维度理解为一种限制或约束
我们先来看一下距离维度是怎么做的
routing.addDimension(transitCallbackIndex, 0, 3000,true,"Distance"); RoutingDimension distanceDimension = routing.getMutableDimension("Distance"); distanceDimension.setGlobalSpanCostCoefficient(100);
我们看一下addDimension这个方法的源码：
public boolean addDimension(int evaluator_index, long slack_max, long capacity, boolean fix_start_cumul_to_zero, String name) { return mainJNI.RoutingModel_addDimension(swigCPtr, this, evaluator_index, slack_max, capacity, fix_start_cumul_to_zero, name); }
我们重点关注一下long capacity这个参数，其作用是限制车辆的最大行驶距离。如果我们不需要对其进行限制，那么直接传入Long.MAX_VALUE即可
完成计划代码
注意数据模型的代码上面已经提供过了，因此这里不再赘述。
public static void main(String[] args) throws Exception { //加载本地方法库 Loader.loadNativeLibraries(); // 初始化数据模型 final DataModel data = new DataModel(); //创建求解器manager对象，初始化求解器数据 RoutingIndexManager manager = new RoutingIndexManager(data.distanceMatrix.length, data.vehicleNumber, data.depot); // 初始化求解器 RoutingModel routing = new RoutingModel(manager); // 注册回调函数 final int transitCallbackIndex = routing.registerTransitCallback((long fromIndex, long toIndex) -> { int fromNode = manager.indexToNode(fromIndex); int toNode = manager.indexToNode(toIndex); return data.distanceMatrix[fromNode][toNode]; }); // 定义回调函数至每条路线 routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex); // 增加距离维度约束 routing.addDimension(transitCallbackIndex, 0, 3000, true, "Distance"); RoutingDimension distanceDimension = routing.getMutableDimension("Distance"); distanceDimension.setGlobalSpanCostCoefficient(100); //设置搜索方法 RoutingSearchParameters searchParameters = main.defaultRoutingSearchParameters() .toBuilder() .setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC) .build(); // 执行算法 Assignment solution = routing.solveWithParameters(searchParameters); // 打印路线 printSolution(data, routing, manager, solution); }
static void printSolution( DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution) { long maxRouteDistance = 0; for (int i = 0; i < data.vehicleNumber; ++i) { long index = routing.start(i); logger.info("Route for Vehicle " + i + ":"); long routeDistance = 0; String route = ""; while (!routing.isEnd(index)) { route += manager.indexToNode(index) + " -> "; long previousIndex = index; index = solution.value(routing.nextVar(index)); routeDistance += routing.getArcCostForVehicle(previousIndex, index, i); } logger.info(route + manager.indexToNode(index)); logger.info("Distance of the route: " + routeDistance + "m"); maxRouteDistance = Math.max(routeDistance, maxRouteDistance); } logger.info("Maximum of the route distances: " + maxRouteDistance + "m"); }
执行后得到以下结果
:::tips
Route for Vehicle 0:
0 -> 8 -> 6 -> 2 -> 5 -> 0
Distance of the route: 1552m
Route for Vehicle 1:
0 -> 7 -> 1 -> 4 -> 3 -> 0
Distance of the route: 1552m
Route for Vehicle 2:
0 -> 9 -> 10 -> 16 -> 14 -> 0
Distance of the route: 1552m
Route for Vehicle 3:
0 -> 12 -> 11 -> 15 -> 13 -> 0
Distance of the route: 1552m
Maximum of the route distances: 1552m
:::
图示：
以上，我们解决了一个基本的车辆路线问题。但是我们可以看到在上述示例中，规划出来的最终路径是无序的，即无法保证取送的顺序。因此我们需要引入其他的约束保证顺序。
车辆取送问题
在示例1的基础之上，我们要对其进行改进。首先我们需要对配送的顺序进行限制，保证路线的方向性，并且需要先取到货才能送货。
在取送的问题中，我们还需要考虑多仓库的问题，即起点也会有多个，每条路线的起点可以是不同的，而不是从一个相同的仓库出发，而且我们也不需要车辆返回起点。这里为了简化，我们暂时不考虑起点终点重合的问题。
取货与配送矩阵
在以上需求中，我们首先需要考虑的就是路线的方向。这里or-tools也给我们提供了可以直接设置的参数。
public final int[][] pickupsDeliveries = {{1, 2}, {3, 4}, {5, 6}, {7, 8}, {9, 10}, {11, 12}, {13, 14}, {15, 16}};
可以看到这里也是一个二维数组对象。但是需要注意的是这个二维数组中的每个一维数组有且只有两个值。第一个值代表起点，第二个值代表的是终点，数据值即是他们在distanceMatrix中对应的下标，每个下标都是唯一的，不允许重复。
接下来我们需要往求解器中添加这些约束因子
Solver solver = routing.solver(); //添加路径取送约束 for (int[] request : data.pickupsDeliveries) { long pickupIndex = manager.nodeToIndex(request[0]); long deliveryIndex = manager.nodeToIndex(request[1]); routing.addPickupAndDelivery(pickupIndex, deliveryIndex); solver.addConstraint( solver.makeEquality(routing.vehicleVar(pickupIndex), routing.vehicleVar(deliveryIndex))); solver.addConstraint(solver.makeLessOrEqual( distanceDimension.cumulVar(pickupIndex), distanceDimension.cumulVar(deliveryIndex))); }
在以上这段代码中，我们对配送约束矩阵进行遍历。`routing.addPickupAndDelivery(pickupIndex, deliveryIndex);`这段代码会向求解器中创建自提和配送请求。
接着我们使用下面的代码添加了另外的约束：每张单据必须由同一辆车取货和配送
solver.addConstraint( solver.makeEquality(routing.vehicleVar(pickupIndex), routing.vehicleVar(deliveryIndex)));
最后我们还需要限制每张单据在配送前必须要先完成取货。所以需要限制车辆在到达取货点行驶的累计距离必须要不超过其到达配送点的累计行驶距离
solver.addConstraint(solver.makeLessOrEqual( distanceDimension.cumulVar(pickupIndex), distanceDimension.cumulVar(deliveryIndex)));
以上，我们便完成了对于车辆配送路线的约束。
任意的起点和终点
:::tips
只需修改矩阵的第一行和第一列均全零，即可修改距离矩阵到任何其他地点的距离为 0。这会将仓库变为虚拟位置，对最佳路线没有任何影响
:::
在实际的应用中，我们只需要新增一个默认的点来作为我们的虚拟仓库，使得他到所有点的距离都为0。将他放在我们的第一行，下标为0，我们在使用的时候在创建求解器对象的时候将depot的值传入0就可以实现任意的起点和终点。
这里还需要注意，在最后的返回的结果中，还是会打印出下标为0的这个点，所以我们在最终的打印方法里需要做处理，过滤掉0
车辆取送问题代码实现
我们来看一下完整的代码
static class DataModel { public final long[][] distanceMatrix = { {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 19801, 11006, 19801, 18919, 22227, 20719, 25550, 5698, 40312, 110962, 12084, 14385, 4566, 18368, 21985}, {0, 19801, 0, 12014, 0, 2441, 5925, 1473, 7095, 14143, 45184, 91440, 10836, 5613, 15977, 6469, 8001}, {0, 11006, 12014, 0, 12014, 10149, 12175, 12297, 19006, 7401, 35848, 102899, 1311, 8708, 6449, 14329, 17783}, {0, 19801, 0, 12014, 0, 2441, 5925, 1473, 7095, 14143, 45184, 91440, 10836, 5613, 15977, 6469, 8001}, {0, 18919, 2441, 10149, 2441, 0, 4389, 2164, 9379, 13414, 42745, 92867, 8899, 5653, 14806, 8336, 10333}, {0, 22227, 5925, 12175, 5925, 4389, 0, 4572, 10998, 17013, 41082, 91020, 10867, 9968, 17843, 12380, 13688}, {0, 20719, 1473, 12297, 1473, 2164, 4572, 0, 7363, 15118, 44552, 90798, 11056, 6805, 16737, 7903, 9152}, {0, 25550, 7095, 19006, 7095, 9379, 10998, 7363, 0, 19877, 51847, 85429, 17874, 11321, 22242, 7857, 5662}, {0, 5698, 14143, 7401, 14143, 13414, 17013, 15118, 19877, 0, 41367, 105271, 8044, 8687, 3282, 12886, 16561}, {0, 40312, 45184, 35848, 45184, 42745, 41082, 44552, 51847, 41367, 0, 124228, 36330, 44170, 38348, 49669, 52691}, {0, 110962, 91440, 102899, 91440, 92867, 91020, 90798, 85429, 105271, 124228, 0, 101602, 96612, 107404, 92948, 89626}, {0, 12084, 10836, 1311, 10836, 8899, 10867, 11056, 17874, 8044, 36330, 101602, 0, 7936, 7518, 13548, 16909}, {0, 14385, 5613, 8708, 5613, 5653, 9968, 6805, 11321, 8687, 44170, 96612, 7936, 0, 10922, 5624, 9111}, {0, 4566, 15977, 6449, 15977, 14806, 17843, 16737, 22242, 3282, 38348, 107404, 7518, 10922, 0, 15709, 19408}, {0, 18368, 6469, 14329, 6469, 8336, 12380, 7903, 7857, 12886, 49669, 92948, 13548, 5624, 15709, 0, 3699}, {0, 21985, 8001, 17783, 8001, 10333, 13688, 9152, 5662, 16561, 52691, 89626, 16909, 9111, 19408, 3699, 0}}; public final int[][] pickupsDeliveries = {{1, 2}, {3, 4}, {5, 6}, {7, 8}, {9, 10}, {11, 12}, {13, 14}, {15, 16}}; public final Integer vehicleNumber = 7; }
private static Plan compute(DataModel data) { long[][] distanceMatrix = data.distanceMatrix; RoutingIndexManager manager = new RoutingIndexManager(distanceMatrix.length, data.vehicleNumber, 0); RoutingModel routing = new RoutingModel(manager); final int transitCallbackIndex = routing.registerTransitCallback((long fromIndex, long toIndex) -> { int fromNode = manager.indexToNode(fromIndex); int toNode = manager.indexToNode(toIndex); return distanceMatrix[fromNode][toNode]; }); routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex); routing.addDimension(transitCallbackIndex, 0, Long.MAX_VALUE, true, "Distance"); RoutingDimension distanceDimension = routing.getMutableDimension("Distance"); Solver solver = routing.solver(); //添加路径取送约束 for (int[] request : data.pickupsDeliveries) { long pickupIndex = manager.nodeToIndex(request[0]); long deliveryIndex = manager.nodeToIndex(request[1]); routing.addPickupAndDelivery(pickupIndex, deliveryIndex); solver.addConstraint( solver.makeEquality(routing.vehicleVar(pickupIndex), routing.vehicleVar(deliveryIndex))); solver.addConstraint(solver.makeLessOrEqual( distanceDimension.cumulVar(pickupIndex), distanceDimension.cumulVar(deliveryIndex))); } RoutingSearchParameters searchParameters = main.defaultRoutingSearchParameters() .toBuilder() .setFirstSolutionStrategy(FirstSolutionStrategy.Value.PARALLEL_CHEAPEST_INSERTION) .build(); Assignment solution = routing.solveWithParameters(searchParameters); return printSolution(data.vehicleNumber, routing, manager, solution); }
static Plan printSolution(Integer vehicleNumber, RoutingModel routing, RoutingIndexManager manager, Assignment solution) { long totalDistance = 0; List<String> list = new ArrayList<>(); for (int i = 0; i < vehicleNumber; ++i) { long index = routing.start(i); System.out.println("车辆 " + i + ":"); long routeDistance = 0; String route = ""; while (!routing.isEnd(index)) { int resIndex = manager.indexToNode(index); if (resIndex != 0) { route += resIndex + ","; } long previousIndex = index; index = solution.value(routing.nextVar(index)); routeDistance += routing.getArcCostForVehicle(previousIndex, index, i); } int lastIndex = manager.indexToNode(index); String msg = route; if (lastIndex != 0) { msg += lastIndex; } if (msg.endsWith(",")) { msg = msg.substring(0, msg.length() - 1); } list.add(msg); System.out.println(msg); System.out.println("路线里程: " + routeDistance + "m"); totalDistance += routeDistance; } double res = (double) totalDistance / 1000; System.out.println("最后的路线列表:" + list); System.out.println("该方案总里程: " + res + "km"); Plan plan = new Plan(); plan.setCarNum(vehicleNumber); plan.setTotalDistance(totalDistance); return plan; }
public static void main(String[] args) throws Exception { Loader.loadNativeLibraries(); final DataModel data = new DataModel(); Plan compute = compute(data); }
最后的执行结果
:::tips
车辆 0:
15,16
路线里程: 3699m
车辆 1:
5,6
路线里程: 4389m
车辆 2:
7,8
路线里程: 7363m
车辆 3:
13,9,14,10
路线里程: 50317m
车辆 4:
1,3,2,4
路线里程: 23020m
车辆 5:
11,12
路线里程: 101602m
车辆 6:
路线里程: 0m
最后的路线列表:[15,16, 5,6, 7,8, 13,9,14,10, 1,3,2,4, 11,12, ]
该方案总里程: 190.39km
:::
以上的执行结果也印证了之前我们讲过的，车辆数量参数vehicleNumber实际上是最大车辆数量限制，可以看到车辆6是没有安排线路的。并且最终的路线结果也符合我们的约束矩阵的要求，必须要先取到货才能配送。
车辆容量限制
在取送问题的示例中，我们保证了发货单配送的取送顺序，但是还没有加上车辆的容载限制。我们在之前提到过，维度这个概念可以理解为就是给求解器加上一些约束，因此这里我们加上一个容量的维度即可。
数据模型
//每一个点的商品的数量 public final long[] demands = {0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8}; //车辆最大容载 public final long[] vehicleCapacities = {25, 25, 25, 25, 25, 25, 25};
demands：这个数组记录的是每个点上面对应的商品数量，即车辆抵达这个点，就会累计数量。事实上，按照我们的取送逻辑，这里应该设置成起点为正（取货），终点为负（卸货），但是为了演示的方便，我们这里就没有做设置。
vehicleCapacities：每辆车的最大容载数量。只要每行驶到一个点，就会累计商品数量，不允许超过车辆的容载。
要注意，在使用的时候每个点都需要指定商品数量，每辆车必须指定容量。即demands的长度需要与我们本次需要计算路径的点的数量一致（包含我们的虚拟仓库0），vehicleCapacities的长度也需要等于我们指定的最大车辆数量。
容量维度
// 添加容量限制 final int demandCallbackIndex = routing.registerUnaryTransitCallback((long fromIndex) -> { int fromNode = manager.indexToNode(fromIndex); return data.demands[fromNode]; }); routing.addDimensionWithVehicleCapacity(demandCallbackIndex, 0, data.vehicleCapacities, true, "Capacity"); Solver solver = routing.solver();
在取送问题的示例中，加上以上的容量维度代码限制即可
总结
在本文中，我们使用or-tools解决了基本的带有容量限制的车辆取送问题。但是在现实的业务场景中，显然要比这些问题要复杂的多，在下一篇中我们将详细的讨论一个真实的业务场景问题。
