Home > Enterprise >  How to solve the problem - after the optimization, there is vehicles with employees who have no jobs
How to solve the problem - after the optimization, there is vehicles with employees who have no jobs

Time:08-04

  1. need to place employees in cars
  2. need to allocate work to employees

Here is the source code: Models:

@PlanningEntity
public class Job {

    @PlanningId
    private Long id;
    
    private String address;

    @PlanningVariable(valueRangeProviderRefs = "employeeRange")
    private Employee employee;

    private String direction;

}

@PlanningEntity
public class Employee {

    @PlanningId
    private Long id;

    private String name;

    private String direction;

    private Integer minJobCount;

    private Integer maxJobCount;

    @InverseRelationShadowVariable(sourceVariableName = "employee")
    private List<Job> jobs = new ArrayList<>();

    @PlanningVariable(valueRangeProviderRefs = "vehicleRange")
    private Vehicle vehicle;
}

@AllArgsConstructor
public class Vehicle {

    @PlanningId
    private Long id;

    private Integer seatingCapacity;

    @InverseRelationShadowVariable(sourceVariableName = "vehicle")
    List<Employee> employees = new ArrayList<>();

}


@PlanningSolution
public class Solution {

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

    @PlanningEntityCollectionProperty
    private List<Job> jobs;

    @ProblemFactCollectionProperty
    @ValueRangeProvider(id = "vehicleRange")
    private List<Vehicle> vehicles;

    @PlanningScore
    private HardMediumSoftLongScore score;

    public Plan(List<Inspector> inspectors, List<Job> jobs, List<Vehicle> vehicles) {
        this.inspectors = inspectors;
        this.applications = applications;
        this.vehicles = vehicles;
    }

}

Constraints:

public class CustomConstraintProvider implements ConstraintProvider {

    @Override
    public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
        return new Constraint[]{
                minNumberConflict(constraintFactory),
                maxNumberConflict(constraintFactory),
                directionConflict(constraintFactory),
                vehicleCapacity(constraintFactory),
                vehicleMaxCapacity(constraintFactory)
        };
    }

    private Constraint minNumberConflict(ConstraintFactory constraintFactory) {
        return constraintFactory.forEach(Job.class).groupBy(Job::getEmployee, count())
                .filter((employee, count) -> employee.getMinNumber() > count)
                .penalize("MIN_INSPECTION_COUNT_CONFLICT",
                        HardMediumSoftLongScore.ONE_MEDIUM, (employee, count) -> employee.getMinNumber() - count);
    }

    private Constraint maxNumberConflict(ConstraintFactory constraintFactory) {
        return constraintFactory.forEach(Job.class).groupBy(Job::getEmployee, count())
                .filter((employee, count) -> count > employee.getMaxNumber())
                .penalize("MAX_INSPECTION_COUNT_CONFLICT",
                        HardMediumSoftLongScore.ONE_HARD, (employee, count) -> count - employee.getMaxNumber());
    }

    private Constraint directionConflict(ConstraintFactory constraintFactory) {
        return constraintFactory.forEach(Job.class)
                .filter(job -> !job.getEmployee().getDirection()
                        .equals(job.getAdministrativeDivision()))
                .penalize("DIRECTION_CONFLICT", HardMediumSoftLongScore.ONE_HARD);
    }

    private Constraint vehicleMaxCapacity(ConstraintFactory factory) {
        return factory.forEach(Vehicle.class)
                .filter(vehicle -> vehicle.getEmployees().size() > vehicle.getSeatingCapacity())
                .penalizeLong("TOTAL_CAPACITY_CONFLICT",
                        HardMediumSoftLongScore.ONE_HARD, vehicle -> vehicle.getEmployees().size() - vehicle.getSeatingCapacity());
    }

    private Constraint vehicleCapacity(ConstraintFactory factory) {
        return factory.forEach(Vehicle.class)
                .filter(vehicle -> !vehicle.getEmployees().isEmpty())
                .filter(vehicle -> vehicle.getEmployees().size() < vehicle.getSeatingCapacity())
                .penalizeLong("OPTIMAL_EMPLOYEES_PLACEMENT_CONFLICT",
                        HardMediumSoftLongScore.ONE_SOFT, vehicle -> vehicle.getSeatingCapacity() - vehicle.getEmployees().size());
    }

}

Input parameters:

  • Vehicle with capacity: 17, 17, 2, 6, 2, 2
  • Employees number - 6
  • Jobs - 30

Result:

┌┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┐
├┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┼┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┤
│               Vehicle                 │            Vehicle capacity          │
├┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┼┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┤
├┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┤
│              Nəqliyayt: 6732350370761100881 - capacity: 2                    │
├───────────────────────────────────────┬──────────────────────────────────────┤
│8930883530776265424                    │Job        {id=4150490238027319537}   │
│                                       │Job        {id=4707535022401407092}   │
│                                       │Job        {id=631702768559803139}    │
│                                       │Job        {id=4473385357049938675}   │
│                                       │Job        {id=7920716917533527363}   │
│                                       │Job        {id=2052525520996550776}   │
├───────────────────────────────────────┼──────────────────────────────────────┤
│6474786395546274699                    │                                      │
├┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┼┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┤
├┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┤
│              Vehicle: 6598109476345237345 - capacity: 2                      │
├───────────────────────────────────────┬──────────────────────────────────────┤
│8939243370145989526                    │Job        {id=9145445512850195611}   │
│                                       │Job        {id=1287792664485382814}   │
├───────────────────────────────────────┼──────────────────────────────────────┤
│1162213509116611091                    │Job        {id=9185386477906185129}   │
├┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┼┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┤
├┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┤
│              Vehicle: 5217106628424059704 - capacity: 2                      │
├───────────────────────────────────────┬──────────────────────────────────────┤
│7361941555795543986                    │Job        {id=8818040969169815329}   │
│                                       │Job        {id=4018994000382545633}   │
│                                       │Job        {id=3336748836211279270}   │
│                                       │Job        {id=448960811141515624}    │
│                                       │Job        {id=5269646864048277907}   │
├───────────────────────────────────────┼──────────────────────────────────────┤
│7873415553511670835                    │Job        {id=5192891860283509924}   │
│                                       │Job        {id=6649801262843315756}   │
│                                       │Job        {id=850844391421461690}    │
│                                       │Job        {id=4090598636979374614}   │
│                                       │Job        {id=9214572757237514987}   │
│                                       │Job        {id=4231472489001798330}   │
├┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┼┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┤
└┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┘

Problem: Employee with ID 6474786395546274699 must not be placed to the vehicle because he has no jobs

CodePudding user response:

Write a hard constraint that penalizes situations where there is a jobless employee in a vehicle - the solver will then work to minimize the total penalty. In the case of the model shown above, that constraint could look like this:

constraintFactory.forEach(Employee.class)
    .ifNotExists(Job.class,
        Joiners.equal(Function.identity(), Job::getEmployee)
    .penalize("Jobless employee in a vehicle", 
        HardMediumSoftLongScore.ONE_HARD);

forEach(Employee.class) makes sure you will only get initialized employees, therefore you are guaranteed they are in a vehicle. The ifNotExists(...) part is conditional propagation.

However, there is a problem with this model. Your @PlanningVariable will always assign employees to vehicles. If null is a valid option for employee vehicle, you need to make sure your @PlanningVariable is nullable..

  • Related