OptaPlanner源码学习-VRPTW问题计算得分
2021/12/27 20:07:30
本文主要是介绍OptaPlanner源码学习-VRPTW问题计算得分,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
问题定义
车辆路线规划问题是一个经典的组合优化问题,也是旅行商问题的泛化。该问题的定义为:
- 有给定数量的客户有运输需求;
- 为从某个固定地点出发和返回的车辆寻找一个最优路线试的可以服务所有的客户
车辆路线规划问题是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); }
这篇关于OptaPlanner源码学习-VRPTW问题计算得分的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性
- 2024-05-29哪些无用敏捷指标正在破坏敏捷转型?
- 2024-05-29鸿蒙原生应用再新丁!新华社 入局鸿蒙
- 2024-05-29设计模式 之 迭代器模式(Iterator)