optaplanner - 使用 OptaPlanner 解决具有容量的车辆路径问题
问题描述
您好所有 optaplanners。我是使用 optaplanner 的新手,在这里我对规划具有重量和体积容量的车辆路线有一些疑问。感谢您的帮助,我很感激任何建议。
我正在实施具有容量的 VRP,但要求容量以重量和体积为尺寸。我走的路就是以optaplanner为例,从体积和重量上重构车辆容量,在重量和体积上重构访问的需求。然后我修改了使用数量来处理容量的约束提供程序,以处理重量,然后我实现了另一个非常相似但处理体积的约束提供程序。从现在开始,我还将要求车辆的容量和访客(客户)的负载的其他维度。
1-由于我是新手,我想知道我的假设是否正确,我是否走在正确的道路上?
2- 我想知道与每个维度的约束提供者一起工作是否正确,或者我是否应该加入一个约束提供者的所有重量和体积或其他计算。如果可能的话,我该怎么做?
3- 如果我有一辆只有重量容量的车辆和另一辆只有容量容量的车辆,但我有访问(客户)的需求要求同时覆盖重量和体积,因此我永远不会获得可行的路线,因为只有一辆车经过同一次访问。我怎么解决这个问题?
4-当访问(客户)的需求超过车辆的容量时,我该如何管理,车辆会多次前往同一访问,直到它覆盖访问(客户)的总需求?
在这里,我分享我的修改以获得更好的上下文。谢谢!
重构载具容量:
public class PlanningVehicle implements Standstill {
@PlanningId
private long id;
private int weightCapacity;
private int volumeCapacity;
...
}
重构了访问的需求:
@PlanningEntity(difficultyWeightFactoryClass = DepotAngleVisitDifficultyWeightFactory.class)
public class PlanningVisit implements Standstill {
@PlanningId
private long id;
private PlanningLocation location;
private int weightDemand;
private int volumeDemand;
...
}
我实施了两个硬分,每个维度(重量和体积)一个:
@ConstraintConfiguration(constraintPackage = "com.router.solver")
public class VehicleRoutingConstraintConfiguration {
...
public static final String VEHICLE_WEIGHT_CAPACITY = "Vehicle capacity in weight";
public static final String VEHICLE_VOLUME_CAPACITY = "Vehicle capacity in volume";
...
@ConstraintWeight(VEHICLE_WEIGHT_CAPACITY)
private HardSoftLongScore vehicleWeightCapacity = HardSoftLongScore.ONE_HARD;
@ConstraintWeight(VEHICLE_VOLUME_CAPACITY)
private HardSoftLongScore vehicleVolumeCapacity = HardSoftLongScore.ONE_HARD;
}
我实现了两个单独的约束:
public class FirstConstraintProvider implements ConstraintProvider {
...
protected Constraint vehicleWeightCapacity(ConstraintFactory constraintFactory) {
return constraintFactory.from(TimeWindowedVisit.class)
.groupBy(PlanningVisit::getVehicle, sum(PlanningVisit::getWeightDemand))
.filter((vehicle, demand) -> demand > vehicle.getWeightCapacity())
.penalizeConfigurableLong(
VEHICLE_WEIGHT_CAPACITY,
(vehicle, demand) -> demand - vehicle.getWeightCapacity());
}
protected Constraint vehicleVolumeCapacity(ConstraintFactory constraintFactory) {
return constraintFactory.from(TimeWindowedVisit.class)
.groupBy(PlanningVisit::getVehicle, sum(PlanningVisit::getVolumeDemand))
.filter((vehicle, demand) -> demand > vehicle.getVolumeCapacity())
.penalizeConfigurableLong(
VEHICLE_VOLUME_CAPACITY,
(vehicle, demand) -> demand - vehicle.getVolumeCapacity());
}
...
}
解决方案
对角线阅读:
-
- 是的,我更喜欢将重量和体积分成单独的约束,以使它们保持隔离,这样更便于维护。此外,一旦您开始使用 ConstraintMatchTotals 等向用户“解释分数”,这肯定会更好。
- 3 & 4) 典型的方法是将一次客户访问拆分为同一地点的多次访问。所以分成多个部分。例如,如果车辆在一个位置拾取 5 个部件中的 3 个,则这 3 个位置之间的行驶时间为零,并且装载/卸载时间被折叠(参见自动折叠设计模式)。最大的挑战是在 optaplanner 解决之前确定这些部分的粒度。这是一个微调练习。如果您要移动箱子、托盘、物品等,这很有效。可能的例外是,如果您要移动水、钱、煤气等。在这种情况下,类似于 InvestementPortofio 示例的电源调整可能很有趣而是这样做了。
推荐阅读
- c# - C#串口通信示例
- python - 字典列表中的 Nan 值
- angular - Angular 9:无法在 v9.1.0 中构建依赖于其他 Angular 库的 Angular 库
- c# - Display category once in repeater
- java - Opencsv,StatefulBeanToCsv 将嵌套的对象列表写入 csv
- javascript - Javscript:对于每个图像单击显示模式与图像缩放
- yocto - yocto 图像大小随着分区大小的增加而增加
- hibernate - 如何在 Spring Hibernate 中批量删除?
- java - NiFi Confluent Schema注册表异常
- sql - 使用单个连接子句连接多个表(sqlite)