Can VRPTW models take a negative cost matrix?

[onecable5781]

Hello,

I have an application where the cost matrix of a VRPTW can be negative while the transit times are nonnegative. The objective is to minimize the total cost of all routes subject to satisfying all other regular VRPTW constraints - each customer is visited exactly once within the time windows without letting the negative costs lead to otherwise infeasible routes.

A similar recent discussion #4019 seems to suggest to bump up all costs by a constant addition so that the minimum after bumping is 0

So, if my original cost matrix for a 2 customer problem is

 0  -1   -1
-1   0   -1
-1  -1    0   

my current understanding is that I should be modifying it to:

 1   0   0
 0   1   0
 0   0   1   

wherein I have added a +1 to each entry.

My question is about the diagonal 0s of the original cost matrix. Since the diagonal elements are self loops of type i -> i which are anyway disallowed in VRP solutions, should my original cost matrix be considered to be:

 M  -1   -1
-1   M   -1
-1  -1    M   

where M is some large positive number in which case, the modified cost matrix which I submit to OR Tools will be different? Or, is the underlying OR Tools solver clever enough to never worry about self loops of type i -> i and hence it does not matter what M is in the original cost matrix in which case, it might as well be 0.

Thank you.

[sschnug]

Again: Take it with a grain of salt (no or-tools dev)

While the more general question incorporating all cases sounds like trouble, in your case, it seems, using 1 or M doesn't influence correctness assuming " i -> i which are anyway disallowed in VRP solutions". Without that assumption, one has to look into it in more detail.

Correctness given, now looking at performance, i would highly expect the M variant at least as good (or better) as the 1 variant.

In general, as much as possible is done BEFORE asking the cp-solver (in the routing-solver) and while forbidden self-loops are a-priori fixed domains (no runtime-propagation needed), it's potentially less efficient to check than non-improving costs.

If you are interested in analyzing it, use

or-tools/ortools/constraint_solver/solver_parameters.proto

Line 71 in 5f7eabb

// Activate local search profiling.

This gives you something like:

Local search filter statistics:
                          |     Calls |   Rejects | Time (s) | Rejects/s
       SumObjectiveFilter |    134243 |    128982 | 1.5e+03  |      85
    DimensionFilter(Time) |      6067 |      5382 | 1.3e+02  |      43
    DimensionFilter(Time) |      3842 |      3677 |      48  |      77
DimensionFilter(Capacity) |      2206 |      1522 |      47  |      32
     VariableDomainFilter |      1179 |      1060 |      18  |      59
DimensionFilter(Capacity) |       578 |       417 |     6.7  |      62
     VariableDomainFilter |       381 |         0 |     6.1  |       0
    VehicleVariableFilter |       379 |         0 |     6.1  |       0
    PathCumulFilter(Time) |       376 |         0 |     6.1  |       0
      VehicleBreaksFilter |       376 |         0 |     6.1  |       0
    NodeDisjunctionFilter |       112 |         0 |    0.72  |       0
    VehicleVariableFilter |       110 |         0 |    0.71  |       0
    PathCumulFilter(Time) |       107 |         0 |     0.7  |       0
      VehicleBreaksFilter |       107 |         0 |    0.71  |       0
                    Total |    150063 |    141040 | 1.8e+03  |      79

Now i claim:

• SumObjectiveFilter can use bigM to reject early, less so with 1
• SumObjectiveFilter is faster than VariableDomainFilter

  • or-tools/ortools/constraint_solver/routing.cc

    Line 4660 in 5f7eabb

    // The SumObjectiveFilter has the best reject/second ratio in practice,

  • Which is probably the self-loop (but i'm guessing)

That being said. I did some presolve-experiments in the past converting forbidden-arcs (again VariableDomainFilter)` into bigMs and there was no improvement. So maybe this kind of optimization is too much, as long as correctness is given.

Greetings,

Sascha

[onecable5781]

Thank you.
Actually, regarding correctness, the idea of adding a constant to all entries will only work for a TSP with a single vehicle. With a VRP, it may not work.
I will have to rethink my strategy. It does appears that it may not be easy to incorporate negative costs in VRPTW of ortools.

Thank you for your detailed input -- it gives me a lot to delve into.

[jmarca]

One other thing to be aware of, the value at each node of each dimension must be zero or positive. If it is negative due to a negative link cost, it will get truncated *silently* to zero. At least, that was my experience a few years back. As I recall I was doing something like modeling the need for a break as something that decreased as a vehicle moved, so I had negative links for that "dimension" but nothing worked right because nothing went negative. I had to bump everything up by some hard floor, so that if it went below the positive floor, it was time for a break. But the negative link costs technically worked in my use case for a VRP. James

…

On Thu, Apr 11, 2024 at 08:07:05AM -0700, onecable5781 wrote: Thank you. Actually, regarding correctness, the idea of adding a constant to all entries will only work for a TSP with a single vehicle. With a VRP, it may not work. I will have to rethink my strategy. It does appears that it may not be easy to incorporate negative costs in VRPTW of ortools. Thank you for your detailed input -- it gives me a lot to delve into. -- Reply to this email directly or view it on GitHub: #4177 (reply in thread) You are receiving this because you are subscribed to this thread. Message ID: ***@***.***>

-- James E. Marca Activimetrics LLC