Dispatch simulation routes only if it contains must dispatch requests

[leonlan]

This PR changes the way that simulation routes are dispatched.

The proposed change dispatches a simulation route only if it contains a must dispatch request. This means that a simulation route that only contains non-must-dispatch requests (and no simulated requests) is not dispatched. Such routes can be postponed at no cost, hence we should not count it as dispatching action. Before this PR, it happened about 2% of the time that a route that could be postponed is still dispatched.

The assumptions behind this change are:

• each simulated instance always starts with the epoch instance
• a route with must dispatch requests can never contain simulated requests

Moreover, this PR now makes round trips as random initial solutions. This ensures that we always have feasible solutions if we use nbVeh = nbClients vehicles. I also removed feasibility checking when solving simulation instances.

[leonlan]

@N-Wouda I think it's also helpful if you take a look at this subtle change.

[leonlan]

I got an IndexError during benchmarking, which means that the assumption that

• a route with must dispatch requests can never contain simulated requests

doesn't hold. Need to look further into this. I think that the non-euclidean distances play a role here, because must dispatch requests are filtered based on round-trip routes, which are not per definition the fastest.

[jmhvandoorn]

Benchmarking (error) shows that the assumption

• a route with must dispatch requests can never contain simulated requests

doesn't hold. Need to look further into this.

Maybe start with verifying that the solution is feasible when this happens.

It's either that, or a bug in the new python code.

By definition of "must dispatch" (=departing in epoch t+1 is too late) and "simulated requests" having release times >= epoch t+1 this should not be possible for feasible solutions.

[leonlan]

Benchmarking (error) shows that the assumption

• a route with must dispatch requests can never contain simulated requests

doesn't hold. Need to look further into this.

Maybe start with verifying that the solution is feasible when this happens.

It's either that, or a bug in the new python code.

By definition of "must dispatch" (=departing in epoch t+1 is too late) and "simulated requests" having release times >= epoch t+1 this should not be possible for feasible solutions.

Good point, I'll revert the feasibility changes and benchmark again.

[leonlan]

Indeed, simulation solve returned infeasible solutions. That is very strange... why are we still getting an infeasible solution from the solver when the single-route solution should be feasible?

[jmhvandoorn]

Indeed, simulation solve returned infeasible solutions. That is very strange... why are we still getting an infeasible solution from the solver when the single-route solution should be feasible?

Not sure, but the solution you mean is either not in the population, or not regarded as "best". Because even when running the solver for 0 iterations, the best solution isn't feasible (and contains mostly routes of length 2)

[leonlan]

Not sure, but the solution you mean is either not in the population, or not regarded as "best". Because even when running the solver for 0 iterations, the best solution isn't feasible (and contains mostly routes of length 2)

Good that you point this out! I also saw 2-customer routes, and now that I have given it another thought, this is actually the issue. The initial solutions are not "round-trips", which can be explained because the Individual constructor adds +1 to this:

https://github.com/N-Wouda/Euro-NeurIPS-2022/blob/0889560b8204c99be3ce45d3931e9ab5de8ffc7a/hgs_vrptw/src/Individual.cpp#L160-L161

So each route consists of two customers. This line should be something like

auto const clientsPerRoute = std::max(params->nbClients / params->nbVehicles, 1);

I'll change this tomorrow.

[jmhvandoorn]

Just to be sure, we might want to double check that changing the initialization doesn't influence the performance.

[N-Wouda]

I'll have a look at this tomorrow!

[leonlan]

Good that you point this out! I also saw 2-customer routes, and now that I have given it another thought, this is actually the issue. The initial solutions are not "round-trips", which can be explained because the Individual constructor adds +1 to this:

This also explains why I often encountered many infeasibility issues when testing dynamic, even when setting nbVeh to the number of clients (see remark in #89). The new changes should make sure that the initial population are round trips.

[leonlan]

Benchmark is finished: dynamic performance is unchanged, static is slightly higher, but I suspect this is due to postprocessing.