User defined hard / soft constraints

[dbhoot]

It'd be nice if we could implement our own user defined constraints (hard or soft). A hard constraint we often use is a vehicle not being allowed to perform more than x jobs or work longer than y hours.

A common soft constraint we use is the distance outside of a certain polygon.

[jcoupey]

All constraints we currently take into account are hard constraints. They're not used at all in the optimization objective, just for validity checks: a solution is either valid if all constraints are met or not considered at all for evaluation.

Adding arbitrary user-defined hard constraints would be far from trivial because the solving approach is tightly coupled with what constraints we handle. In some cases, checking for some new constraints might require extra work and dramatically increase the algorithmic complexity, thus the computing time.

The hard part about introducing soft constraints is that you then need to mess with the objective function by introducing a cost for soft constraint violations. Another point is that evaluating this additional cost may also incur a huge drawback for performance. For those two reasons, I suspect that adding soft constraints won't happen in the very near future.

Concerning the specific examples provided:

a vehicle not being allowed to perform more than x jobs

You can already handle that with capacity constraints, just set an amount component to be 1 for all jobs, then set the according capacity to the required limit per vehicle.

work longer than y hours

There is already quite some flexibility in the way you can restrict working hours using vehicle time windows. Do you have a use-case where this is not enough?

the distance outside of a certain polygon

I'm curious about that one, can you expand on the use-case and how this constraint makes sense from an operational perspective?

[dbhoot]

Adding arbitrary user-defined hard constraints would be far from trivial because the solving approach is tightly coupled with what constraints we handle. In some cases, checking for some new constraints might require extra work and dramatically increase the algorithmic complexity, thus the computing time.

Also aware of the challenges here. I kind of like how or-tools does this. If I remember correctly, you can add a constraint object to a general csat problem and then pass it off to a solver. I'm not familiar enough with the vroom codebase to know if a similar approach could work here. But it's def worth checking out. https://github.com/google/or-tools/blob/master/ortools/constraint_solver/constraint_solver.cc

The hard part about introducing soft constraints is that you then need to mess with the objective function by introducing a cost for soft constraint violations. Another point is that evaluating this additional cost may also incur a huge drawback for performance. For those two reasons, I suspect that adding soft constraints won't happen in the very near future.

Yup. There's potential to create a foot gun from a performance perspective. But it's also really powerful if done well.

Concerning the specific examples provided:

a vehicle not being allowed to perform more than x jobs

You can already handle that with capacity constraints, just set an amount component to be 1 for all jobs, then set the according capacity to the required limit per vehicle.

Yeah you can. The way I image this would work is to add an extra capacity / amount on top of the existing physical limitations.

work longer than y hours

There is already quite some flexibility in the way you can restrict working hours using vehicle time windows. Do you have a use-case where this is not enough?

My previous example wasn't great. However, something like 'the driver must take a 35 minute break every 4 hours of work` is hard to pull off with the current API. No? Even saying something like the the driver can work at most a 2 hours within a specified 6 hour range doesn't seem possible. I can give an interval in seconds or I can give an absolute time but is it possible to mix?

the distance outside of a certain polygon

I'm curious about that one, can you expand on the use-case and how this constraint makes sense from an operational perspective?

Sure. One example is where you have different union groups that compete for work in territories. Ideally, you prefer jobs within the territory you work/bind on. However, in the event the vehicles in that territory are overloaded, you would want to allow neighboring unions with excess capacity to fulfill the extra work. In general, it's a way to bias the cost to prefer certain situations over others.

[jcoupey]

you can add a constraint object to a general csat problem and then pass it off to a solver

Yes, we don't have this kind of easy way to add a constraint. The validity checks related to constraints are directly embedded within the heuristic and local search procedure. See e.g. the various is_valid implementations for local search operators in problems/cvrp/operators and problems/vrptw/operators.
The way we extend the features is by adding new constraints gradually and adjusting the solving process accordingly. This is why most feature tickets are about specific constraints.

'the driver must take a 35 minute break every 4 hours of work` is hard to pull off with the current API

That would be close to #186.

the driver can work at most a 2 hours within a specified 6 hour range doesn't seem possible

You're right it isn't.

it's a way to bias the cost to prefer certain situations over others

Thanks for the example details. The current take on this is that we prefer to use constraints to push some situations/solutions types rather than messing with the objective function. On your specific example, maybe you could achieve acceptable solutions by using skills to allow or restrict areas for different drivers. This is maybe not as flexible but depending on the problem setting you might get exactly the desired effect.

[showkeyjar]

please add amount component to the API document. the newest document just have capacity.

[jcoupey]

@showkeyjar if by "the newest document" you mean current master or the release/1.5 branch, then amount is mentioned all right. You can still use it for backward compatibility, but it is marked as deprecated and replaced by the delivery and pickup keys.

[showkeyjar]

@jcoupey ok, got it,thanks.

[ifle]

Ability to write custom constraints is very important and must be part of the library. For example we have customers requiremtns that no 2 different products can be transported in the same vehicle at the same time. This important if products require different temperatures, for example meat and vegetables & fruits.

[jcoupey]

Hi @ifle, thanks for your input, comments and use-case examples are highly valuable. But please refrain from stating what "must" be integrated in the project. There are several reasons for this:

1. What is badly needed in one use-case does not necessarily match the most common requirements, or what the project is designed for (see also 2 and 4).
2. As mentioned above, design choices for the solving approach come with pros and cons with regard to efficiency/speed and flexibility, I don't necessarily want to change this now.
3. I'm the main developer here and I'm not receiving any help (money or contributions) from most users while they're using the project "for free". This is totally fine from my point of view, but you must understand that for the benefit of everybody, we need a sustainable model for this to work. Hence the roadmap and priorities are set by the most common use-cases of my company's clients.
4. This is an open-source project, so people that want to experiment with new features that are important to them are welcome to submit patches and/or work on their own fork. In that case, I'll always be willing to discuss solving approaches and implementation options.

I'll flag this ticket as a feature request because that's what it is, but frankly I don't think this will be implemented in a generic way any time soon. If you badly need setting very specific custom constraints, you may be interested in looking up libraries that have a different solving approach and offer more flexibility, e.g. jsprit, or-tools or Optaplanner.

[ifle]

Sorry for "must". Really I'm very impressed from your works.
By my opinion - the core library can't coverage all use cases - then ability to extensibility is very important for each library. Sorry again

[jcoupey]

@ifle no problem, just wanted to make things clear regarding choices and roadmap.

Again, from the current approach and codebase, my view is that adding more flexibility in constraints description could only happen at the expense of much longer computing times. I don't really want to go this way now because getting "good solutions fast" is the motto. And also we have other important unimplemented features with higher priority.

[ifle]

Is there roadmap? I seen you worked on shipments

[jcoupey]

Is there roadmap?

Nothing formal, but the next milestone is usually set. This may be subject to changes but gives an overall idea of the mid-term prioritized features.

[jonathanelbaze]

Hi Julien !

On the subject of soft constraints, in my use case, I would like to allow vehicles to work overtime.
This means that each vehicle would have a soft time_window (normal working hours) and a soft time_window (maximum overtime possible).
When working overtime, a penalty cost would be added in order to minimize this kind of work. But sometimes overtime work will be very helpful (for example to avoid dispatching 2 vehicles to a remote location (5h round-trip) for only a few minutes of overtime for the vehicle already there)

Questions :

• Is there a way to currently apply this ?

• Will there be one soon ?

• In your opinion, is it possible to easily modify the objective function in the code to adapt it to this problem ?

• Where would that be ?

• Would the algorithm lose a lot of efficiency ?

Thank you very much for your work, it's incredibly useful !

[jcoupey]

No, there is no way currently to provide soft time window constraints. You could still have some kind of softening logic outside VROOM and compare results with various time window lengths in input, but then overtime penalties would not be taken into account during solving.

I see a few downsides on the overtime thing:

1. For validity checks, we store earliest/latest dates for all tasks in a route, and upon any modification we propagate those forward and backward to make sure they still match with constraints. There are probably situations where we currently stop with a guarantee that everything will be OK down the line, and where it would now be mandatory to keep going simply to compute the overtime penalty.
2. For any route change, we usually compute the potential travel time gain upfront. We store enough information to be able to make that in constant time (usually), so in most cases we discard moves without even having to check for validity. Now if gain has to include an overtime component, simply computing the gain becomes as expensive as checking validity with the process described above.
3. The very notion of penalty is not that easy to deal with: the somehow extreme example of only a few minutes overtime saving 5h of driving make it sound obvious but how to ponder overtime with other costs is not that clear, and it may be use-case dependent.

So all in all probably doable, probably quite expensive and tricky to tune.

[jcoupey]

Closing as arbitrary user-defined constraints is too broad. On the initial post:

vehicle not being allowed to perform more than x jobs

Ticketed in #421 and part of the next release.

or work longer than y hours.

See #273.