An Adaptive Heuristic for Multi Commodity FixedCharge Network flows

Specialeforsvar: Andreas Holm Ditlevsen

Titel: An Adaptive Heuristic for Multi Commodity Fixed Charge Network flows

Abstract: The heuristic Adapted Large Network Search (ALNS) has shown promising results in vehicle routing problems, but there is limited research on its applications in other problems. Network flow problems have real life applications in everything from the shipping industry, to telecommunications, to computing which baseball teams are eliminated from a league.
We explore if ALNS can be used to find fast reasonable solutions to the Multi Commodity Fixed-Charge Network Flow problem. The problem consists of choosing which arcs to open, to minimize the cost of transporting a set of commodities across a network. The heuristic attempts to improve an initial solution by changing it iteratively in two steps.
First, one of multiple “destroy” functions is tasked with closing a subset of the arcs in the current solution. Next, one of multiple “repair” functions opens a set of currently closed arcs. The heuristic adapts to the problem by adjusting the probabilities of picking each destroy- and repair function based on their previous performance.
Computational experiments show that our implementation of ALNS can reduce the cost of a reasonable initial solution by up to 22%.

Vejleder: Giovanni Pantuso
Censor:    Konstantin Pavlikov, SDU