How to choose a car and optimally accommodate passengers in it?

user_19415969 0
Viewed 63

Based on my previous question 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;

    @PlanningVariable(valueRangeProviderRefs = "transportRange")
    private Transport transport;
}

Transport:

@PlanningEntity
public class Transport {

    @PlanningId
    private Long id;
    private Integer capacity;

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

    public int countEmptySeats() {
        return seatsNumber - inspectors.size();
    }
    
}


@PlanningEntity
class Transport {

    @PlanningId
    Long id;
    
    @InverseRelationShadowVariable(sourceVariableName = "transport")
    List<Employee> employees = 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;
    }
}

Constraints:

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());
}

private Constraint optimalVehicleConflict(ConstraintFactory factory) {
        return factory.forEach(Transport.class)
                .filter(transport -> transport.getEmployees().isEmpty())
                .penalize("Empty transport", HardMediumSoftLongScore.ONE_SOFT, vehicle -> (int) Math.pow(transport.countEmptySeats(), 2));
    }

The problem: When I have vehicle with capacities: 17, 6, 2, 2, 2 and 6 passengers then as a result I get 3 vehicles with 2 passengers instead of 1 vehicle with capacity 6.

+---------+-----------+
| vehicle | employees |
+---------+-----------+
|      17 |         - |
|       6 |         - |
|       2 |         2 |
|       2 |         2 |
|       2 |         2 |
+---------+-----------+

How I can solve this problem? Thanks in advance!

optaplanner java
1 Answers

You should write a constraint which penalizes empty vehicles, and give it sufficient weight. Such a constraint could look like this, in theory:

constraintFactory.forEach(Transport.class)
    .filter(transport -> transport.isEmpty())
    .penalize("Empty vehicle", HardSoftScore.ONE_SOFT, 
        transport -> Math.pow(transport.countEmptySeats(), 2))

Do note that:

  • The constraint weight is soft. You may want to consider making this a hard constraint, if this is of an utmost importance.
  • The match weight is based on the number of empty seats, and it grows quickly. This is important - if a vehicle has more empty seats, it will incur a larger penalty, the assumption being that bigger vehicles are more expensive to run. You may find a different way of factoring that in.

However, I believe that your model above is broken. As far as I know, PlanningListVariable can not be used as any other collection. It is specifically designed to model a chain - for example, the list would represent a route of a vehicle, each item one stop on the route. The list defines a precedence relationship, where your model has none. Have you seen this actually work at runtime? (I'd be surprised if it did, but it is possible that I do not yet fully understand this new and as of yet undocumented feature.)

I can think of two ways of modelling the problem, each with its own pros and cons:

  • Have one planning entity per seat in a transport. Make that entity's variable (the employee) nullable. And then write a constraint which penalizes vehicles per empty seats.

  • Have employee be the entity, and assign transports to them. If a transport has no employees, it gets a penalty. If a transport has more employees than seats, it gets a (very) hard penalty.

I'd probably prefer the latter, as I foresee it will lead to less struggle further down the line.

user_67940630
Related