Evaluate value and time-cost of preprocessing instances

[LuukPentinga]

Trivial improvements can be made to the instances before any routes are made. Example: direct edges are not always the shortest path between two nodes. Removal or penalization of such edges may help local search operators.

First evaluate whether reducing available edges in such a way even results in significantly better results. If so, determine if efficient implementation of this does not take up too much computational time. Should be highly parallel, consider CUDA programming due to availability of GPU.

Suggestions:

• All-pairs dijkstra
• Minimal arrival time feasibility

[N-Wouda]

Figuring out whether this makes sense to try (the first step) is fairly easy in Python with numpy/scipy and the like. That's probably well worth doing, and should not take too long to try!

[N-Wouda]

@LuukPentinga is this something that's still worthwhile to do? If not, should we close this issue?

[leonlan]

@LuukPentinga See Niels' comment :-) (I'm trying to clean up the issues a bit).

[LuukPentinga]

As the formatting of the problem assumes that a visit of a node equals the handling of a customer at that node, it appears we cannot really do anything with this. In most instances we could definitely create shorter paths than the direct edge between two nodes, but I don't see how we can use this anymore. This is more of a problem definition issue than a solution issue. Proprocessing the time windows generally was not worth it as changes to instances were extremely minor. Closing issue.