|Description:|| Every LOFAR field had a unique cable layout. Making a unique cable layout is a rather delicate process that takes a considerable amount of time when done manually, which it currently is.|
As an intern at ASTRON, I took it upon myself to solve this issue with an algorithm and started by looking at similar graph problems for both inspiration, and perhaps an easy solution. The most related graph problem is the Steiner tree problem. A Steiner tree is an extension to a minimum spanning tree, where so called “Steiner points” are added to minimize the the total distance. Unfortunately no implementation is available that meets all the specific requirements necessary to solve the issue at hand.
So I designed a problem specific algorithm, along with approximately twenty template layouts. The algorithm will measure the cost of combining the input matched with a template, for all templates. The cost is based on the cost of cable length (only 85 meter or 115 meter cables are used) and the total amount of digging done. The best combination will be given as result.
After this process the best result will be tidied up by the algorithm to meet certain demands that are important for the quality of the LOFAR field.
For several LOFAR fields not in the template solutions, the algorithm I implemented produces better results than manually generated ones. The cable layout code now lives on Github and may be used for future international LOFAR fields.
|Copyright:||Thomas Tijsma / Tammo Jan Dijkema|