Neighbourhood sizes about euro-neurips-2022 HOT 15 CLOSED

@leonlan @MarjoleinAerts what do you think of this?

Marjolein, for context: the local search at the node/client level does basically this:

for each client U:
  for each client V that is near U:
    test node operators on clients U and V

The nbGranular parameter determines how many clients $V$ are near each client $U$.

from euro-neurips-2022.

Set different values for different instance sizes, as could happen when we start tuning in #33.
Set nbGranular to be a percentage of the number of clients, rather than an absolute value.

I think we can try both. We have to be slightly careful with setting nbGranular as percentage because the number of neighbors will then grow quadratically. In particular for the >500 instances, the difference between the number of neighbor pairs for 500 customer instances and 800 customer instances is quite big if we set them both to e.g. 20%.

from euro-neurips-2022.

Might indeed work to expeirment with this. With respect to setting nbGranular to a percentage of number of clients, it couldbe helpful to set a minimum absolute value and a maximum absolute value (especially a max absolute value to prevent a too large neighborhood exploration and high computation times). I think that also solves the issue raised by @leonlan.

from euro-neurips-2022.

I'm testing a run with nbGranular = 50 right now (so +10 from Vidal's default).

from euro-neurips-2022.

Increasing nbGranular to 50 (+25% from 40) reduces the number of iterations by about 25% as well. That makes perfect sense, of course. However, the solution quality also ever so slightly decreases from 164506 to 164546. I will try another run with nbGranular = 35 to see whether we just need more iterations, rather than larger neighbourhoods.

If so, we should probably implement the percentage + min/max bounds thing we discussed above.

from euro-neurips-2022.

With nbGranular = 35, the number of iterations goes up quite a bit, and solution quality barely changes (164521 now, baseline 164506). I'm now testing whether using these extra few thousand iterations for the route operators is worthwhile.

from euro-neurips-2022.

Setting nbGranular = 35, intensificationProbability = 15, and postProcessPathLength = 3, I get 41915 iterations (+10% from baseline), and an average cost of 164508 (right at baseline). So there's some sort of trade-off here, but it does not seem to matter a lot.

@leonlan do you know why performance now appears to be worse than on, say, 25/9 with commit 842866b?

from euro-neurips-2022.

@N-Wouda Sorry I didn't see the @. Is the question still relevant or is it resolved with #120?

from euro-neurips-2022.

@leonlan I think that resolved it!

from euro-neurips-2022.

I think there's a possibility that increasing the neighborhood will not help a lot, because the LS implementation of granular neighborhoods is not fully correct. I thought it was correct when merging #129 but I just had a second look at this:

For a correct working of granular neighboorhoods, we want to remove the isDepot check:

 if (applyNodeOps(U, p(V))) 
     continue; 

This caused errors related to merging TimeWindowSegments. I don't know in detail what happens there and was unable to resolve it.

from euro-neurips-2022.

This is what happens now:

We basically check U and V, and then also check whether inserting U after V's depot makes sense (if p(V) is the depot). @leonlan, how does that conflict with granular neighbourhoods?

from euro-neurips-2022.

The idea of granular neighborhoods is to restrict local search moves such that we only evaluate moves that correspond to promising arcs. In our proximity calculation for granular neighborhoods, we consider V to be a neighbor of U if either (U, V) is a promising arc or (V, U) is a promising arc.

Consider the neighbor V of U and perform applyNodeOps(U, V). We have 4 different local search operators:

• Relocate (N-0)
• Swap (N-M, M >= 1)
• MoveTwoClientsReversed
• TwoOpt

Relocate

For relocate, U is inserted after V. This means we go from the original to the proposed change:

Original:
p(U) -> U -> n(U)
p(V) -> V -> n(V)

Proposed:
p(U) -> n(U)
p(V) -> V -> U -> n(V)

All fine, since (V, U) is possibly a promising arc (but it could also be that only (U, V) is promising).

Swap

Now for swap, U is swapped with V. This leads to the change:

Original:
p(U) -> U -> n(U)
p(V) -> V -> n(V)

Proposed:
p(U) -> V -> n(U)
p(V) -> U  -> n(V)

This move did not lead to the creation of arcs (U,V) or (V, U), essentially being an arbitrary move that does not exploit any proximity-based information. The proposed fix is to apply the node ops to (U, p(V)), which does re-create the arc (U, V):

Original:
p(U) -> U -> n(U)
p(p(V)) -> p(V) -> V

Proposed:
p(U) -> p(V) -> n(U)
p(p(V)) -> U  -> V

MoveTwoClientsReversed

Similar reasoning can be applied to show that MoveTwoClientsReversed and TwoOpt don't consider moves that create the arcs that are desired by the granular neighborhoods.

For the current implementation of MoveTwoClientsReversed:

Original:
p(U) -> U -> X -> n(n(U))
p(V) -> V -> n(V)

Proposed:
p(U) -> n(n(U))
p(V) -> V -> X -> U -> n(V)

If we consider (U, p(V)) instead:

Original:
p(U) -> U -> X -> n(X)
p(p(V)) -> p(V) -> V

Proposed:
p(U) -> n(X)
p(p(V)) -> p(V) -> X -> U -> V -> n(V)

TwoOpt

For the current implementation of TwoOpt intra-route:

Original:
p(U) -> U -> ... -> V -> n(V)

Proposed:
p(U) -> V -> ... -> U -> n(U)

If we consider (U, p(V)) instead:

Original:
p(U) -> U -> ... -> p(V) -> V -> n(V)

Proposed:
p(U) -> p(V) -> ... -> U -> V -> n(V)

For TwoOpt inter-route, the current implementation does this:

Original:
p(U) -> U -> n(U) -> n(n(U))
p(V) -> V -> n(V) -> n(n(V))

Proposed:
p(U) -> U -> n(V) -> n(n(V))
p(V) -> V -> n(U) -> n(n(U))

And we can show that (U, p(V)) is the move we actually desire:

Original:
p(U) -> U -> n(U) -> n(n(U))
p(p(V)) -> p(V) -> V -> n(V)

Proposed:
p(U) -> U -> V -> n(V)
p(V) -> V -> n(U) -> n(n(U))

Conclusion

To summarize, for swap, MoveTwoClientsReversed and TwoOpt, we actually want to consider (U, p(V)) during LS search, because they recreate the edges that we want to have based on proximity/granular neighborhoods. Right now, we only consider the moves (U, V), which except for Relocate, do not create the edges that we desire. We only consider when (U, p(V) when V is the depot, but this is not enough.

from euro-neurips-2022.

Relocate

For relocate, U is inserted after V. This means we go from the original to the proposed change:

Original:
p(U) -> U -> n(U)
p(V) -> V -> n(V)

Proposed:
p(U) -> n(U)
p(V) -> V -> U -> n(V)

All fine, since (V, U) is possibly a promising arc (but it could also be that only (U, V) is promising).

If we instead compare (U, p(V)), we get:

Original:
p(U) -> U -> n(U)
p(p(V)) -> p(V) -> V

Proposed:
p(U) -> n(U)
p(p(V)) -> p(V) -> U -> V

Which is also OK for relocate. So, perhaps we should always check U and p(V), instead of V?

from euro-neurips-2022.

Yes that's also OK. Then we can also change the proximity calculation to only have V as neighbor of U when (U, V) is a good arc.

I tried changing to applyNodeOps(U, p(V)) some time ago, but with no success. Maybe you could have a look since you implemented it?

from euro-neurips-2022.

Maybe you could have a look since you implemented it?

For posterity: we tried this in #142, but it didn't seem to work much better than what we already had.

The nbGranular parameter has been tuned for each setting now, and it doesn't seem like different values for different instance sizes matters all that much. Because of that I'm closing this issue.

from euro-neurips-2022.