Route minimization procedures about euro-neurips-2022 HOT 15 CLOSED

@leonlan our initial solutions all start with one client per route now, right? Can you maybe take one of these instances with a small route diff, and plot the trajectory of # routes of the current best solution in each iteration?

It's coming down from nbClients to something close to the BKS's number, but not quite getting there in time. I'm just not sure if it's getting stuck (in which case we need to do something about it with, say, a fleet minimization procedure), or just needs more time to converge (in which case we should do ???).

Another question is how much the final number of routes actually depends on the number of routes in the initial random solutions. We have changed this a few times so far.

from euro-neurips-2022.

@leonlan our initial solutions all start with one client per route now, right? Can you maybe take one of these instances with a small route diff, and plot the trajectory of # routes of the current best solution in each iteration?

Are you OK if I built this in collectStatistics? Then I'll directly address the other TODO from #82.

Another question is how much the final number of routes actually depends on the number of routes in the initial random solutions. We have changed this a few times so far.

Yes, this is definitely an issue as well. Now that we use 1 route per client, we overestimate. But with main from 11 September 2c495c4 it goes both ways:

[('ORTEC-VRPTW-ASYM-4e5f1a3a-d1-n205-k17', 'Gap: 5.01', 'Route diff: -2'),
 ('ORTEC-VRPTW-ASYM-dd43a785-d1-n880-k50', 'Gap: 2.83', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-7f99f05a-d1-n528-k40', 'Gap: 2.27', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-844ea26c-d1-n231-k15', 'Gap: 2.27', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-fec88673-d1-n302-k25', 'Gap: 2.08', 'Route diff: -3'),
 ('ORTEC-VRPTW-ASYM-5d8fd227-d1-n211-k15', 'Gap: 2.07', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-13db18b2-d1-n310-k20', 'Gap: 1.84', 'Route diff: -3'),
 ('ORTEC-VRPTW-ASYM-ef1c4bb9-d1-n236-k20', 'Gap: 1.79', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-ce78488d-d1-n332-k30', 'Gap: 1.64', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-8bc1fa17-d1-n302-k23', 'Gap: 1.53', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-aa746fc7-d1-n478-k45', 'Gap: 1.51', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-37572525-d1-n240-k16', 'Gap: 1.42', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-3709cf41-d1-n287-k19', 'Gap: 1.40', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-c82ca041-d1-n393-k23', 'Gap: 1.35', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-d0d70aec-d1-n290-k18', 'Gap: 1.31', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-7ef1213a-d1-n292-k23', 'Gap: 1.30', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-898e14bd-d1-n230-k20', 'Gap: 1.29', 'Route diff: -2'),

from euro-neurips-2022.

Are you OK if I built this in collectStatistics?

Of course!

Yes, this is definitely an issue as well. Now that we use 1 route per client, we overestimate. But with main from 11 September 2c495c4 it goes both ways.

It's a bit early to speculate before we have more stats on this, but if it only comes down to a lack of time, we might just as well mix up the random generation of individuals a bit: instead of one client per route, maybe also do a few with two, three, etc.

from euro-neurips-2022.

@leonlan our initial solutions all start with one client per route now, right? Can you maybe take one of these instances with a small route diff, and plot the trajectory of # routes of the current best solution in each iteration?

It's coming down from nbClients to something close to the BKS's number, but not quite getting there in time. I'm just not sure if it's getting stuck (in which case we need to do something about it with, say, a fleet minimization procedure), or just needs more time to converge (in which case we should do ???).

I have the statistics for the following two instances:

• ORTEC-VRPTW-ASYM-844ea26c-d1-n231-k15.csv - bks cost: 69908, bks n_routes: 10
• ORTEC-VRPTW-ASYM-5d8fd227-d1-n211-k15.csv - bks cost: 84576, bks n_routes: 9

Both instances are solved with 1 route more and the 2%-ish gap as shown earlier. Based on these statistics, the solutions seem to be stuck on the number of routes. Surpisingly, the infeasible instances do sometimes get lower routes but this doesn't seem to get transferred to the feasible solutions.

from euro-neurips-2022.

I need to check if this is still an issue with after the recent merge #120.

from euro-neurips-2022.

Not as big of an issue as before, but the "bad" instances are still using more routes than the BKS. This is main from 6 october 4447443.

Not sure if's worth it to go into route-minimization procedures, or that we just solve it in other ways (e.g., better mutation/crossovers etc.). We have enough mechanisms in our algorithm to use less or more routes, so fortunately that's not the problem.

[('ORTEC-VRPTW-ASYM-62980c46-d1-n254-k20', 'Gap: 1.58', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-37572525-d1-n240-k16', 'Gap: 1.33', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-02182cf8-d1-n327-k20', 'Gap: 1.19', 'Route diff: 0'),
 ('ORTEC-VRPTW-ASYM-8bc13a3f-d1-n421-k40', 'Gap: 1.12', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-7ef1213a-d1-n292-k23', 'Gap: 1.07', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-c82ca041-d1-n393-k23', 'Gap: 1.05', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-d137e14b-d1-n257-k17', 'Gap: 1.02', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-dd43a785-d1-n880-k50', 'Gap: 0.95', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-844ea26c-d1-n231-k15', 'Gap: 0.89', 'Route diff: 0'),
 ('ORTEC-VRPTW-ASYM-4fe9435f-d1-n418-k28', 'Gap: 0.88', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-f346bd6e-d1-n353-k21', 'Gap: 0.86', 'Route diff: 0'),

from euro-neurips-2022.

@leonlan do you have a plot of a trajectory of # routes (y) over iters (x) for a single instance?

Edit: maybe average/min/max # routes per subpopulation?

from euro-neurips-2022.

@leonlan do you have a plot of a trajectory of # routes (y) over iters (x) for a single instance?

Edit: maybe average/min/max # routes per subpopulation?

I only have data for avg. per subpopulation. But I did manage to produce figures for the 3 worst performing instances for the main of 6 oct. All instances have >1% gap. The "avg routes" trajectories are each very different.

I added more figures for the 20 worst instances in the attached zip.
worst20-avg-routes.zip

from euro-neurips-2022.

Probably a bit extreme, but what if we just use a random-route removal operator with greedy reinsert as mutation step to reduce the fleet size? The greedy reinsert skips empty routes, so it will only insert new clients into existing routes.

from euro-neurips-2022.

Do we have anything planned to tackle this?

from euro-neurips-2022.

I'll try out a random-route-destroy and greedy insert. I don't think we'll have the time to try more advanced fleet minimization techniques.

from euro-neurips-2022.

I don't think I can finish this in time before tuning unfortunately. I've been too focused on the dynamic problem.

from euro-neurips-2022.

I just checked the statistics from main. Despite a big performance improvement due to #33, it's still very clear that bad runs use too many routes. On the qualification phase, these are the top 20 worst instances:

[('ORTEC-VRPTW-ASYM-8bc1fa17-d1-n302-k23', 'Gap: 1.81', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-d137e14b-d1-n257-k17', 'Gap: 1.38', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-7ef1213a-d1-n292-k23', 'Gap: 1.25', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-b3059fbe-d1-n325-k20', 'Gap: 1.21', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-4fe9435f-d1-n418-k28', 'Gap: 1.14', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-37572525-d1-n240-k16', 'Gap: 1.05', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-6aedfe61-d1-n308-k35', 'Gap: 0.93', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-dd59b788-d1-n252-k18', 'Gap: 0.92', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-62980c46-d1-n254-k20', 'Gap: 0.92', 'Route diff: 0'),
 ('ORTEC-VRPTW-ASYM-21e8376e-d1-n507-k30', 'Gap: 0.90', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-dd43a785-d1-n880-k50', 'Gap: 0.84', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-d0d70aec-d1-n290-k18', 'Gap: 0.79', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-8bc13a3f-d1-n421-k40', 'Gap: 0.76', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-c82ca041-d1-n393-k23', 'Gap: 0.71', 'Route diff: 0'),
 ('ORTEC-VRPTW-ASYM-f346bd6e-d1-n353-k21', 'Gap: 0.69', 'Route diff: 0'),
 ('ORTEC-VRPTW-ASYM-7f99f05a-d1-n528-k40', 'Gap: 0.64', 'Route diff: 0'),
 ('ORTEC-VRPTW-ASYM-41880837-d1-n262-k20', 'Gap: 0.59', 'Route diff: 0'),
 ('ORTEC-VRPTW-ASYM-ce78488d-d1-n332-k30', 'Gap: 0.57', 'Route diff: 0'),
 ('ORTEC-VRPTW-ASYM-d9af647d-d1-n237-k16', 'Gap: 0.57', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-53ac3334-d1-n285-k21', 'Gap: 0.56', 'Route diff: 0')]

For future research, it may be interesting to look into route minimization procedures. A simple idea is to add penalty coefficients for the number of routes (suggested by @N-Wouda).

from euro-neurips-2022.

One final comment on this: the team placed second in DIMACS VRPTW track uses a route minimization procedure outlined here.

from euro-neurips-2022.

I'll close this issue since it's not relevant right now. The future tag should help us find this issue back later if we want to work on it.

from euro-neurips-2022.