OptaPlanner continues as Timefold

Google OR-Tools versus Timefold comparison

Google OR-Tools and Timefold are open source mathematical optimization solvers. Both are fast and scalable solvers, used across the globe by a large user base in production. They have similarities, but also differences.

This comparison is written by the Timefold team to guide you through the fundamental differences in these technologies. We aim to present correct and truthful information. However, it’s important to acknowledge our natural bias towards Timefold.

Number of solvers

OR-Tools

OR-Tools has individual solvers for Constraint Programming (CP), Mixed-Integer Programming (MIP), Vehicle Routing (VRP) and Graph Algorithms. Each solver has its own API, tailored to a specific set of use cases.

OR-Tools comes with a set of examples for each of these solvers to learn the different APIs easily.

Timefold

Timefold is one solver, with a unified API that handles any use case with any combination of constraints. It can solve hybrid problems, such as Vehicle Routing with a constraint to distribute the workload fairly across drivers (a typical constraint of Employee Rostering).

Timefold comes with a GitHub quickstarts repo that provides a starting point for each use case, such as Vehicle Routing with Time Windows.

Define a model

Define a model (non vehicle routing)

Both OR-Tools CP and Timefold require you to define your model with optimization variables, so the mathematical optimization software knows which decisions it needs to make.

OR-Tools CP

OR-Tools’s CP solver supports 3 types of optimization variables: booleans, integers and floating point numbers. You can define your planning model in those types.

For example, you can use model.newBoolVar() to model the assignment of a particular employee to a particular shift:

// Input
CpModel model = ...
IntVar[][] assignments = new IntVar[shifts.size()][employees.size()];
for (int s = 0; s < shifts.size(); s++) {
    for (int e = 0; e < employees.size(); e++) {
        assignments[s][e] = model.newBoolVar(...);
    }
}
... // Add constraints to enforce no shift is assigned to multiple employees

// Solve
solver.solve(model);

// Output
for (int s = 0; s < shifts.size(); s++) {
    for (int e = 0; e < employees.size(); e++) {
        if (value(assignments[s][e]) == 1L) {
            print(shifts[s] + " is assigned to " + employees[e]);
        }
    }
}

Timefold

Timefold supports any type of optimization variables, including your custom classes (Employee, Vehicle, …​) and standard classes (Integer, BigDecimal, LocalDate, …​). You typically define your planning model in your own domain classes.

For example, you can use @PlanningVariable on your Shift.employee field to model the assignment of an employee to a shift:

@PlanningEntity
class Shift { // User defined class
    ... // Shift id, date, start time, required skills, ...

    @PlanningVariable
    Employee employee;
}

class Employee { // User defined class
  ... // Name, skills, ...
}

@PlanningSolution
class TimeTable { // User defined class
    List<Employee> employees;
    List<Shift> shifts;
}

// Input
Timetable timetable = new Timetable(shifts, employees);

// Solve
timetable = Solver.solve(timetable);

// Output
for (Shift shift : timetable.shifts) {
    print(shift + " is assigned to " + shift.employee);
}

None of these classes (Shift, Employee and Timetable) exist in Timefold itself: you define and shape them. Your code naturally represents employees as instances of the Employee class, shifts as instances of the Shift class, and so forth.

Timefold supports Object-Oriented Programming (OOP) input, including polymorphism.

Search space comparison

In the code above for employee scheduling, OR-Tools uses boolean variables and Timefold uses employee variables.

This has an effect on the search space:

  • OR-Tools’s CP solver creates a boolean variable for every (shift, employee) combination. Given 2000 shifts and 100 employees, that’s an array of 200 000 elements.

  • On the other hand, Timefold creates an Employee variable for every Shift. Given 2000 shifts and 100 employees, that’s an array of 2000 elements.

Domain model comparison

The Timefold model naturally enforces the one shift per employee hard constraint by design, the OR-Tools CP model implements it.

Define a vehicle routing model

OR-Tools Vehicle Routing

OR-Tools has a separate API for Vehicle Routing based on OR-Tools’s RoutingModel class which comes with a fixed number of constraints out-of-the-box:

// Input
RoutingIndexManager manager = new RoutingIndexManager(locationListSize, vehicleListSize, 0);
RoutingModel routingModel = new RoutingModel(manager); // OR-Tools defined class
routingModel.setArcCostEvaluatorOfAllVehicles(...);
routingModel.addDimensionWithVehicleCapacity(...);

// Solve
Assignment assignment = routingModel.solve();

// Output
for (int i = 0; i < vehiclesCount; i++) {
    long index = routingModel.start(i);
    print("Vehicle " + i + ": ");
    while (!routing.isEnd(index)) {
      print(manager.indexToNode(index) + ", ");
      index = solution.value(routing.nextVar(index));
    }
}

Timefold

Timefold solves Vehicle Routing like any other planning problem, but provides building blocks for Vehicle Routing, such as list variables (and shadow variables to calculate the arrival time):

@PlanningEntity
class Vehicle { // User defined class
    ... // start time, start location, capacity, skills, ...

    @PlanningListVariable
    List<Visit> visits;
}

class Visit { // User defined class
    ... // location, demand, time window(s), ...
}

// Input
VehicleRoutePlan plan = new VehicleRoutePlan(vehicles, visits);

// Solve
plan = Solver.solve(plan);

// Output
for (Vehicle vehicle : plan.vehicles) {
    print(vehicle + ": " + vehicle.visits);
}

On the base model, you can add complex constraints, such as floating lunch breaks, multi-vehicle visits and any other custom constraint.

Constraints

OR-Tools CP

OR-Tools’s CP solver constraints are implemented as mathematical equations.

For example, to assign at most one shift per day, you add an equation s1 + s2 + s3 <= 1 for all shifts on day 1, an equation s4 + s5 <= 1 for all shifts on day 2, and so forth:

for (int e = 0; e < employees.size(); e++) {
    for (int d = 0; d < dates.size(); d++) {
        IntVar[] vars = new IntVar[...];
        int i = 0;
        for (int s = 0; s < shifts.size(); s++) {
            // If the shift is on the date
            if (shifts[s].date == dates[d])) {
                vars[i++] = assignments[s][e];
            }
        }
        model.addLessOrEqual(LinearExpr.sum(vars), 1);
    }
}

OR-Tools Vehicle Routing

OR-Tool’s VRP solver comes with a fixed number of constraints out-of-the-box, such as time windows. You can find all the available constraints on the RoutingModel class.

Timefold

Timefold constraints are implemented as programming code.

For example, to assign at most one shift per day, select every pair of Shift instances that have the same date and the same employee, to penalize matching pairs as a hard constraint:

// For every shift ...
constraintFactory.forEach(Shift.class)
    // ... combined with any other shift ...
    .join(Shift.class,
        // ... on the same date ...
        equal(shift -> shift.date),
        // ... assigned to the same employee ...
        equal(shift -> shift.employee))
    // ... penalize one broken hard constraint per pair.
    .penalize(HardSoftScore.ONE_HARD)
    .asConstraint("One shift per day");

Timefold’s ConstraintStreams API uses a Functional Programming (FP) approach, so it can run delta calculations under the hood for maximum scalability and performance.

Constraints can reuse existing code. For example, because date is an instance of LocalDate (a Date and Time API), you can use LocalDate.isDayOfWeek() to select 2 shifts on the same day of week:

        // ... on the same day of week ...
        equal(shift -> shift.date.getDayOfWeek())

Date and times arithmetic is notoriously difficult, because of Daylight Saving Time (DST), timezones, leap years and other intricacies. Timefold allows you to directly use any 3th-party API (such as LocalDate) in your constraints.

Besides the equal() joiner, Timefold provides lessThan(), greaterThan(), lessThanOrEqual(), greaterThanOrEqual(), overlapping(), etc. It automatically applies indexing (hashtable techniques) on joiners for performance.

It has higher level abstractions. For example, select two overlapping shifts with the overlapping() joiner (even if they start or end at different times):

        // ... that overlap ...
        overlapping(shift -> shift.startDateTime, shift -> shift.endDateTime)

Besides the join() construct, Timefold supports filter(), groupBy(), ifExists(), ifNotExists(), map(), etc.

For example, allow employees that can work double shifts to work double shifts by filtering out all employees that work double shifts with a filter():

// For every shift ...
constraintFactory.forEach(Shift.class)
    // ... assigned to an employee that does not work double shifts ...
    .filter(shift -> !shift.employee.worksDoubleShifts)
    // ... combined with any other shift ...
    .join(Shift.class,
        equal(shift -> shift.date),
        // ... assigned to that same employee that does not work double shifts ...
        equal(shift -> shift.employee))
    .penalize(HardSoftScore.ONE_HARD)
    .asConstraint("One shift per day");

The groupBy() construct supports count(), sum(), average(), min(), max(), toList(), toSet(), toMap(), etc. You can also plug in custom collectors.

For example, don’t assign more than 10 shifts to any employee by counting their shifts with count():

constraintFactory.forEach(Shift.class)
    // Group shifts by employee and count the number of shifts per employee ...
    .groupBy(shift -> shift.employee, count())
    // ... if more than 10 shifts for one employee ...
    .filter((employee, shiftCount) -> shiftCount > 10)
    // ... penalize as a hard constraint ...
    .penalize(HardSoftScore.ONE_HARD,
            // ... multiplied by the number of excessive shifts.
            (employee, shiftCount) -> shiftCount - 10)
    .asConstraint("Too many shifts");

Timefold has no linear limitations.

For example, avoid overtime and distribute it fairly by penalizing the number of excessive hours squared:

constraintFactory.forEach(Shift.class)
    // Group shifts by employee and sum the shift duration per employee ...
    .groupBy(shift -> shift.employee, sum(shift -> shift.getDurationInHours()))
    // ... if an employee is working more hours than his/her contract ...
    .filter((employee, hoursTotal) -> hoursTotal > employee.contract.maxHours)
    // ... penalize as a soft constraint of weight 1000 ...
    .penalize(HardSoftScore.ofSoft(1000),
            // ... multiplied by the number of excessive hours squared.
            (employee, hoursTotal) -> {
                    int excessiveHours = hoursTotal - employee.contract.maxHours;
                    return excessiveHours * excessiveHours;
            })
    .asConstraint("Too many shifts");

This penalizes outliers more. It automatically load balances overtime in fair manner across the employees, whenever possible.

Timefold also supports positive constraints: use reward() instead of penalize(). You can mix positive and negative constraints.

Scoring

OR-Tools CP

OR-Tools’s CP solver supports 2 score levels: hard constraints as constraints and soft constraints as an objective function that returns a floating point number.

OR-Tools Vehicle Routing

OR-Tools’s Vehicle Routing solver only supports the hard and soft constraints in the RoutingModel class.

Timefold

Timefold supports extra score levels beyond hard and soft constraints. For example, HardMediumSoftScore allows to prioritize medium operational constraints (such as assign all shifts) over soft financial constraints (such as reduce cost). Without resorting to multiplication with a big number.

Timefold supports to weight constraints dynamically per dataset without rebuilding the entire model. For example to make the soft constraint fairness in dataset A twice as important as in dataset B.

Timefold includes a Score Analysis API to break down a score per constraint.

Timefold does not suffer from numerical instability because it doesn’t rely on floating point arithmetic internally for constraint validation.

Cloud and Integration

Both OR-Tools and Timefold run on Linux, Mac and Windows. Both can run locally and in the cloud.

OR-Tools

Google Research offers a paid Operations Research API in the cloud based on OR-Tools.

Timefold

Timefold Solver has integration modules for Spring, Quarkus and JSON (de)serialization. It supports native compilation for serverless use cases that need to start up in milliseconds.

Timefold Enterprise offers a paid Field Service Routing API and Employee Scheduling API, that runs all major clouds (including Amazon AWS, Microsoft Azure and Google Cloud).

License, support and community

Both OR-Tools and Timefold Solver Community are open source software under the Apache License, which allows free usage in commercial software. In both cases, the code is open on GitHub.

OR-Tools

OR-Tools is developed by a small team at Google with help from the open source community.

To get started, go the OR-Tools website and follow the get started guide.

Timefold

Timefold is developed by Timefold BV with help from the open source community. Timefold BV is a company that lives and breathes planning optimization.

To get started, read the docs or clone the quickstarts repo on GitHub.

Timefold BV offers paid support and consulting through the Timefold Enterprise edition. This comparison covered only the features in the free, open source edition.