How to choose a vehicle that can accommodate the specified number of employees with OptaPlanner?

user_19415969 0
Viewed 52

How to choose a vehicle that can accommodate the specified number of employees with OptaPlanner?

Employee:

public class Employee {

    @PlanningId
    private Long id;

    private String name;
}

Transport (Vehicle)

@PlanningEntity
public class Transport {

    @PlanningId
    private Long id;
    private Integer capacity;

    @PlanningListVariable(valueRangeProviderRefs = "employeeRange")
    private List<Employee> employeeList = new ArrayList<>();
}

Solution

@PlanningSolution
public class Solution {

    @PlanningEntityCollectionProperty
    private List<Transport> transports;

    @ProblemFactCollectionProperty
    @ValueRangeProvider(id = "employeeRange")
    private List<Employee> employees;

    @PlanningScore
    private HardMediumSoftLongScore score;

    public Plan(List<Transport> transports, List<Employee> employees) {
        this.transports = transports;
        this.employees = employees;
    }
}

Constraint

private Constraint transportCapacity(ConstraintFactory factory) {
        return factory.forEach(Transport.class)
                      .filter(transport -> transport.getEmployees().size() >   transport.getCapacity()).penalizeLong("capacity",
                    HardMediumSoftLongScore.ONE_HARD, transport -> transport.getEmployees().size() - transport.getCapacity());
}

Given:

  • transports with capacity - 20, 4, 6, 2
  • employees - 6

The problem is that the algorithm chooses the transport that comes first and meets the given restrictions. For example, for solving this problem algorithm chooses transport with capacity 20 instead of 6 which is more optimal.

How to solve this problem correctly? Thanks in advance!

optaplanner java
2 Answers

The problem is that the algorithm chooses the transport that comes first and meets the given restrictions.

This is how the Construction Heuristic algorithm works. Its goal is to quickly find a good enough solution that can be further optimized in the next phase called the Local Search.

Now, if you consider assigning 6 employees to the transport with capacity 6 better than the transport with capacity 20, you have to provide incentives for OptaPlanner to make that improvement.

These incentives are expressed in the form of constraints. In this case you could define a constraint that adds a soft score penalty for the unused capacity on each used transport.

Using the transport of size 20 could result in the score of 0hard/-14soft whereas using the transport of size 6 would result in 0hard/0soft, which is better.

user_16911520

Based on the answer of yurloc we can add 2 constraints:

  • The first constraint is responsible for the maximum number of seats in transport.
  • The second constraint is responsible for the optimal placement of employees.
private Constraint transportMaxCapacity(ConstraintFactory factory) {
return factory.forEach(Transport.class)
        .filter(transport -> transport.getEmployees().size() > transport.getCapacity())
        .penalizeLong("max capacity conflict",
                HardMediumSoftLongScore.ONE_HARD, transport -> transport.getEmployees().size() - transport.getCapacity());
}

private Constraint transportCapacity(ConstraintFactory factory) {
return factory.forEach(Transport.class)
        .filter(transport -> !transport.getEmployees().isEmpty())
        .filter(transport -> transport.getEmployees().size() < transport.getCapacity())
        .penalizeLong("optimal placement conflict",
                HardMediumSoftLongScore.ONE_SOFT, transport -> transport.getCapacity() - transport.getInspectorList().size());
}
user_194159690
Related