Developing Planning Solution Using OptaPlanner

Introduction

Thanks for reading this blog, in this blog I am sharing my experience with Red Hat JBoss Business Resource Planner (OptaPlanner). This is just beginner level of tutorial. If you already familiar with OptaPlanner, this may not be the right place for you.

If you want to know more information about OptaPlanner, please visit http://www.optaplanner.org/ and https://access.redhat.com/documentation/en-us/red_hat_jboss_brms/6.4/html/business_resource_planner_guide/
 for more information.

In this tutorial, I used a simple use case for developing a planning solution. Lets start with use case.

Source code for this tutorial is available from github (https://github.com/sprabakkar/optaplanner.git).

Use case

A Cleaning Service Company cleans houses. It needs to assign cleaners to houses in a weekly basis.

Each house has many cleaning spots like kitchen, bathroom, common area etc...each cleaning spots cleaned by individual cleaner. So each has to cleaned by more than two cleaners.

A cleaner works from Monday to Friday. some cleaners may take leave due to personal reasons.

A cleaner can clean one house per day, he can not assigned to another house on the same day. Some time house may not be cleaned due to absent (due to various reasons like sick, etc)of cleaner .

We have our use case ready, now, lets start to find the planning solution.

1 - Solver Configuration

First we need to start with Solver Configuration, to do that we need to know our planning entity, planning variable, solution class and business rules (score constraints) for score calculation. To get those details we need to design a proper domain model from the use case. Please refer the product documentation for more information regarding planning entity and planning variable.

1.1 Domain Object Model

In our house cleaning use case, Cleaner, HouseCleaningSpot, House, Location, DayOfWeeek and CleaningSolution are the identified objects,

Class Diagram for Cleaning Problem Use case

Planning entity changes during solving, planning entity has one or more planing variables. Planning variable points to planning value, which changes during planning, between score calculations.

From the domain object model, in many to one relationship the many side is the Planning Entity.

From the above domain model, HouseCleaningSpot is the Planning Entity, Cleaner object is the Planning Variable.

CleaningSolution is the Planning Solution Class. Solution represents a planning problem and a possible solution of that problem.

1.2 Score Calculation

Score is a result of the score function on a single possible solution. Every initialized solution has a score. The beast solution is the solution with the highest score. Planner cannot automatically know which Solution is best for your business, so you need to tell it how to calculate the score of a given Solution according to your business needs.

Now we need to identify the business rules from the use case for score calculation. In this tutorial we are using drools for score calculation. So we need to create a drl file for identified business rule for score calculation.

As I mentioned earlier, I am going to use just few rules which is important for this tutorial.

I have one hard constraint(*) , one medium constraint and one soft constraint.

1.2.1 Hard constraint

Business Rule: each cleaner work one (spot) house per day only,

Rule:

// ############################################################################

// Hard constraints

// ############################################################################

rule "Conflict: 1 cleaner has to clean 2 houses on the same day of week"

when

HouseCleaningSpot($c : cleaner, cleaner != null, $d : house.dayOfWeek.dayId, $leftId : id)

HouseCleaningSpot(cleaner == $c, house.dayOfWeek.dayId == $d, id > $leftId)

then

scoreHolder.addHardConstraintMatch(kcontext, -1);

end

1.2.2 Medium Constraint

Business Rule: A cleaner may go for absent due to personal reasons,

Rule:

// ############################################################################

// Medium constraints

// ############################################################################

rule "overconstrained: leave as little possible unassigned spots"

when

HouseCleaningSpot(cleaner == null)

then

scoreHolder.addMediumConstraintMatch(kcontext, -1);

end

1.2.3 Soft Constraint

Business Rule: A cleaner can assigned to the nearest workstation from their resident.

Rule:

// ############################################################################

// Soft constraints

// ############################################################################

rule "Minimize traveling distance"

when

HouseCleaningSpot($d : distanceFromCleanerToHouse)

then

scoreHolder.addSoftConstraintMatch(kcontext, -$d);

end

1.3 Optimization Algorithm

In this tutorial we are using Construction Heuristic, FIRST_FIT. Please refer the product documentation for available algorithms.

At this point we are ready for solver configuration,

Solver configuration xml file looks as follows, using this file we define and configure planning entity, solution class, score function and optimization algorithms.

<?xml version="1.0" encoding="UTF-8"?>

<solver>

<solutionClass>com.acme.planning.model.CleaningSolution</solutionClass>

<entityClass>com.acme.planning.model.HouseCleaningSpot</entityClass>

<scoreDirectorFactory>

<scoreDefinitionType>HARD_MEDIUM_SOFT</scoreDefinitionType>

<scoreDrl>com/acme/planner/solver/cleaningPlanScoreRules.drl</scoreDrl>

</scoreDirectorFactory>

<termination>

<minutesSpentLimit>1</minutesSpentLimit>

</termination>

<constructionHeuristic>

<constructionHeuristicType>FIRST_FIT</constructionHeuristicType>

</constructionHeuristic>

<localSearch>

<acceptor>

<lateAcceptanceSize>400</lateAcceptanceSize>

<entityTabuSize>3</entityTabuSize>

</acceptor>

<forager>

<acceptedCountLimit>1000</acceptedCountLimit>

</forager>

</localSearch>

</solver>

2 - Build Solver

A solver solves a planning problem. Solver build from the a solver configuration (build from the above step one).

Solver solver = new CleaningSolutionApp().createSolver();

protected Solver createSolver() {

SolverFactory solverFactory = SolverFactory

.createFromXmlResource(SOLVER_CONFIG);

Solver solver = solverFactory.buildSolver();

solver.addEventListener(new SolverEventListener() {

public void bestSolutionChanged(BestSolutionChangedEvent event) {

CleaningSolution bestSolution = (CleaningSolution) event

.getNewBestSolution();

}

});

return solver;

}

3 - Load Problem

CleaningSolution is the Planning Solution Class. (Planning) Solution represents a planning problem and a possible solution of that problem.

Build the CleaningSolution object with problem data set, In our case Cleaners and HouseCleaningSpot objects.

Solver solver = new CleaningSolutionApp().createSolver();

CleaningSolution unsolvedCleaningSolution = createCleaningSolution();

solver.solve(unsolvedCleaningSolution);

private static CleaningSolution createCleaningSolution() {

CleaningSolution unsolvedCleaningProblem = new CleaningSolution();

List<Cleaner> clist = createCleaners();

List<HouseCleaningSpot> hsclist = createHouseCleaningSpot();

unsolvedCleaningProblem.setCleanerList(clist);

unsolvedCleaningProblem.setHouseCleaningSpotList(hsclist);

return unsolvedCleaningProblem;

}

4 - Solve Problem

Solver getBestSolution() method returns CleaningSolution instance with every HouseCleaningSpot assigned to a cleaner.

CleaningSolution solvedCloudBalance = (CleaningSolution) solver.getBestSolution();

Problem Solution

===========================================================

House Id is ::: A

Cleaning spot 101 assigned to cleaner 111 on Monday

Cleaning spot 102 assigned to cleaner 112 on Monday

Cleaning spot 103 assigned to cleaner 113 on Monday

===========================================================

House Id is ::: B

Cleaning spot 201 assigned to cleaner 111 on Tuesday

Cleaning spot 202 assigned to cleaner 112 on Tuesday

===========================================================

House Id is ::: C

Cleaning spot 301 assigned to cleaner 111 on Wednesday

Cleaning spot 302 assigned to cleaner 112 on Wednesday

Cleaning spot 303 assigned to cleaner 113 on Wednesday

Cleaning spot 304 assigned to cleaner 114 on Wednesday

Cleaning spot 305 assigned to cleaner 115 on Wednesday

===========================================================

House Id is ::: D

Cleaning spot 401 assigned to cleaner 111 on Thursday

Cleaning spot 402 assigned to cleaner 112 on Thursday

===========================================================

House Id is ::: E

Cleaning spot 501 assigned to cleaner 111 on Friday

Cleaning spot 502 assigned to cleaner 112 on Friday

Cleaning spot 503 assigned to cleaner 113 on Friday

===========================================================

House Id is ::: F

Cleaning spot 601 assigned to cleaner 116 on Wednesday

Cleaning spot 602 assigned to cleaner 117 on Wednesday

Cleaning spot 603 assigned to cleaner 118 on Wednesday

===========================================================

-End-