JBoss.orgCommunity Documentation
Table 3.1. Examples overview
Example  Domain  Size  Competition?  Special features used 

N queens 


 None 
Cloud balancing 


 
Traveling salesman 


 
Dinner party 




Tennis club scheduling 


 
Course timetabling 


 
Machine reassignment 


 
Vehicle routing 


 
Vehicle routing with time windows  Extra on Vehicle routing:


 
Project job scheduling 


 
Hospital bed planning 




Exam timetabling 


 
Employee rostering 


 
Traveling tournament 


 None 
Cheap time scheduling 


 None 
A realistic competition is an official, independent competition:
that clearly defines a realword use case
with realworld constraints
with multiple, realworld datasets
that expects reproducible results within a specific time limit on specific hardware
that has had serious participation from the academic and/or enterprise Operations Research community
These realistic competitions provide an objective comparison of OptaPlanner with competitive software and academic research.
This documentation heavily uses the 4 queens puzzle as the primary example.
The above solution is wrong because queens A1
and B0
can attack each
other (so can queens B0
and D0
). Removing queen B0
would respect the "no 2 queens can attack each other" constraint, but would break the "place n queens"
constraint.
Below is a correct solution:
All the constraints have been met, so the solution is correct. Note that most n queens puzzles have multiple correct solutions. We'll focus on finding a single correct solution for a given n, not on finding the number of possible correct solutions for a given n.
public class Column {
private int index;
// ... getters and setters
}
public class Row {
private int index;
// ... getters and setters
}
public class Queen {
private Column column;
private Row row;
public int getAscendingDiagonalIndex() {...}
public int getDescendingDiagonalIndex() {...}
// ... getters and setters
}
public class NQueens implements Solution<SimpleScore> {
private int n;
private List<Column> columnList;
private List<Row> rowList;
private List<Queen> queenList;
private SimpleScore score;
// ... getters and setters
}
When 2 queens share the same column, row or diagonal line, such as (*) and (**), they can attack each other.
Given a list of cities, find the shortest tour for a salesman that visits each city exactly once.
The problem is defined by Wikipedia. It is one of the most intensively studied problems in computational mathematics. Yet, in the real world, it's often only part of a planning problem, along with other constraints, such as employee shift rostering constraints.
Miss Manners is throwing another dinner party.
This time she invited 144 guests and prepared 12 round tables with 12 seats each.
Every guest should sit next to someone (left and right) of the opposite gender.
And that neighbour should have at least one hobby in common with the guest.
And the 2 politicians, 2 doctors, 2 coaches and 2 programmers shouldn't be the same kind at a table.
Schedule each lecture into a timeslot and into a room.
The problem is defined by the International Timetabling Competition 2007 track 3.
The problem is defined by the Google ROADEF/EURO Challenge 2012.
Besides the basic case (CVRP), there is also a variant with time windows (CVRPTW).
The capacitated vehicle routing problem (CVRP) and it's timewindowed variant (CVRPTW) are defined by the VRP web.
CVRP instances (without time windows):
An32k5 has 1 depots, 5 vehicles and 31 customers with a search space of 10^46. An33k5 has 1 depots, 5 vehicles and 32 customers with a search space of 10^48. An33k6 has 1 depots, 6 vehicles and 32 customers with a search space of 10^48. An34k5 has 1 depots, 5 vehicles and 33 customers with a search space of 10^50. An36k5 has 1 depots, 5 vehicles and 35 customers with a search space of 10^54. An37k5 has 1 depots, 5 vehicles and 36 customers with a search space of 10^56. An37k6 has 1 depots, 6 vehicles and 36 customers with a search space of 10^56. An38k5 has 1 depots, 5 vehicles and 37 customers with a search space of 10^58. An39k5 has 1 depots, 5 vehicles and 38 customers with a search space of 10^60. An39k6 has 1 depots, 6 vehicles and 38 customers with a search space of 10^60. An44k7 has 1 depots, 7 vehicles and 43 customers with a search space of 10^70. An45k6 has 1 depots, 6 vehicles and 44 customers with a search space of 10^72. An45k7 has 1 depots, 7 vehicles and 44 customers with a search space of 10^72. An46k7 has 1 depots, 7 vehicles and 45 customers with a search space of 10^74. An48k7 has 1 depots, 7 vehicles and 47 customers with a search space of 10^78. An53k7 has 1 depots, 7 vehicles and 52 customers with a search space of 10^89. An54k7 has 1 depots, 7 vehicles and 53 customers with a search space of 10^91. An55k9 has 1 depots, 9 vehicles and 54 customers with a search space of 10^93. An60k9 has 1 depots, 9 vehicles and 59 customers with a search space of 10^104. An61k9 has 1 depots, 9 vehicles and 60 customers with a search space of 10^106. An62k8 has 1 depots, 8 vehicles and 61 customers with a search space of 10^108. An63k10 has 1 depots, 10 vehicles and 62 customers with a search space of 10^111. An63k9 has 1 depots, 9 vehicles and 62 customers with a search space of 10^111. An64k9 has 1 depots, 9 vehicles and 63 customers with a search space of 10^113. An65k9 has 1 depots, 9 vehicles and 64 customers with a search space of 10^115. An69k9 has 1 depots, 9 vehicles and 68 customers with a search space of 10^124. An80k10 has 1 depots, 10 vehicles and 79 customers with a search space of 10^149. Fn135k7 has 1 depots, 7 vehicles and 134 customers with a search space of 10^285. Fn45k4 has 1 depots, 4 vehicles and 44 customers with a search space of 10^72. Fn72k4 has 1 depots, 4 vehicles and 71 customers with a search space of 10^131.
CVRPTW instances (with time windows):
Solomon_025_C101 has 1 depots, 25 vehicles and 25 customers with a search space of 10^34. Solomon_025_C201 has 1 depots, 25 vehicles and 25 customers with a search space of 10^34. Solomon_025_R101 has 1 depots, 25 vehicles and 25 customers with a search space of 10^34. Solomon_025_R201 has 1 depots, 25 vehicles and 25 customers with a search space of 10^34. Solomon_025_RC101 has 1 depots, 25 vehicles and 25 customers with a search space of 10^34. Solomon_025_RC201 has 1 depots, 25 vehicles and 25 customers with a search space of 10^34. Solomon_100_C101 has 1 depots, 25 vehicles and 100 customers with a search space of 10^200. Solomon_100_C201 has 1 depots, 25 vehicles and 100 customers with a search space of 10^200. Solomon_100_R101 has 1 depots, 25 vehicles and 100 customers with a search space of 10^200. Solomon_100_R201 has 1 depots, 25 vehicles and 100 customers with a search space of 10^200. Solomon_100_RC101 has 1 depots, 25 vehicles and 100 customers with a search space of 10^200. Solomon_100_RC201 has 1 depots, 25 vehicles and 100 customers with a search space of 10^200. Homberger_0200_C1_2_1 has 1 depots, 50 vehicles and 200 customers with a search space of 10^460. Homberger_0200_C2_2_1 has 1 depots, 50 vehicles and 200 customers with a search space of 10^460. Homberger_0200_R1_2_1 has 1 depots, 50 vehicles and 200 customers with a search space of 10^460. Homberger_0200_R2_2_1 has 1 depots, 50 vehicles and 200 customers with a search space of 10^460. Homberger_0200_RC1_2_1 has 1 depots, 50 vehicles and 200 customers with a search space of 10^460. Homberger_0200_RC2_2_1 has 1 depots, 50 vehicles and 200 customers with a search space of 10^460. Homberger_0400_C1_4_1 has 1 depots, 100 vehicles and 400 customers with a search space of 10^1040. Homberger_0400_C2_4_1 has 1 depots, 100 vehicles and 400 customers with a search space of 10^1040. Homberger_0400_R1_4_1 has 1 depots, 100 vehicles and 400 customers with a search space of 10^1040. Homberger_0400_R2_4_1 has 1 depots, 100 vehicles and 400 customers with a search space of 10^1040. Homberger_0400_RC1_4_1 has 1 depots, 100 vehicles and 400 customers with a search space of 10^1040. Homberger_0400_RC2_4_1 has 1 depots, 100 vehicles and 400 customers with a search space of 10^1040. Homberger_0600_C1_6_1 has 1 depots, 150 vehicles and 600 customers with a search space of 10^1666. Homberger_0600_C2_6_1 has 1 depots, 150 vehicles and 600 customers with a search space of 10^1666. Homberger_0600_R1_6_1 has 1 depots, 150 vehicles and 600 customers with a search space of 10^1666. Homberger_0600_R2_6_1 has 1 depots, 150 vehicles and 600 customers with a search space of 10^1666. Homberger_0600_RC1_6_1 has 1 depots, 150 vehicles and 600 customers with a search space of 10^1666. Homberger_0600_RC2_6_1 has 1 depots, 150 vehicles and 600 customers with a search space of 10^1666. Homberger_0800_C1_8_1 has 1 depots, 200 vehicles and 800 customers with a search space of 10^2322. Homberger_0800_C2_8_1 has 1 depots, 200 vehicles and 800 customers with a search space of 10^2322. Homberger_0800_R1_8_1 has 1 depots, 200 vehicles and 800 customers with a search space of 10^2322. Homberger_0800_R2_8_1 has 1 depots, 200 vehicles and 800 customers with a search space of 10^2322. Homberger_0800_RC1_8_1 has 1 depots, 200 vehicles and 800 customers with a search space of 10^2322. Homberger_0800_RC2_8_1 has 1 depots, 200 vehicles and 800 customers with a search space of 10^2322. Homberger_1000_C110_1 has 1 depots, 250 vehicles and 1000 customers with a search space of 10^3000. Homberger_1000_C210_1 has 1 depots, 250 vehicles and 1000 customers with a search space of 10^3000. Homberger_1000_R110_1 has 1 depots, 250 vehicles and 1000 customers with a search space of 10^3000. Homberger_1000_R210_1 has 1 depots, 250 vehicles and 1000 customers with a search space of 10^3000. Homberger_1000_RC110_1 has 1 depots, 250 vehicles and 1000 customers with a search space of 10^3000. Homberger_1000_RC210_1 has 1 depots, 250 vehicles and 1000 customers with a search space of 10^3000.
The vehicle routing with timewindows domain model makes heavily use of shadow variables. This allows it to express its constraints more
naturally, because properties such as arrivalTime
and departureTime
, are
directly available on the domain model.
For the optimization algorithm, this doesn't matter much, as long as the distance between 2 points can be looked up (and are preferably precalculated). The road cost doesn't even need to be a distance, it can also be travel time, fuel cost, or a weighted function of those. There are several Google Maps like technologies available to precalculate road costs, such as GraphHopper (embeddable, offline Java engine) and Open MapQuest (web service). There are also several technologies to render it, such as Leaflet.
Take special care that the road costs between 2 points use the same optimization criteria as the one used in OptaPlanner. For example, GraphHopper etc will by default return the fastest route, not the shortest route. Don't use the km (or miles) distances of the fastest GPS routes to optimize the shortest trip in OptaPlanner: this leads to a suboptimal solution as shown below:
Contrary to popular belief, most users don't want the shortest route: they want the fastest route instead. They prefer highways over normal roads. They prefer normal roads over dirt roads. In the real world, the fastest and shortest route are rarely the same.
This problem features overconstrained datasets.
The problem is a variant on Kaho's Patient Scheduling and the datasets come from real world hospitals.
Soft constraints (each of which has a parametrized penalty):
Period spread: 2 exams that share students should be a number of periods apart.
Mixed durations: 2 exams that share a room should not have different durations.
Front load: Large exams should be scheduled earlier in the schedule.
Period penalty (specified per dataset): Some periods have a penalty when used.
Room penalty (specified per dataset): Some rooms have a penalty when used.
It uses large test data sets of reallife universities.
The problem is defined by the International Timetabling Competition 2007 track 1. Geoffrey De Smet finished 4th in that competition with a very early version of OptaPlanner. Many improvements have been made since then.
Below you can see the main examination domain classes:
Notice that we've split up the exam concept into an Exam
class and a
Topic
class. The Exam
instances change during solving (this is the
planning entity class), when their period or room property changes. The Topic
,
Period
and Room
instances never change during solving (these are problem
facts, just like some other classes).
For each shift, assign a nurse to work that shift.
The problem is defined by the International Nurse Rostering Competition 2010.
Schedule matches between n teams.
The problem is defined on Michael Trick's website (which contains the world records too).
Soft constraints (addendum to the original problem definition):