Redoute - Pruning Instances of E-VRP-NL Problems

April 08, 2022, 11:20 AM - 11:40 AM


Online Event

James Fitzpatrick, University College Dublin

Our solver focuses on pruning the search space associated with solving these problem instances by fixing a large fraction of the edge variables. The fixing of variables is achieved using a combination of rule-based approaches and machine learning classification models, which, in turn, are based on features derived from known heuristics, optimisation techniques and the statistical distribution of edge weights and distances of nodes from the depot and each other node. The process of reduce-and-route significantly limits the search space for a given problem so that it might be solved much more quickly than the original MILP instances, enabling us to find many new feasible solutions of the larger problem instances in the challenge and to obtain known optimal solutions for many smaller instances.

[Challenge Paper]   [Video]