Briefly the four node problem was devised by The National Grid Company plc as test problem for scheduling the maintenance of electrical transmission lines.
The problem is how to schedule the maintenance of eight electrical power transmission lines arranged in pairs which connect four nodes (or substations) so as to disrupt the supply of electricity the least. Each line takes one week to maintain, all eight have to be maintained within a nine week plan.
The line capacities, generator capacities and power demand are set to make the problem highly constrained. Having solved this problem, we are now looking at much larger real world problem, namely scheduling maintenance of the South Wales region for the current year. This problem has been made more difficult by increasing the maintenance required and the number of weeks needed to do each one.
Various documents describe the problem and our attempts at solving it using a greedy scheduling heuristic with a permutation based GA.
Java demonstration. Code for the fitness function and existing GA is available via anonymous ftp cs.ucl.ac.uk genetic/ga-code/four_node
Solutions have also been obtained with a modified version of the timetabling GA, PGA
last update 22 April 2011