These are all
planning problems

Tackling the problem

In our favorite programming language!

Greedy Algorithms

Greedy algorithms make locally optimal choices at each step, but do not consider effects on follow up steps.

Greedy code

                    var remaining = new ArrayList<>(allVisits); //copy
var visitOrder = new ArrayList<>();

Visit latest = remaining.getFirst();
visitOrder.add(latest);
remaining.remove(latest);

int remainingSize = remaining.size();
for (int i = 0; i < remainingSize-1; i++) {
    Visit closestVisit = findClosest(latest, remaining);
    visitOrder.add(closestVisit);
    remaining.remove(closestVisit);
    latest = closestVisit;
}
                    
                

Algorithm comparison

Let's try everything!
Brute Force 💪

How big is the search space?

Search space for n 🎁: n!

Search space for 5 🎁: 120

Search space for 10 🎁: 3628800

Search space for 100 🎁: 10¹⁵⁷

Search space for 1000 🎁: 10²⁵⁶⁷

Search space for 1000 🎁: 10²⁵⁶⁷

Atoms in the observable universe: 10⁸⁰

10^2567: 2487 more zeroes

Algorithm comparison

How good are humans?

Result comparison

Christmas Magic

or math.. probably math.

Mathematical Optimization

Group of techniques to find the ideal inputs from a set
in order to maximize or minimize a real function.

Planning optimization made easy

• Optimization problems in domain code
• Open Source (Apache license)
• JVM based!

Easy score calculator

public HardSoftLongScore calculateScore(VehicleRoutePlan plan) {
    long totalDrivingTime = 0;

    for(Vehicle v : plan.getVehicles()) {
        totalDrivingTime += v.getTotalDrivingTimeSeconds();
    }

    return HardSoftLongScore.of(0, totalDrivingTime*-1);
}

Metaheuristics

1. Make a fast initial solution
2. Exploring alternatives by moving things around

How many solutions per second?

log08:27:00.867  INFO Solving started: ...
08:27:02.528  INFO Construction Heuristic ended: ...
                       move evaluation speed (39580/sec) ...
08:27:21.313  INFO Local Search ended: ...
                       move evaluation speed (101701/sec) ...
08:27:21.317  INFO Solving ended: ...
                       move evaluation speed (101461/sec) ...

It looks at 100 000 solutions per second

Algorithm comparison

In reality

• Drivers can only visit locations when they are open
• Trucks have limited capacity
• Multiple trucks scheduled at the same time
• ...

Constraints

How do you define constraints?

Constraint minimizeTravelTime(ConstraintFactory factory) {
    return factory.forEach(Vehicle.class)
            .penalizeLong(HardSoftLongScore.ONE_SOFT,
                    Vehicle::getTotalDrivingTimeSeconds)
            .asConstraint("Minimize Travel Time");
}
                

More elaborate example

                
Constraint vehicleCapacity(ConstraintFactory factory) {
    return factory.forEach(Visit.class)
        .filter(visit -> visit.getVehicle() != null)
        .groupBy(Visit::getVehicle, sum(Visit::giftAmount))
        .filter((v, sum) -> sum > v.getCapacity())
        .penalizeLong(HardSoftLongScore.ONE_HARD,
                (v, sum) -> sum - v.getCapacity())
        .asConstraint("Vehicle Capacity");
}
                
                

Why use constraints?

• Read like business rules
• Explainable Score
• Incremental Score Calculation

Incremental Score Calculation

Adding one new package 🎁

🖊 Model domain

⚖️ Define constraints

🚀 Run!

Algorithm comparison

GenAI

Can't solve these kinds of problems

but can be used to write Timefold code.

Start coding today

1. Go to https://timefold.ai/open-source-solver
2. Click Run a Quickstart.
3. Pick a quickstart from the README.
4. Run it: 🚀

In Conclusion

Planning problems are about people.

Optimization helps you take care of them. 🎁

Give the 🎁 of optimization!

Learn more	solver.timefold.ai
Get started
Feedback	Add me on socials! 🙏 Tom Cools: (@tomcools.be)