Complex scheduling
and routing optimization
made easy

The world is full
of scheduling problems

For example

The world is full
of scheduling problems

Some are automated

Few are optimized

Optimize them
with PlanningAI

Vehicle routing case study

Expected: -1% driving time

Result: -25% driving time

⇒ -10 million kg CO² emission per year

⇒ -100 million $ cost per year

Difficult to solve?

Calculate score

javapublic long calculateScore(TimeTable timeTable) {
    long hardScore = 0;
    for (Lesson lesson1 : timeTable.lessons) {
        for (Lesson lesson2 : timeTable.lessons) {
            if (lesson1.room == lesson2.room
                    && lesson1.timeslot == lesson2.timeslot) {
                hardScore--;
            }
            if (lesson1.teacher == lesson2.teacher
                    && lesson1.timeslot == lesson2.timeslot) {
                hardScore--;
            }
            if (lesson1.studentGroup == lesson2.studentGroup
                    && lesson1.timeslot == lesson2.timeslot) {
                hardScore--;
            }
        }
    }
    return hardScore;
}

Calculate score

pythondef calculate_score(time_table):
    hard_score = 0
    for lesson1 in time_table.lessons:
        for lesson2 in time_table.lessons:
            if (lesson1.room == lesson2.room
                and lesson1.timeslot == lesson2.timeslot):
                hard_score -= 1
            if (lesson1.teacher == lesson2.teacher
                and lesson1.timeslot == lesson2.timeslot):
                hard_score -= 1
            if (lesson1.student_group == lesson2.student_group
                and lesson1.timeslot == lesson2.timeslot):
                hard_score -= 1
    return hard_score

Greedy algorithm

Greedy code

javafor (Lesson lesson : timeTable.lessons) {
    long bestScore = Long.MIN_VALUE;
    Room bestRoom = null;
    Timeslot bestTimeslot = null;
    for (Timeslot timeslot : timeTable.timeslots) {
        lesson.setTimeslot(timeslot);
        for (Room room : timeTable.rooms) {
            lesson.setRoom(room);
            long score = calculateScore(timeTable);
            if (score > bestScore) {
                bestScore = score;
                bestRoom = room;
                bestTimeslot = timeslot;
            }
        }
    }
    lesson.setTimeslot(bestTimeslot);
    lesson.setRoom(bestRoom);
}

Greedy code

pythonfor lesson in time_table.lessons:
    best_score = float('-inf')
    best_room = None
    best_timeslot = None

    for timeslot in time_table.timeslots:
        lesson.timeslot = timeslot
        for room in time_table.rooms:
            lesson.room = room
            score = calculate_score(time_table)
            if score > best_score:
                best_score = score
                best_room = room
                best_timeslot = timeslot

    lesson.timeslot = best_timeslot
    lesson.room = best_room

DEMO

Greedy algorithm

Algorithm comparison

Brute force

Brute force code

javalong bestScore = Long.MIN_VALUE;
for (Timeslot timeslotLesson1 : timeslots) {
    lesson1.setTimeslot(timeslotLesson1);
    for (Room roomLesson1 : rooms) {
        lesson1.setRoom(roomLesson1);

        for (Timeslot timeslotLesson2 : timeslots) {
            lesson2.setTimeslot(timeslotLesson2);
            for (Room roomLesson2 : rooms) {
                lesson2.setRoom(roomLesson2);
                ...

                for (Timeslot timeslotLessonN : timeslots) {
                    lessonN.setTimeslot(timeslotLessonN);
                    for (Room roomLessonN : rooms) {
                        lessonN.setRoom(roomLessonN);
                        int score = calculateScore(timeTable);
                        if (score > bestScore)
                            ...

Brute force code

pythonbest_score = float('-inf')
for timeslot_lesson_1 in timeslots:
    lesson1.timeslot = timeslot_lesson_1
    for room_lesson_1 in rooms:
        lesson1.room = room_lesson_1

        for timeslot_lesson_2 in timeslots:
            lesson_2.timeslot = timeslot_lesson_2
            for room_lesson_2 in rooms:
                lesson_2.room = room_lesson_2
                ...

                for timeslot_lesson_n in timeslots:
                    lesson_n.timeslot = timeslot_lesson_n
                    for room_lesson_n in rooms:
                        lesson_n.room = room_lesson_n
                        score = calculate_score(time_table)
                        if score > best_score:
                            ...

DEMO

Brute Force

How big is the search space?

Search space for n lessons: nⁿ

Search space for 400 lessons: 10¹⁰⁴⁰

Atoms in observable universe: 10⁸⁰

Algorithm comparison

Metaheuristics

• Local Search
• Tabu Search
• Simulated Annealing
• Late Acceptance
• ...

+ advanced subsystem algorithms

Implement yourself?

Planning optimization made easy

• Library of optimization algorithms
• AI, not ML
• Open Source (Apache license)
• Actively developed by our Open Core company

Easy score calculator

javapublic HardSoftScore calculateScore(TimeTable timeTable) {
    long hardScore = 0;
    for (Lesson lesson1 : timeTable.lessons) {
        for (Lesson lesson2 : timeTable.lessons) {
            if (lesson1.room == lesson2.room
                    && lesson1.timeslot == lesson2.timeslot) {
                hardScore--;
            }
            if (lesson1.teacher == lesson2.teacher
                    && lesson1.timeslot == lesson2.timeslot) {
                hardScore--;
            }
            if (lesson1.studentGroup == lesson2.studentGroup
                    && lesson1.timeslot == lesson2.timeslot) {
                hardScore--;
            }
        }
    }
    return HardSoftScore.of(hardScore, 0);
}

Easy score calculator

pythondef calculate_score(time_table) -> HardSoftScore:
    hard_score = 0
    for lesson1 in time_table.lessons:
        for lesson2 in time_table.lessons:
            if (lesson1.room == lesson2.room
                and lesson1.timeslot == lesson2.timeslot):
                hard_score -= 1
            if (lesson1.teacher == lesson2.teacher
                and lesson1.timeslot == lesson2.timeslot):
                hard_score -= 1
            if (lesson1.student_group == lesson2.student_group
                and lesson1.timeslot == lesson2.timeslot):
                hard_score -= 1
    return HardSoftScore.of(hard_score, 0)

DEMO

Metaheuristics

Algorithm comparison

Vehicle Routing Problem (VRP)

DEMO

Field Service Routing

app.timefold.ai