问题定义
车辆路线规划问题是一个经典的组合优化问题，也是旅行商问题的泛化。该问题的定义为：
- 有给定数量的客户有运输需求；
- 为从某个固定地点出发和返回的车辆寻找一个最优路线试的可以服务所有的客户
车辆路线规划问题是NP-hard问题，一般建议求最优解的近似解。
车辆路线规划问题有很多变种，主要包含 Classical VRP（VRP）、 Capacitated Vehicle Routing Problem (CVRP)、 Vehicle Routing Problem with Time Windows (VRPTW)、 Vehicle Routing Problem with Pick-Up and Delivery (VRPPD)等。现实生活中VRP模型用处较少，其它都很常见；CVRP对应配送中心对配送站点的送货，VRPTW则面向客户的送货，如外卖；VRPPD对应取货和送货，如京东快递即可以送快递又可以取快递。
本本主要套餐CVRP，其定义如下：
令G =（V，A)表示一个有向图，其中V是顶点集，而A是弧集。一个顶点表示 m个容量为Q的相同车辆组成的车队所在的仓库，其它顶点表示要服务的客户。每个客户顶点vi与需求qi关联。每个弧（vi，vj）通过A与耗费成本cij相关联。每个客户包含一个就绪时间，一个过期时间。 CVRPTW目标是找到一系列路线，以便：
- 每条路线以仓库为起始点;
- 每个用户仅被服务一次;
- 每条路线的需求量不超过Q;
- 所有路线总消耗成本最小;
- 客户在就绪时间和过期时间之间被服务；
VRPTW问题描述
C101（测试用例名称）
VEHICLE（车辆信息）
NUMBER CAPACITY
25（辆） 200（每辆车最大负载）
CUSTOMER（用户信息）
用户号 位置X坐标 位置Y坐标 需求 用户就绪时间 截止时间 服务时间
CUST NO. XCOORD. YCOORD. DEMAND READY TIME DUE DATE SERVICE TIME
0 40 50 0 0 1236 0
1 45 68 10 912 967 90
2 45 70 30 825 870 90
3 42 66 10 65 146 90
4 42 68 10 727 782 90
5 42 65 10 15 67 90
6 40 69 20 621 702 90
7 40 66 20 170 225 90
8 38 68 20 255 324 90
9 38 70 10 534 605 90
10 35 66 10 357 410 90
11 35 69 10 448 505 90
12 25 85 20 652 721 90
13 22 75 30 30 92 90
14 22 85 10 567 620 90
15 20 80 40 384 429 90
16 20 85 40 475 528 90
17 18 75 20 99 148 90
18 15 75 20 179 254 90
19 15 80 10 278 345 90
20 30 50 10 10 73 90
21 30 52 20 914 965 90
22 28 52 20 812 883 90
23 28 55 10 732 777 90
24 25 50 10 65 144 90
25 25 52 40 169 224 90
通过Optaoplanner求解获取的结果类似如下样式：Vechicle i（包含仓库坐标） -> Customer 1 -> Customeri -> Vechicle i（包含仓库坐标），排线后获取结果类似如下：
A-n32-k5
Vehicle 1: 1(0)->13(21)->2(19)->17(18)->31(14)->1(0) totalDemand = 72.0
Vehicle 2: 1(0)->28(20)->25(24)->1(0) totalDemand = 44.0
Vehicle 3: 1(0)->22(12)->32(9)->20(24)->18(19)->14(16)->8(16)->27(2)->1(0) totalDemand = 98.0
Vehicle 4: 1(0)->7(12)->4(6)->3(21)->24(8)->5(19)->12(14)->29(15)->15(3)->1(0) totalDemand = 98.0
Vehicle 5: 1(0)->21(8)->6(7)->26(24)->11(8)->30(2)->16(22)->23(4)->10(16)->9(6)->19(1)->1(0) totalDemand = 98.0
最优解: 787.08
Vehicle 1（仓库） -> 13(21) -> 2(19) -> 17(18) -> 31(14) -> Vehicle 1（仓库） totalDemand = 72.0
VRPTW问题简单方式计算得分算法源码
VehicleRoutingEasyScoreCalculator分析
@Override
public HardSoftLongScore calculateScore(VehicleRoutingSolution solution) {
boolean timeWindowed = solution instanceof TimeWindowedVehicleRoutingSolution;
List<Customer> customerList = solution.getCustomerList();
List<Vehicle> vehicleList = solution.getVehicleList();
Map<Vehicle, Integer> vehicleDemandMap = new HashMap<>(vehicleList.size());
for (Vehicle vehicle : vehicleList) {
vehicleDemandMap.put(vehicle, 0);
}
long hardScore = 0L;
long softScore = 0L;
for (Customer customer : customerList) {
// Entity(Customer)的planningVariable（Customer or Vehivle)，计算当前用户和前驱节点之间的距离（前驱可以是车，可以是人，车必须在列表第一个）
Standstill previousStandstill = customer.getPreviousStandstill();
if (previousStandstill != null) {
// 每个Entity分配一辆Vehicle
Vehicle vehicle = customer.getVehicle();
// 以车辆为单位计算每辆车的总载荷
vehicleDemandMap.put(vehicle, vehicleDemandMap.get(vehicle) + customer.getDemand());
// 计算当前节点和前驱节点之间的距离
// Score constraint distanceToPreviousStandstill
softScore -= customer.getDistanceFromPreviousStandstill();
if (customer.getNextCustomer() == null) {
// Score constraint distanceFromLastCustomerToDepot
// 如果这个客户是最后一个被服务的客户，还要计算当前客户与仓库（车辆包含仓库信息）之间的距离（软限制，越大越好）
softScore -= customer.getLocation().getDistanceTo(vehicle.getLocation());
}
if (timeWindowed) {
// 如果是VRPTW问题，则需要计算车辆arrivalTime是否打破了用户的dueTime时间限制（强限制，越大越好）
TimeWindowedCustomer timeWindowedCustomer = (TimeWindowedCustomer) customer;
long dueTime = timeWindowedCustomer.getDueTime();
Long arrivalTime = timeWindowedCustomer.getArrivalTime();
if (dueTime < arrivalTime) {
// Score constraint arrivalAfterDueTime
hardScore -= (arrivalTime - dueTime);
}
}
}
}
// 计算每个车辆的是否打破容量限制（强限制，越大越好）
for (Map.Entry<Vehicle, Integer> entry : vehicleDemandMap.entrySet()) {
int capacity = entry.getKey().getCapacity();
int demand = entry.getValue();
if (demand > capacity) {
// Score constraint vehicleCapacity
hardScore -= (demand - capacity);
}
}
// Score constraint arrivalAfterDueTimeAtDepot is a built-in hard constraint in VehicleRoutingImporter
return HardSoftLongScore.valueOf(hardScore, softScore);
}