Published in Blog
Optimize routing and scheduling in Python: a new open source solver Timefold
Automate and optimize your operations scheduling in Python with Timefold AI
In Python, data scientists have a rich, open source AI toolkit to handle any business challenge, except for planning and scheduling. How do you optimally route field service technicians, assign employees to shifts, or schedule maintenance jobs?
For large organizations, solver technologies can reduce operational costs by $100,000,000 and CO² emissions by 10 million kg. So why doesn’t every Data Scientist use optimization solvers?
It’s because solvers are notoriously hard to use. Even a simple Vehicle Routing Problem implementation involves dealing with mathematical equations. Most solvers are too complex to handle real-world complexity. That’s about to change.
We are excited to announce Timefold Solver for Python, the new open source solver for Python developers and data scientists. It’s easy to use, powerful, and fast.
Solve a planning problem by calling solve():
solution = solver.solve(problem)Timefold is built for real-world complexity, such as Field Service Routing, Maintenance Scheduling, Employee Scheduling, Last Mile Delivery, and Task Assignment. It’s not optimized for a simple Traveling Salesman Problem. It scales to large datasets with business constraints for tens of thousands of employees, and more.
Timefold Solver for Python is free to use (open source under the Apache License), documented, thoroughly tested, and released on PyPi. It’s backed by our open core company that lives and breathes planning optimization.
Just pip install timefold and run one of the quickstarts:
Hello world |
Employee Scheduling |
|
|
Vehicle Routing Problem |
School Timetabling |
|
|
Each quickstart comes with a fully functional REST API, unit tests, and web UI.
Easy to use
Timefold puts developer productivity front and center. In Timefold, you define your model as domain classes and your constraints as code.
No need for mathematical equations. No need for a double array of binary variables. Timefold is the solver for Data Scientists and Software Engineers, not mathematicians. It integrates naturally with the rest of your Python software stack.
Let’s take a look at the source code for Employee Scheduling and Vehicle Routing:
Employee Scheduling
In Employee Scheduling, assign shifts to employees, while adhering to labor regulations and employee availability requests. It’s commonly used for healthcare personnel, security guards, police, or any employees that work in shifts.
Domain code
The Employee class has the name and skills of an employee:
class Employee:
name: str
skills: set[str]The Shift class contains the start and end of each shift,
as well as the required skill.
It also has an employee field, annotated with PlanningVariable.
That’s the field(s) that Timefold changes during solving.
Because it contains such an annotated field, the class has a @planning_entity decorator.
@planning_entity
class Shift:
start: datetime
end: datetime
required_skill: str
employee: Annotated[Employee | None, PlanningVariable]Employee and Shift are custom domain classes, so you can add attributes as needed, for your constraints, to fulfill your business requirements.
Constraints
Timefold assigns each shift to an employee, taking into account the constraints, such as:
-
Required skill: Every assigned employee must have the required skill. Add this as a hard constraint:
# For each shift ... (constraint_factory.for_each(Shift) # ... that is assigned an employee that doesn't have the required skill ... .filter(lambda shift: shift.required_skill not in shift.employee.skills) # ... penalize as an infeasible solution .penalize(HardSoftScore.ONE_HARD) .as_constraint("Missing required skill")) -
Ten hours between shifts: Ideally, an employee has 10 hours between two shifts. Add this as a soft constraint (AKA an objective):
# For each shift ...
(constraint_factory.for_each(Shift)
# ... combined with a later shift with the same employee ...
.join(Shift,
Joiners.equal(lambda shift: shift.employee.name),
Joiners.less_than_or_equal(lambda shift: shift.end, lambda shift: shift.start)
)
# ... with less than 10 hours in between ...
.filter(lambda first_shift, second_shift:
(second_shift.start - first_shift.end).total_seconds() // (60 * 60) < 10)
# ... penalize as a soft constraint weighted by the number of minutes less than 10 hours
.penalize(HardSoftScore.ofSoft(1), lambda first_shift, second_shift:
600 - ((second_shift.start - first_shift.end).total_seconds() // 60))
.as_constraint("At least 10 hours between 2 shifts"))-
Fairness: All employees are assigned the same amount of work.
-
and many more
Each constraint is unit tested. Run pytest on a quickstart to validate every constraint works as you intended:
def test_required_skill():
ann = Employee(name="Ann", skills={"Doctor"})
(constraint_verifier.verify_that(required_skill)
.given(ann,
Shift(start=..., end=..., required_skill="Nurse", employee=ann))
.penalizes(1))
beth = Employee(name="Beth", skills={"Nurse"})
(constraint_verifier.verify_that(required_skill)
.given(beth,
Shift(start=..., end=..., required_skill="Nurse", employee=beth))
.penalizes(0))Vehicle Routing
In the Vehicle Routing Problem, assign each visit to a vehicle and decide the order of the visits for each vehicle. The goal is to minimize driving time while adhering to capacity, time windows, overtime, and other constraints.
Domain
The Vehicle class has a list of visits, annotated with PlanningListVariable.
Timefold fills in the list of visits:
@planning_entity
class Vehicle:
name: str
home_location: Location
visits: Annotated[list[Visit], PlanningListVariable]
... # shift hours, capacity, skills, ...The Visit class has a name and location:
class Visit:
name: str
location: Location
... # time windows, weight/volume usage, skill requirements, ...Constraints
Constraints, such as the capacity constraint, are written in code:
def vehicle_capacity(factory: ConstraintFactory):
return (factory.for_each(Vehicle)
.filter(lambda vehicle: vehicle.calculate_total_demand() > vehicle.capacity)
.penalize(HardSoftScore.ONE_HARD,
lambda vehicle: vehicle.calculate_total_demand() - vehicle.capacity)
.as_constraint("Vehicle capacity"))This approach has the following benefits:
Powerful
Many solvers claim to be the fastest solver. But even the fastest solver is useless if it can’t implement all of your business requirements:
-
Hard constraints are physical or legal limitations. For example, an employee can’t be in two places at the same time.
-
Medium constraints assign as much work as possible, without breaking hard constraints. Ideally, all work is assignable, but on some days there is more work than people to do it.
-
Soft constraints (AKA objectives) reduce costs, increase service quality, and improve employee retention. For example, minimize traveling time or minimize overtime. These constraints are aggregated into a weighted function.
If a solution breaks a single hard constraint, the entire solution is useless. But also, every soft constraint that is missing constitutes a hidden cost to the company.
Therefore, Timefold can handle any constraint. Not just linear constraints. Not just quadratic constraints. Even constraints such as fairness and load balancing are fully supported.
Reliable, fast, and scalable
Timefold is built for complex business constraints and large datasets. It uses significantly less memory than traditional solvers, allowing it to scale beyond traditional limitations.
Because of many internal performance optimizations, it’s extremely fast. Even with custom code in your constraints. Under the hood, it uses a JVM to speed up performance.
To orchestrate high-scale datasets or maps integration, Timefold is developing a proprietary Enterprise extension.
Get Started
Timefold Solver for Python is ready to automate and optimize your operations scheduling challenges.
Get started with one of the quickstarts today:
$ git clone https://github.com/TimefoldAI/timefold-quickstarts.git
...
$ cd timefold-quickstarts/python/hello-world
...
$ pip install -e .
...
$ run-appIf you have questions, don’t hesitate to ask on StackOverflow. If you find an issue, report it in a GitHub issue.
Join the community
Join us in the community and start a GitHub discussion. To learn more about planning optimization, visit our website or follow us on Youtube.
