Route minimization procedures

[leonlan]

Following #111, I tried to analyze for which instances we have a large gap w.r.t. the best known solution (BKS). Gap is defined as (cost - best_cost) / best_cost * 100. What I noticed is that for the solutions with large gap, this is often due to having 1 more route than in the best known.

Here is some data using the main branch from 30 September. The route difference is how many more routes the found solution uses than the BKS. A consistent pattern among solutions with large gap is 1 more route is used than what is used in the best known solution.

[('ORTEC-VRPTW-ASYM-844ea26c-d1-n231-k15', 'Gap: 2.23', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-5d8fd227-d1-n211-k15', 'Gap: 2.15', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-62980c46-d1-n254-k20', 'Gap: 1.40', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-b3059fbe-d1-n325-k20', 'Gap: 1.37', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-8bc1fa17-d1-n302-k23', 'Gap: 1.35', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-37572525-d1-n240-k16', 'Gap: 1.30', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-a1081c7b-d1-n325-k20', 'Gap: 1.27', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-d0d70aec-d1-n290-k18', 'Gap: 1.23', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-8bc13a3f-d1-n421-k40', 'Gap: 1.22', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-dd43a785-d1-n880-k50', 'Gap: 1.17', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-e814fc2f-d1-n247-k25', 'Gap: 1.10', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-d137e14b-d1-n257-k17', 'Gap: 1.09', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-7ef1213a-d1-n292-k23', 'Gap: 1.07', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-ce78488d-d1-n332-k30', 'Gap: 0.98', 'Route diff: 0'),
 ('ORTEC-VRPTW-ASYM-4fe9435f-d1-n418-k28', 'Gap: 0.95', 'Route diff: 1'),
 ('ORTEC-VRPTW-ASYM-a59d64ac-d1-n328-k20', 'Gap: 0.89', 'Route diff: 0'),
 ('ORTEC-VRPTW-ASYM-6aedfe61-d1-n308-k35', 'Gap: 0.87', 'Route diff: 1'),

It may be helpful to look into route minimization procedures. One possible direction is to use the one proposed in Christiaens and Vanden Berghe (2020).

[N-Wouda]

@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.

[leonlan]

@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'),

[N-Wouda]

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.

[leonlan]

@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.

[leonlan]

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

[leonlan]

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'),

[N-Wouda]

@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?

[leonlan]

@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.

Click here to show figures

  

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

[leonlan]

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.

[N-Wouda]

Do we have anything planned to tackle this?

[leonlan]

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.

[leonlan]

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

[leonlan]

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).

[leonlan]

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

[leonlan]

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.