Hacker News Reader

Comment by chime | Hacker News Reader

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.

View on HN

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.

[1] https://wiki.openstreetmap.org/wiki/Routing/offline_routers

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.

Disclaimer: I'm one of the founders.

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

This feels like a basic service Timefold would offer...

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).

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.

Reply on news.ycombinator.com