Edge assembly crossover - Githubissues

N-Wouda / Euro-NeurIPS-2022

OptiML's contribution to the EURO meets NeurIPS 2022 vehicle routing competition.

Other

16 stars 2 forks source link

Edge assembly crossover #121

Closed LuukPentinga closed 2 years ago

LuukPentinga commented 2 years ago

Implementation of #46. Appears to work as is, but there are some improvements to be made:

[x] Add a block-based strategy. We now only consider single AB cycle strategies.
[ ] Improve the resolveSubtour function. Currently a subtour is resolved by adding a depot node where it minimizes distance. No time penalty considered so far. We may want to skip this altogether and look at 2-OPT*.
[x] See if we can output step 4 in vector format directly. I work with unordered (multi)maps for quick insertion/deletion/access via keys, but the routes are ultimately vector format.

leonlan commented 2 years ago

@LuukPentinga Do you already want this to be reviewed or should we wait for the other todos?

LuukPentinga commented 2 years ago

No need yet, I'll have another look at it first!

N-Wouda commented 2 years ago

@LuukPentinga can you merge main into this branch before pushing new commits? I've changed a few things to limit CI use :-)

N-Wouda commented 2 years ago

@LuukPentinga do you think you'll be able to finish this before ~Friday~ Saturday?

N-Wouda commented 2 years ago

@LuukPentinga do you have an update on this? I'm trying to figure out whether we can incorporate this in the tuning now (if it's nearly done/will be done in a day or so), or should do so after.

LuukPentinga commented 2 years ago

This should finally be a functioning operator. Subtours are merged by distance only, as otherwise we need to recalculate all time windows and we do a bunch of local search afterwards anyway.

The problem previously described in #46 is not really solved. We do a BFS to find a suitable cycle, starting from some random starting node. If no such cycle is found, we just abort the operator and return one of the parents. I suppose that not finding a cycle does not necessarily imply that no cycle exists, but it is at least not connected to the random starting node that we select.

N-Wouda commented 2 years ago

@LuukPentinga great, thanks! I'll have a look this afternoon.

N-Wouda commented 2 years ago

Could you run clang-format to fix the CI?

N-Wouda commented 2 years ago

I'll benchmark this on the cluster in a minute.

N-Wouda commented 2 years ago

This does not work yet (I get a corrupted doubly-linked list, so something goes wrong somewhere). I'll try to figure that out tomorrow.

@LuukPentinga can you add "edge_assembly" to configs/benchmark.toml, and try the benchmark script with 50 iters per instance yourself? That immediately fails for me.

LuukPentinga commented 2 years ago

@N-Wouda I'll have a look. I can reproduce it now so I'll see what I can figure out.

N-Wouda commented 2 years ago

That seems to have fixed it!

N-Wouda commented 2 years ago

I'm running a benchmark with this now (SREX + EAX).

N-Wouda commented 2 years ago

Benchmark results are in:

SREX: ~164300, 40-45K iterations
SREX + EAX: 165204, 74.7K iterations
EAX: 185733, 93.4K iterations

So EAX is really bad. I think (looking at the increased number of iterations) that's because the resulting offspring looks too much alike to the parent solutions.

N-Wouda commented 2 years ago

@LuukPentinga are you willing to test whether an approach with more/larger cycles works?

LuukPentinga commented 2 years ago

Yes, it should require a bit of a change to the cycle search but I think it will be okay. I'll have a go at it.

N-Wouda commented 2 years ago

@LuukPentinga are you still working on this?

N-Wouda commented 2 years ago

@LuukPentinga I want to make our final submission tomorrow. Do you think we can get this finished before late Sunday, or shall we proceed with just SREX?