I haven’t tried Timefold but did try a ton of solvers (local and web) a few years ago when trying to optimize MRP schedule. One of the hardest parts was converting my business logic into constraints, especially date based calculations.
Instead of explicit constraints, is there a way to provide a calculation that can be minmaxed? If every order has a due date, can I say +/- 3 days = 0, 7 early = 9999 (not allowed), 7+ days late = (days late)^2?
Please email me (in profile) if you want to discuss.
You need piecewise linear cost function and auxiliary variables. An experienced practitioner should be able to help you with either mixed integer linear programming or constraint programming
No need when using the timefold solver, the constraint streams allow for a more "human readable" approach.
e.g. Penalise when the minimum is not reached, Penalise when the maximum is exceeded (2 constraints).
Somewhat related, I looked at a bunch of solvers for vehicle routing with time windows. One thing that surprised me was that the SaaS-based distance matrix calculations were prohibitively expensive. Google charged $0.01 per matrix element.
How do folks normally get the distance matrix? I ended up just using the Mapbox Optimization API instead of using a solver.
It is always a question of accuracy / convenience. You can start with straight / geodesic distance. One step up is to use open street maps with an offline open source router [1]. But if you want the accurate driving distance with the latest closures / traffic data the big vendors are the only choice.
Take a look at OSRM. For the Timefold Field Service Routing REST APIs, we have a maps service that runs OSRM under hood by default, but supports alternative map providers too. It calculates both travel time and distance matrixes.
Our maps service does do a bunch of additional optimizations (caching, incremental requests, ...) to assist any solver model we run that request maps information.
I've had to solve this in a number of ways. The fastest I've found is to precompute a hash map at a low-granularity (well, update on batch cycle regularly). Graphhopper with OSRM + OpenStreetMap data are useful in this domain, to the point where relatively dense polygons can be mapped on 16 CPU hours in a 100km by 100km block.
The GraphHopper Matrix API has an (IMO) attractive pricing especially for large matrices. The pricing is credit based and for large matrices we do not charge for every matrix cell but instead we only charge "locations*10". E.g. for a 200x200 matrix we only charge 2000 and not 40 000 credits as our underlying algorithm is very efficient (scales nearly linear). And let's say you need this calculation 25 times a day (using the premium package) then this leads to $0.016 for 1000 matrix elements. Of course even cheaper for larger matrices.
And larger packages will furthermore include a volume discount.
I didn't use Timefold but the predecessor Optaplanner, and I remember there were hard constraints which must always be true (eg one room can only be used for one meeting at a given time) and then there were soft constraints which were minimized (eg shorter distance is better)
so an optimization problem can then be described with a set of those hard/soft contraints
Yes!
These days, to handle cases with more work than resources to do it, medium constraints are used a lot too (so hard/medium/soft constaints), to penalize the amount of unassigned work. Those are harder than soft constraints, but softer than hard constraints.
Cool to see Hawkeye 360 is one of their users. Hawkeye is an Earth observation company that builds satellites to monitor RF spectrum usage on the ground, so I can see how better tasking would help.
It is a tough niche market where you compete with excel people who have built their careers on their manual planning expertise.
Unfortunately you are pitching not to the end user but to their manager (who will have to force them to drop their spreadsheet mambo jumbo). But I guess this is the case with all AI products nowadays anyways.
Whats the name of the algorithm/concept used here? I used simulated annealing, old fashioned algorithm for a college timetable prototype and I'm wondering how this company is using an AI model.
It is a constrained solver. You can argue about what is or is not AI. It varies over time, traditionally driven by in which part of the AI boom/ bust cycle we were, and lately also by which regulations would apply.
My background is in AI but I would have been hesitant calling the rule based systems I wrote to automate financial descisions AI at the time.
I have prototyped using timefold in a work project for hospital bed allocation.
Using the shortcut of "It's AI, but it won't hallucinate because it follows all of your policy and rules" has been a great way to onboard both non technical folks and operators warming up to the idea.
<Looks up Geoffrey> I used Drools Planner in 2012, which is a predecessor of Timefold. There was no talk of distilled "models" back then, but this article mentions models as if its a secret sauce.
I did something like this for a project in a class almost two decades ago. The project was to make a system that would take a bunch of students' schedules and produce a list of teams that optimized for shared free time. I started with simulated annealing and then ended up with a genetic algorithm.
We support Simulated Annealing too, as well as Tabu Search and many others. By default Timefold Solver uses Late Acceptance, which behaves like Simulated Annealing but isn't parameter tuning fickle like SA.
Do note that the base algorithm (such as SA, TS or LA) is less than 5% of the work to get great results. We do a lot of additional things on top of that (incremental score calculation, smart neighborhood selection, multi threaded solving and many more).
Hey Geoffrey, I missed that you were behind this! You did help me choose Drools Planner with simulated annealing in 2012. Congrats on coming a long way since then!
The lesson in this to young people: you can either sell your time by the hour, or buy other's time and use that productively. The former is very finite, the latter scales.
Why, if I didn’t know better, I’d imagine the gp might have been thinking about noted political theorist and agitator Karl Marx, writing briefly in Wage Labor and Capital (1847) [0] or later in his heftier Das Kapital (1867-1894) [1].
Offered without comment, except that better ebook examples are surely available somewhere:
Hmmm... Some co-founders and I are building a UK startup that needs to do skills-based task routing and optimize job assignment for workers who will drive to remote jobs.
Would love to have a quick chat with you or someone at timefold.ai to see if this is something we could potentially use.
A lot of the research on constraint solvers is to solve that problem. CSP is more approachable than boolean SAT or SMT but it's all the same sort of thing - feed it a lot of constraints and some notion of when a solution is better than another one and then leave it running for a while.
When you make the leap, you're basically living of off your savings.
Until the startup has investors that agree to pay the founders a wage (to reduce personal financial stress so they can concentrate on the company) - or the startup is profitable - it's vital that your savings don't run out...
Are there investors who wouldn't agree to pay the founders a wage?
I understand the part where you invest your time and money to build the PoC but I can't imagine running a startup with VC-backed investment without paying out myself a wage. That seems crazy to me if true.
Sounds like a nightmare and a good way to go into personal bankruptcy. Unless, I guess, you had a job where you accumulated ~M of savings, which is very very few people.
> Sure, but in some cases it's also a great way to become very very wealthy.
In very very very few cases, sure. Also, the wealth isn't the only or at least not the biggest motivator for many people trying to build their startups. But I get it - my money my rules disguised under show me how motivated you are to carry this through.
Sure, agreed though a larger percentage of VC funded startups exit than you probably think. Those "90% fail" stats are made up mostly by people who got traditional angel investment or no investment at all.
I'm just saying there's two sides to the coin, that's all.
I think there's a very genuine element of 'show me how motivated you are' you also cannot expect to get a normal standard rate company salary when you own most of the equity and aren't profitable. I think it's reasonable on balance.
No, that's only about the leverage - a perfect instrument to create even more pressure. Everything else I call a BS, sorry. Aren't founders already taking a huge leap by admitting themselves to work probably as much as ~10x more, with of course reciprocal amount of stress, and then you say it's reasonable that founders wouldn't be motivated enough unless they did all of that but for under the market rate? They left their job, they have the idea, they have the people, they have the drive ... and they want to execute it. I just hope not all investments work this way - this would be really sad.
Pretty much all investments work this way. I'm not saying they are on the poverty line - let's say in the UK, standard rate for a great full time programmer or average tech lead is 100k, as a co-founder you'd be earning say 50k (pre profit). You can pay your bills, even go on vacation but yes, not market rate.
I appreciate the details, I am not familiar with this at all. This is pretty shitty considering that as a contractor you would need to work ~3.5 months to earn 50k for much much less work and stress.
That makes me wonder what is the profile of a startup founder who agrees to an infinitely larger amount of complexity and stress for ~4x less income? The ones that got lucky so they don't care or don't have much loose or what. Crazy.
Equity is compensation, just illiquid, risky compensation. If you're wanting to get a wage (liquid, low-risk compensation) as well, expect to trade it against equity (which will naturally happen: if you're a founder being paid a wage, you're being paid it with the VC money which you have gotten by giving them some of your equity for some small fraction of what you expect the equity to be worth if you succeed). If you believe in the company (or at least rate the chances of success as more than the VCs do), it's rational to minimise the amount you trade away in equity for short-term needs or risk-reduction.
Geoffrey, thanks for sharing your story with us. OR sure is a weird niche. Good enough algorithms for solving these problems have existed for decades1, but we still see low adoption and your 95% estimate of the companies not optimizing their operations rings true.
Similarly to you, I spent a short while trying to sell VRP optimization with an API business model, and what dawned on me was that most companies do not have the necessary in-house expertise to integrate optimization into their existing tools even if the API is well-designed. There also really seems not to be any urgency to do that and most logistics companies just offload their inefficiencies onto their customers. Your routes are not effective? No problem, just bill more.
Some years ago I heard about a Swedish team of optimization experts who got so fed up with selling optimization to unwilling transportation companies that they founded their own—just to mop the floor with their ineffective competition. :D
I agree that ease of use is key here. In my PhD dissertation, I tried to address the issue by adding self-adaptivity within transportation management systems, mostly through automatic parameter tuning and algorithm selection. Such approaches remove some amount of fiddling when the optimization tool is adapted to a new optimization problem. Worth a look, perhaps, if you're interested.
Many thanks again for the interesting article and all the best with Timefold.
1) E.g., already by the '90s, we had quite capable algorithms for the VRP. I have open-sourced a library of classical VRP algorithms called VeRyPy, containing simple and not-so-simple heuristic algorithms. It has enjoyed modest success among VRP researchers and practitioners. Nowhere near the success of OptaPlanner, but also, the purpose is different—OptaPlanner is production-ready, whereas VeRyPy is more geared towards education and research purposes.
If nobody does something in a whole industry perhaps it's because it's not a differentiating factor. Do you have a link to the Swedish company? It just sounds like typical "software engineers know better" story where they go bankrupt after a few years because turns out the important bits are in other parts of the business.
A recent example of "knowing better optimisation experts" I know of in my local area are with garbage trucks. A expensive company was hired to optimize - yet they apparently forgot some real world factors, like with snow and ice not all the trucks can go everywhere, some roads too narrow, etc. with the result of chaos and the workers fighting succesfully to be allowed to continue influence their working schedule, they sucesfully managed without the external experts.
People do inefficient things. And they also do it for years, thinking it is a universal law. But usually an expert from the outside will still not know better how to do things.
Yes, this story is far too soothing to the software engineering ego to be actually true! Generally real world problems are messy, hard, and full of human problems. It's a little aggravating when 'software engineers know everything' stories like this are taken at face value and reinforce that mistaken idea.
True stories like this happen, but generally only when a domain expert on the business side was incorporated from the beginning—and that may not be mentioned by the software side.
Without involving the human planners, the project won't succeed. We're empowering them, with PlanningAI assistance, so they can focus on what they planning must do, for who, instead of how it gets there. So when the plan goes off the rails - 5 people call in sick - they can get it back on the rails in seconds with Real-Time Planning.
The engineering work is only half the work, or less. Fitting the technology into the human processes is another big chunk. Half of my videos on youtube deal with such cases: Continuous Planning, Real-Time Planning, Non-distruptive Replanning, Pinning, ... Not code, not technology, but design patterns.
And even then, this is far from 100% of the solution. Technology and education is still not enough.
That human planner with 30 years of business knowledge in his/her head is still a critical: he/she will always need to tweak, oversee and sometimes overrule the planning solution in production.
However I can tell you that this kind of thing really does happen. One of the injection molding conferences I attended had several presentations where companies were contemplating building more injection molding lines, but instead hired consultants (of course rolls eyes) to re-optimize their injection mold programs. After tweaking all the parameters in to speed up injection rates, it turned out the company had about 50% more capacity than they thought.
Now, I suspect this was shit management more than anything. I strongly suspect that the people on the line told their superiors that they needed to fix the programs and got ignored.
However, you couldn't sell anything to the management chain until they were staring at having to spend cash. Selling people on "saving money" is always super difficult as it requires them to change something that is nominally "working". Selling people on "not having to spend money they are staring at imminently" is always way easier. Obviously the easiest sell is "spend money to make a lot more money", but that doesn't happen all that often.
Sorry to dissapoint you and the few other curious ones, this was some 10 years ago and such details such as name of the company have fell of from my overfilled brain long ago. While the person who told me the story is a reputable fellow I must admit they still are a secondhand source. Being a finn I tend to trust people and take their word on it and, hence, do not recall doing my research to factcheck.
Still, it _is_ a good story, and plausible based on what I saw to be the state of the industry back then. Your run of the mill last-mile courier services were really badly organized, from the mathematics and optimization side as simple as they get, and ability to build a robust optimization transportation management system would've given serious competitive edge.
Yes, having in-house expertise to integration optimization into their existing tools is hard. Especially if they use low level solver APIs (especially if it's math equations).
We're working making that easier with high-level REST APIs (Timefold Field Service Routing, etc). And with education (Timefold Academy) by creating videos and articles on how to integrate real-time planning, continuous planning, labor law constraints, fairness, cost reduction, etc
Symbolic math equations isn't a low level solver API. That's the high level interface. A low level interface expects you to provide the optimization problems as raw matrices.
What you're talking about is known as a problem reduction.
I would argue that inputting a loadBalance(sum(shift.duration)) function per employee is a higher level abstraction than inputting a quadratic math equation to accomplish the same thing.
Think Java/C++/Python vs Assembly.
Ironically, talking about problem reduction... most math equation based solver can't scale quadratic equations, so users "relax" the business constraints (to the point that projects fail in production).
I did OR in my Bachelor thesis, and then at my first project at my first job. It worked like magic, and business was sure it wouldn't work. Still one of the projects I always talk about. It was for organizing screens unto pallets unto trucks. Then I never anything with OR ever since. Even for a few early AI products 8 years ago, in the end they didn't go for it. I think you are spot on with the expertise. Even though quite a lot of businesspeople heard about it in university.
I always assumed it was due to (a lack of) scale for most companies? 1% improvement in container planning for Maersk is hundreds of millions of dollars per year, so they can have an entire team dedicated to that. Meanwhile at the other end of the scale, 1% improvement of job scheduling at $DAYJOB probably wouldn't even pay for its own ongoing costs, let alone the costs of setting it up.
A 10% productivity gain is a lot for any company, regardless if they are operating a fleet of 50 or 50 000 vehicles.
However, the cost and risk to achieve that productivity gain is typically huge. Many Operations Research projects fail. And when they do, they are very expensive failures. "Managers getting fired" expensive.
With our technology, we're making OR projects easy and quick to put into production.
I love that GOFAI companies are also calling themselves AI, because seriously why not. If a pile of linear algebra (fittingly trained on The Pile) can be AI, then so can optimizers and solvers.
What a great story and indeed you're an excellent storyteller.
I want to wish you all the luck in the world with this, it sounds like it's going well.
Have you considered offering public pricing for your API, or maybe a few trial? Even if it's only for small use cases, I'd love to know I can just give you guys $100/month to cover my small use case.
I read the entire article once I recognized the name.
Geoffrey is synonymous with OR/Constraints solvers in my mind. I once had to tackle an issue in this domain and wound up using OptaPlanner after weeks of research.
It had the most intuitive API and the best community support by far.
It's a bummer to hear that OptaPlanner was killed, but it sounds like ultimately it led to something greater, so there's a silver lining.
Wishing you the best in your future endeavors, Geoffrey!
I remember you talking about the project in the early drools IRC days. Your positivity and enthusiasm were what really made this project happen, and I have no doubts about your success with this new venture.
I’m glad things went well for you and that you managed to regain control of your life’s work.
111 comments
[ 2.6 ms ] story [ 174 ms ] threadWe also have an overview of our open source solver here: https://timefold.ai/open-source-solver
Instead of explicit constraints, is there a way to provide a calculation that can be minmaxed? If every order has a due date, can I say +/- 3 days = 0, 7 early = 9999 (not allowed), 7+ days late = (days late)^2?
Please email me (in profile) if you want to discuss.
How do folks normally get the distance matrix? I ended up just using the Mapbox Optimization API instead of using a solver.
[1] https://wiki.openstreetmap.org/wiki/Routing/offline_routers
Our maps service does do a bunch of additional optimizations (caching, incremental requests, ...) to assist any solver model we run that request maps information.
And larger packages will furthermore include a volume discount.
Disclaimer: I'm one of the founders.
so an optimization problem can then be described with a set of those hard/soft contraints
Reminds me of NextMv [1] loved their episode on SWE daily. Can anyone compare them to this and how they’re doing?
[1]: https://www.nextmv.io/
It is a tough niche market where you compete with excel people who have built their careers on their manual planning expertise.
Unfortunately you are pitching not to the end user but to their manager (who will have to force them to drop their spreadsheet mambo jumbo). But I guess this is the case with all AI products nowadays anyways.
My background is in AI but I would have been hesitant calling the rule based systems I wrote to automate financial descisions AI at the time.
In this case, Geoffrey also seemed hesitant in the past to refer to his system as AI (see https://www.optaplanner.org/blog/2017/09/07/DoesAIIncludeCon... ), but somtimes you just have to ride the wave that brings in the funding.
I also think AI ousting ML historically was uncalled for, and those that did should bow their heads in shame.
Using the shortcut of "It's AI, but it won't hallucinate because it follows all of your policy and rules" has been a great way to onboard both non technical folks and operators warming up to the idea.
Do note that the base algorithm (such as SA, TS or LA) is less than 5% of the work to get great results. We do a lot of additional things on top of that (incremental score calculation, smart neighborhood selection, multi threaded solving and many more).
https://stackoverflow.com/questions/8712955/which-drools-pro...
The lesson in this to young people: you can either sell your time by the hour, or buy other's time and use that productively. The former is very finite, the latter scales.
Offered without comment, except that better ebook examples are surely available somewhere:
[0] https://www.marxists.org/archive/marx/works/download/pdf/wag...
[1] https://archive.org/details/KarlMarxCapitalVolumeI-III/Karl%...
Would love to have a quick chat with you or someone at timefold.ai to see if this is something we could potentially use.
> Founders might get a wage to avoid personal financial stress
How do you make a living as a founder if you don't get a wage? Is that really a norm?
> but then also need skin in the game, typically by investing personally
And also this. Does it assume that you will invest your savings or what exactly?
Until the startup has investors that agree to pay the founders a wage (to reduce personal financial stress so they can concentrate on the company) - or the startup is profitable - it's vital that your savings don't run out...
I understand the part where you invest your time and money to build the PoC but I can't imagine running a startup with VC-backed investment without paying out myself a wage. That seems crazy to me if true.
If you've got an independently weathly founder then both parties typically prefer equity only.
Traditional seed investors may not agree anything beyond minimum wage. It depends though.
It entirely depends on your personality and circumstances, it's certainly not for everyone.
In very very very few cases, sure. Also, the wealth isn't the only or at least not the biggest motivator for many people trying to build their startups. But I get it - my money my rules disguised under show me how motivated you are to carry this through.
I'm just saying there's two sides to the coin, that's all.
I think there's a very genuine element of 'show me how motivated you are' you also cannot expect to get a normal standard rate company salary when you own most of the equity and aren't profitable. I think it's reasonable on balance.
That makes me wonder what is the profile of a startup founder who agrees to an infinitely larger amount of complexity and stress for ~4x less income? The ones that got lucky so they don't care or don't have much loose or what. Crazy.
The majority of successful founders are already wealthy. Those who aren't, have a pretty high chance of going personally bankrupt in the process
In markets where capital is more scarce, people may want to avoid giving up more equity.
Similarly to you, I spent a short while trying to sell VRP optimization with an API business model, and what dawned on me was that most companies do not have the necessary in-house expertise to integrate optimization into their existing tools even if the API is well-designed. There also really seems not to be any urgency to do that and most logistics companies just offload their inefficiencies onto their customers. Your routes are not effective? No problem, just bill more.
Some years ago I heard about a Swedish team of optimization experts who got so fed up with selling optimization to unwilling transportation companies that they founded their own—just to mop the floor with their ineffective competition. :D
I agree that ease of use is key here. In my PhD dissertation, I tried to address the issue by adding self-adaptivity within transportation management systems, mostly through automatic parameter tuning and algorithm selection. Such approaches remove some amount of fiddling when the optimization tool is adapted to a new optimization problem. Worth a look, perhaps, if you're interested.
Many thanks again for the interesting article and all the best with Timefold.
1) E.g., already by the '90s, we had quite capable algorithms for the VRP. I have open-sourced a library of classical VRP algorithms called VeRyPy, containing simple and not-so-simple heuristic algorithms. It has enjoyed modest success among VRP researchers and practitioners. Nowhere near the success of OptaPlanner, but also, the purpose is different—OptaPlanner is production-ready, whereas VeRyPy is more geared towards education and research purposes.
A recent example of "knowing better optimisation experts" I know of in my local area are with garbage trucks. A expensive company was hired to optimize - yet they apparently forgot some real world factors, like with snow and ice not all the trucks can go everywhere, some roads too narrow, etc. with the result of chaos and the workers fighting succesfully to be allowed to continue influence their working schedule, they sucesfully managed without the external experts.
People do inefficient things. And they also do it for years, thinking it is a universal law. But usually an expert from the outside will still not know better how to do things.
Without involving the human planners, the project won't succeed. We're empowering them, with PlanningAI assistance, so they can focus on what they planning must do, for who, instead of how it gets there. So when the plan goes off the rails - 5 people call in sick - they can get it back on the rails in seconds with Real-Time Planning.
The engineering work is only half the work, or less. Fitting the technology into the human processes is another big chunk. Half of my videos on youtube deal with such cases: Continuous Planning, Real-Time Planning, Non-distruptive Replanning, Pinning, ... Not code, not technology, but design patterns.
And even then, this is far from 100% of the solution. Technology and education is still not enough.
That human planner with 30 years of business knowledge in his/her head is still a critical: he/she will always need to tweak, oversee and sometimes overrule the planning solution in production.
However I can tell you that this kind of thing really does happen. One of the injection molding conferences I attended had several presentations where companies were contemplating building more injection molding lines, but instead hired consultants (of course rolls eyes) to re-optimize their injection mold programs. After tweaking all the parameters in to speed up injection rates, it turned out the company had about 50% more capacity than they thought.
Now, I suspect this was shit management more than anything. I strongly suspect that the people on the line told their superiors that they needed to fix the programs and got ignored.
However, you couldn't sell anything to the management chain until they were staring at having to spend cash. Selling people on "saving money" is always super difficult as it requires them to change something that is nominally "working". Selling people on "not having to spend money they are staring at imminently" is always way easier. Obviously the easiest sell is "spend money to make a lot more money", but that doesn't happen all that often.
https://www.kth.se/en/om/innovation/alumner/airmee-levererar...
https://www.airmee.com/en/
Still, it _is_ a good story, and plausible based on what I saw to be the state of the industry back then. Your run of the mill last-mile courier services were really badly organized, from the mathematics and optimization side as simple as they get, and ability to build a robust optimization transportation management system would've given serious competitive edge.
(edit: removed repeated words)
Edit: vasco was faster with their question haha
Yes, having in-house expertise to integration optimization into their existing tools is hard. Especially if they use low level solver APIs (especially if it's math equations).
We're working making that easier with high-level REST APIs (Timefold Field Service Routing, etc). And with education (Timefold Academy) by creating videos and articles on how to integrate real-time planning, continuous planning, labor law constraints, fairness, cost reduction, etc
See https://www.youtube.com/@timefold/videos
What you're talking about is known as a problem reduction.
Think Java/C++/Python vs Assembly.
Ironically, talking about problem reduction... most math equation based solver can't scale quadratic equations, so users "relax" the business constraints (to the point that projects fail in production).
However, the cost and risk to achieve that productivity gain is typically huge. Many Operations Research projects fail. And when they do, they are very expensive failures. "Managers getting fired" expensive.
With our technology, we're making OR projects easy and quick to put into production.
Really, it's hard to say it's not AI.
Glad to see an open source project gaining benefit from the AI hype train at least. :)
I want to wish you all the luck in the world with this, it sounds like it's going well.
Have you considered offering public pricing for your API, or maybe a few trial? Even if it's only for small use cases, I'd love to know I can just give you guys $100/month to cover my small use case.
Geoffrey is synonymous with OR/Constraints solvers in my mind. I once had to tackle an issue in this domain and wound up using OptaPlanner after weeks of research.
It had the most intuitive API and the best community support by far.
It's a bummer to hear that OptaPlanner was killed, but it sounds like ultimately it led to something greater, so there's a silver lining.
Wishing you the best in your future endeavors, Geoffrey!
I’m glad things went well for you and that you managed to regain control of your life’s work.
Also irrespective of the project itself, amazing wife!
Congrats on all this great progress! Please take care :-)