Wiring layout design reducing cable and trace cost

摘要

We give an efficient constructive deterministic approximation algorithm that determines minimum installation layouts with respect to cable cost and trace cost (the latter for supporting and safeguarding the cables) in order to embed intensity weighted flow nets (wiring diagrams, power supply systems, ...) into industrial, technical, or urban environments. We show, that the algorithm observes a convenient upper cost bound and prove its polynomial time behavior. The resulting layout strucures can be viewed as hybrids derived from General Steiner Trees as well from solutions for the Quadratic-Semi-Assignment Problem. The success of the algorithm is based on the search for partial structures that enable common line conduction on common traces with only moderate increased cable cost (compared with shortest path conduction) but with more reduced trace cost. Practical results are given.