Understanding conflicting objectives

[do-me]

We started testing VRP with different objectives and were wondering about the following.

Let's assume these 3 objectives:

objectives: [
[
  {
    type: "minimize-unassigned"
  }
],
[
  {
    type: "minimize-distance"
  }
],
[
  {
    type: "minimize-duration"
  }
]
]

How does the algorithm work exactly in "balancing" these prioritized objectives?
Some extreme examples to make my point clearer:

Example:

• there is a solution where the distance increased by only 0.1% but duration decreased by 10%. Would this be an actual result of VRP or is it unacceptable that distance increased at all?
• if this would be an actual result, where is the threshold between these objectives with different priorities? The example above traded e.g. 0.1% loss for 10% gain but could it also be 1% loss for 5% gain?

I understand that we can use the threshold parameter if two objectives are equally important (in same array), but I lack the proper imagination of how the algorithm "thinks". Maybe you can help me out?

P.S. our first results with VRP look promising (depending on the objectives more or less on par or better than our existing solution) even though it's slower (we might tweak the termination criteria however, not a final conclusion). I'd like to share some more results/comparisons with you but cannot disclose some details publicly. If you have a preferred way of private communication please let me know.

[reinterpretcat]

The definition of objectives above is pretty strict: they are processed in hierarchy. So, if minimize-unassigned is better by any value, then comparison is done and solution with less unassigned jobs is considered better. If the values are equal, it goes to the next level and compare solutions using values from minimize-distance objectives. The next objective(s) is ignored until values of higher objective are equal.

You may notice, that objectives property is array of arrays. So, you can specify multiple objectives on the same level and they will be interpreted equally important. This leads that multiple solutions can be considered as equal (e.g. Pareto front) and then the solver has to decide how to sort them. Internally, I'm using NSGA-II algorithm for that. However, this approach introduces a few challenges:

• it might be hard to optimize Pareto front
• from user prospective, sometimes it might be desirable to sacrifice value of one of equal objectives to bring major improvement for another objective value. A good example, distance/duration balanced objectives: you're probably not seeking for perfectly balanced tours if the cost is raised significantly.

When I designed this, I had mostly balancing objectives in mind, so they have an extra options to specify how much their quality could be sacrificed to improve quality of other objectives (I think it is mostly for cost-related objectives, such as minimize-cost, minimize-distance and minimize-duration)

Here some useful docs:
https://reinterpretcat.github.io/vrp/concepts/pragmatic/problem/objectives.html#hints
https://reinterpretcat.github.io/vrp/examples/pragmatic/objectives/index.html

You can reach me privately ilya.builuk at gmail com

[do-me]

This answer is very useful thank you very much!

Do you have any experience or examples for effectively using the threshold or is this an empirical value that depends on each tour?

I modified the example from the docs:

        "type": "minimize-distance"
      },
      {
        "type": "minimize-duration",
        "options": {
          "threshold": 0.01

In this example, would 0.01 mean 1% of variance according to NSGA-II algorithm for minimize-duration allowed? Does this translate to "duration can be up to 1% more or less than the average to distance"? It's a little tricky to imagine what kind of impact it has on the optimization.

Would you rather recommend trying different settings and find out empirically?

[reinterpretcat]

Yes, that is mostly empirical value.

At the moment, minimize-duration objective has no options yet: I was experimenting with such options only for balance objectives. So defining it won't take any effect so far:

https://github.com/reinterpretcat/vrp/blob/master/vrp-pragmatic/src/format/problem/model.rs#L542

options.threshold is compared with the value of coefficient of variation used internally as a balance quality measure. The solver compares two solutions and if their objective values are below that threshold, then they are considered equal by that objective:

https://github.com/reinterpretcat/vrp/blob/master/vrp-core/src/construction/features/work_balance.rs#L138-L140

I can add such options, but I would need to understand a bit what would be the best approach to handle non-balancing objectives then.

[do-me]

Ok so it's quite hard to predict what kind of impact threshold might have on the optimization.
We'll look into it and test different settings in the next weeks. Thanks!