Optimization of Cable Harness Routing

Abstract

The problem of routing several cables, which should be grouped into a compound structure, can be a time consuming process when done manually. In this thesis, this problem is modelled as a mixed integer linear programming (MILP) problem. There are several factors to consider when designing a harness routing, and the MILP model contains two conflicting objectives which minimize two specific factors: the length of each distinct cable and the usage of space. A collection of Pareto optimal solutions is computed by assigning different weights to the objectives. Two other factors that are considered in the model formulation are minimum clearance to obstacles, modelled as hard constraints, and preferable zones for the routes as soft constraints. The problem is a large-scale optimization problem, and Lagrangian relaxation is utilized in the solution process. A deflected subgradient method is used to solve the Lagrangian dual problem, and to provide upper and lower bounds on the optimal objective value. Ergodic sequences of the Lagrangian subproblem solutions are utilized for branching decisions during the subgradient iterations, and are also utilized for constructing so-called core problems. Our approach is applied to an industrial test case and it results in a good harness design with respect to the factors mentioned above. For the test cases in this thesis, the relative duality gaps vary between 0.59% and 21.7% for varying objective weights. Our results also indicate that we can get good solutions within an acceptable time frame, that is in a few minutes. We suggest a number of possible improvements of our approach to reduce the computing times.