Variable Neighborhood Search for the Partition Graph Coloring Problem

Overview

The internet as global communication platform evolved to a pillar of modern society. Increasing demand to exchange data keeps putting a fundamental question to internet service providers: How to fulfill the consumers requests? When expanding communication networks one can either build new and expand existing networks, which means being forced to install additional cables and expensive hardware, or adapt the network to utilize existing devices and lines more efficiently. This is where the aspect of optimizing networks comes to mind. In this work we show in detail how to model and solve the real world problem of assigning wavelengths to communication lines in fibre networks relying on Wavelength Division Multiplexing (WDM) using the Partition Graph Coloring Problem (PCP). We will present a solution using metaheuristic approaches, namely a Variable Neighborhood Search (VNS).

Competition history

• ISEF 2014 Embedded Systems · Entry CS301

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.