ケーブルハーネスの自動配線の考え方

配線を「通してよい道のネットワーク」と「線の割り当て」と「束の中の並べ方」に分けて解く. 多品種流の整数計画, 交渉による混雑解消 (PathFinder), Cosserat rod による形の確認

要点: 自動配線は 1 本ずつ空間の最短路を引くより, 「道のネットワークを先に決め, その上で全部の線を同時に割り当て, 最後に束の中の並びと曲げを決める」の 3 段に分けると, 束がまとまり形がそろう.

3 段の分け方 #

段	決めるもの	解き方の例	同じ分け方の分野
1. 道のネットワーク	線を通してよい経路 (フレームに沿った区間, 分岐してよい点, 関節をまたぐ所)	構造の稜線・面からの一定距離の線, 人が描いた道, 骨格 (medial axis)	CAD の harness 設計 (CATIA / NX は bundle segment と branch point を先に引く)
2. 割り当て (global routing)	どの線がどの区間を通るか, どこで分岐するか	多品種流の整数計画 (MILP), 交渉による混雑解消 (PathFinder)	VLSI / FPGA の global routing
3. 束の中 (detailed routing)	区間の中での線の並び順, 角の丸め, 固定具の位置	区間ごとの並び (track assignment), 曲げ半径での丸め, 一定間隔の固定	VLSI の detailed routing, PCB の配線層

空間の格子で 1 本ずつ引く方法では, 束ねるのは「既に引いた線の近くを安くする」重みに頼る. 線を引く順番で結果が変わり, 曲げや重なりは後から直すことになる.

段 2 の定式化: 多品種流 + 固定費 #

道のネットワークを有向グラフ $G = (V, E)$ , 区間 $e$ の長さを $ℓ_{e}$ とする. つなぐ組 (線) $k$ ごとに流量 1 を流す.

$x_{k, e} \in {0, 1}$ : 線 $k$ が区間 $e$ を通るか
$y_{e} \in {0, 1}$ : 区間 $e$ を 1 本でも使うか (束の区間を作るか)

min k \sum e \sum ℓ_{e} x_{k, e} + e \sum f_{e} y_{e}

s.t. 各 k の流量保存, x_{k, e} \leq y_{e}, k \sum d_{k}^{2} x_{k, e} \leq C_{e} y_{e}

$f_{e}$ (固定費) が束ねる報酬になる. 同じ区間を何本で使っても $f_{e}$ は 1 回分なので, まとめて通すほど安い
$C_{e}$ は区間に通せる束の太さ (断面積) の上限. $d_{k}$ は線の外径
分岐する電源線などの多端子は, 端子の 1 つを根にして各端子への流れを作り, 区間の使用 $z_{n, e} \geq x_{n, t, e}$ をネットごとにまとめる (Steiner 木). 分岐点の口数の上限は節点の次数の制約で書ける
系統を分ける (電源と信号を同じ区間に入れない) は $x_{p, e} + x_{s, e} \leq 1$ の形の制約

Karlsson, Åblad, Hermansson ら (Chalmers, 2023) は長さ・束ねる報酬・通したい領域を目的に入れ, 決定的な方法で配線の形の候補を出して Pareto 前線を近似した. 産業規模の 3D の例 3 つで数秒〜数分 (根拠: arXiv:2311.09061, Computer-Aided Design 169 (2024)). 同じグループの修士論文は MILP と Lagrange 緩和 (劣勾配法) で上界と下界を出している (Optimization of Cable Harness Routing). 配線図の形と 3D の位置を 1 つの MILP にまとめた例もある (arXiv:2603.08157).

段 2 の別解: 交渉による混雑解消 (PathFinder)#

McMurchie と Ebeling (1995) の FPGA 配線法. 全部の線を一度は資源の取り合いを許して引き, 取り合いの多い所の値段を上げて引き直すことを繰り返す.

c_{n} = (b_{n} + h_{n}) p_{n}

$b_{n}$ : 元の値段 (長さ)
$h_{n}$ : 履歴. 取り合いがあった回ごとに増える
$p_{n}$ : 今の取り合いの数に応じた係数

引く順番に結果が左右されにくい. MILP が大きすぎるときの代わりになる (根拠: PathFinder の解説).

出口のまわりと束を分けて引く #

束を縦横 (軸に平行) にそろえ, 角と角の間を 2R (R は最小曲げ半径) 空けると, 曲げ半径は守れる. ただし出口が狭い所にあると, 2R のまっすぐな長さが取れず, 大回りになるか角がきつくなる.

部分	引き方	同じ分け方の分野
出口のまわり (出口から一定距離)	斜めを許した格子の最短路 → 直線に間引く → 曲げ半径が入らない角を曲線 (ベジェ) に置き換える	PCB の fanout / breakout (BGA の下は斜めや細い線で外へ出す)
その外 (束)	状態を (ボクセル, 進む向き) にした Dijkstra. 曲がる手は「曲がって 2R まっすぐ進む」まで	VLSI の Manhattan routing

2 つのつなぎ方: 縦横の探索を「出口のまわりの全部のボクセル」から始めてよいことにし, 各ボクセルの初期値をそこまでの格子の最短路の重みにする (多始点の Dijkstra). 終わりも同じ
つなぎ目の角: 縦横は始めに 2R まっすぐ進む, 出口の方へ戻る向きでは始めない. これが無いと, つなぎ目で角が詰まるか折り返す
出口のまわりで縦横の探索に「自由に曲がる手」を足す方法は, 曲げ半径を見ずに角を作るので, 後で丸めきれない角が増える
出口のまわりは, 出口そのものでなく, 出口からまっすぐ出した先の点から測る (長く下ろしてから曲がる出口がある)
丸めきれない角を 3 次ベジェ曲線に置き換える方法は, 両端の点と向きを決めると, 両端が近く向きが大きく違う所で曲率半径 R を守れない. 「円弧 - 直線 - 円弧」(Dubins 経路の CSC) なら半径 R を守る形を直接作れる. 両端を辺の途中にも取ると候補が増える

分岐の部品 (継ぎ・端子台) を置く所 #

分岐を部品 (WAGO などのレバー式の継ぎ) でする場合, 部品の位置を「つながる端子までの距離の合計が最小」で決めると, 束から離れた角に置かれやすい. 線は部品から各端子へ別々に出る
先に部品なしで木 (Steiner 木) を引き, その分岐点を部品の目標にして, 目標から一定距離以内の取り付け面だけから選ぶと, 部品が束の上に乗る
分岐点が取り付け面から遠い (宙で分かれる) ときは目標を使わない. 一番近い面に寄せると, 線が長くなることがある

動く所 #

関節をまたぐ線は, 道のネットワークに「またぐ区間」(ケーブルキャリア, 回転部の巻き取り) を置き, その区間の長さを関節の可動範囲から決める
たるんだ部分の形 (重力・曲げ剛性) は Cosserat rod のモデルで計算できる. Fraunhofer の IPS Cable Simulation はこれを使い, 格子で探した経路をこのモデルで細かく直す (Fraunhofer ITWM, Chalmers)

ケーブルハーネスの自動配線の考え方

3 段の分け方 #

段 2 の定式化: 多品種流 + 固定費 #

段 2 の別解: 交渉による混雑解消 (PathFinder)#

出口のまわりと束を分けて引く #

分岐の部品 (継ぎ・端子台) を置く所 #

動く所 #

関連 #

On this page

ケーブルハーネスの自動配線の考え方

3 段の分け方#

段 2 の定式化: 多品種流 + 固定費#

段 2 の別解: 交渉による混雑解消 (PathFinder)#

出口のまわりと束を分けて引く#

分岐の部品 (継ぎ・端子台) を置く所#

動く所#

関連#

On this page

3 段の分け方 #

段 2 の定式化: 多品種流 + 固定費 #

出口のまわりと束を分けて引く #

分岐の部品 (継ぎ・端子台) を置く所 #

動く所 #

関連 #