(57)【特許請求の範囲】
【請求項１】
ケーブリングの対象となる装置内で使用される構成要素を表す複数のボックス（４）と、２つの構成要素間の接続を表す接続線（６）と、接続線（６）とボックス（４）の間の可能な接続点に対応する端子とが配置される配線図（ＷＤ）の自動作成プロセスであって、前記複数のボックス（４）は、横軸および縦軸に沿って配置され、
前記配線図上に表現される構成要素を情報システムへ入力するステップであって、各構成要素は、予め線形方程式（Ｒ）の形式に書き換えられた一定の制約が対応する所定のタイプに属するステップと、
前記配線図上に表現される接続を情報システムへ入力するステップと、
横軸上の複数のボックスの相対配置を所定の横座標に対して最適化するとともに、前記ボックスの向きを最適化するように、第１の方程式系を情報システムにより生成し、情報システムにより前記系を解くステップと、
複数のボックスの相対配置を縦軸に対して最適化するとともに、各ボックスの端子の相対配置を同じ前記軸に対して最適化するように、第２の方程式系を情報システムにより生成し、情報システムにより前記系を解くステップと、
複数のボックスを横軸および縦軸に対して絶対的方式で配置するとともに、接続のルーティングも最適化するように、第３の方程式系を情報システムにより生成し、情報システムにより前記系を解くステップとを含むことを特徴とするプロセス。
【請求項２】
表現される接続は、１本または複数本のワイヤで構成されるケーブルであり、シースが、複数本のワイヤで構成されるケーブルに関連づけられ、横軸上のボックスの相対配置を行う際、ケーブルのシースが、接続されるボックスに対して相対的に配置されることを特徴とする請求項１に記載のプロセス。
【請求項３】
第３の方程式系の生成を含むステップは、以下の２つのサブステップ、すなわち、
複数のボックスを縦軸に対して絶対的方式で配置するように、第３の方程式系を情報システムにより生成し、情報システムにより前記系を解くステップと、
複数のボックスを横軸に対して絶対的方式で配置するとともに、接続のルーティングを最適化するように、第４の方程式系を情報システムにより生成し、情報システムにより前記系を解くステップとによって実施されることを特徴とする請求項１または２の一項に記載のプロセス。
【請求項４】
接続のルーティングの最適化は、文字列の配置を目的とする接続上の場所の存在を検証することを提供することを特徴とする請求項１から３の一項に記載のプロセス。
【請求項５】
文字列を設定する場所の存在を検証した後、接続上の文字列の配置が、方程式系を解くことによって決定されることを特徴とする請求項４に記載のプロセス。
【請求項６】
線形方程式は、専ら整数のみを使用することを特徴とする請求項１から５の一項に記載のプロセス。
【請求項７】
ボックス（４）は、そのサイズと端子によって定義され、前記ボックスは、図記号および／または文字列および／または１つまたは複数の端子に関連づけられたケーブル記号をもつこともあることを特徴とする請求項１から６の一項に記載のプロセス。
【請求項８】
ボックスのタイプは、とりわけ、ボックスの幅が可変かどうか、高さが可変かどうか、端子の順序が変更可能かどうか、ボックスがアウトレットを備えているかどうかなどを決定することを特徴とする請求項１から７の一項に記載のプロセス。
【請求項９】
第１の方程式系に関して、表現される異なるボックスは、所定の本数の垂直線上に配置されるものとし、前記第１の方程式系は、前記垂直線上のボックスの配置に関する制約を書き換える方程式で構成されることを特徴とする請求項１から８の一項に記載のプロセス。
【請求項１０】
第１の方程式系は、ボックスを接続する導電線によって形成される屈曲の数を求める方程式で構成され、前記数は、対応するステップにおいて最小化される傾向にあることを特徴とする請求項１から９の一項に記載のプロセス。
【請求項１１】
第２の方程式系は、異なるボックス内の接続端子のグループ化に関連する制約を書き換える方程式で構成されることを特徴とする請求項１から１０の一項に記載のプロセス。
【請求項１２】
第２の方程式系は、ボックスを接続する導電線の間で形成される交わりの数を求める方程式で構成され、前記数は、対応するステップにおいて最小化される傾向にあることを特徴とする請求項１から１１の一項に記載のプロセス。
【請求項１３】
縦軸に沿ったボックスの絶対配置に関して、ボックスの接続端子は、すべて所定のグリッドピッチの倍数である高度に配置されることを特徴とする請求項１から１２の一項に記載のプロセス。
【請求項１４】
縦軸に沿ったボックスの絶対配置に関して、接続線の切断の数を求める方程式が立てられ、切断の前記数は、最小化されることを特徴とする請求項１から１３の一項に記載のプロセス。
【請求項１５】
横軸に沿ったボックスの絶対配置に関して、水平方向および垂直方向について接続線におけるオーバラップの数が求められ、最小化されることを特徴とする請求項１から１４の一項に記載のプロセス。
【請求項１６】
横軸に沿ったボックスの絶対配置に関して、接続の交わりの数が求められ、最小化されることを特徴とする請求項１から１５の一項に記載のプロセス。
【請求項１７】
様々な方程式系の方程式を立てる目的で、一方では、位置や大きさなどに対応する変数である、実数変数が定義され、他方では、要素が集合に属するかどうかを指示したり、２つの要素の相対配置を指示したりするための、値０か値１のいずれかをとる２進変数が定義され、前記変数を利用して、方程式が、作成される配線図のタイプに特有の制約の書き換えとなることを特徴とする請求項１から１６の一項に記載のプロセス。
【請求項１８】
様々な方程式系を解くステップの後で、手順がさらに、以下のステップ、すなわち、
前記解くステップから得た解を、数値データに基づく図の作成を可能にする変換器に導入するステップと、
方程式系を解くことによって得られた数値データに対応する配線図（ＷＤ）を作成するステップとを含むことを特徴とする請求項１から１７の一項に記載のプロセス。
【請求項１９】
情報記憶媒体に保存されるコンピュータプログラムであって、前記プログラムは、情報システムによってロードされ、実行されたときに、請求項１から１８のいずれか一項に記載の最適化プロセスの実施を可能にする命令を含むコンピュータプログラム。
【請求項２０】
請求項１から１８のいずれか一項に記載の手順を実施するように構成された手段を含むことを特徴とする情報システム。
【請求項２１】
情報システムによって可読な、おそらく全体的または部分的に交換可能なデータ媒体であって、より具体的には、ＣＤ−ＲＯＭ、またはハードディスクまたはフロッピディスクなどの磁気記録媒体、または電気的または光学的信号などの伝送媒体であり、プログラムが情報システムによってロードされ、実行されたときに、請求項１から１８のいずれか一項に記載の手順の実施を可能にするコンピュータプログラムの命令を含むことを特徴とするデータ媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、配線図を作成するための手順に関する。
【０００２】
本発明は、より詳細には、航空学分野での利用を意図している。しかし、本発明は、（自動車、宇宙など）輸送分野であろうと、（産業機械の製造、コンピュータ化ホームエレクトロニクスシステムなど）その他の産業分野であろうと、その他の部門でも応用することができよう。本発明は、より詳細には、電気ケーブル配線に関するが、流体力学や空気力学などの分野にも適用される。
【背景技術】
【０００３】
現代の航空機では、電気回路は、非常に多くの構成要素を利用し、相対的に複雑になっている。まず第１に製作し、その後は航空機のサービス保守に役立てることができるように電気回路を表現するために、一方では基本平面図が、他方では配線図が作成される。
【０００４】
航空機は、様々な異なる電気システム（エンジン、発電、操縦装置、ブレーキシステムなど）から構成される。これらのシステムは各々、ＡＴＡ１００規格（航空輸送協会）に準拠する機能とも呼ばれる異なる区分に分割される。基本平面図は、システム内の１つの機能を構成する異なる要素間の電気的な相互接続を概略的に説明する。基本平面図によって、説明された機能を深く理解することができ、故障時の原因究明が容易になる。配線図（Ｗｉｒｉｎｇ  Ｄｉａｇｒａｍ）（すなわち、配線レイアウト図の英語名）を表す短縮形でＷＤとも呼ばれる配線レイアウト図（または平面図）は、基本平面図に含まれる情報に基づいて設計され、システム内の対応する機能の製作に必要なすべての情報を統合する。配線図はまた、電気システムを製作することを担当する部門に、ケーブルの一覧を提供することを可能にする。
【０００５】
現在、配線図ばかりか基本平面図も、手作業で作成されている。もちろん、これらのプランおよび図を作成するため、ＣＡＤソフトウェアアプリケーション（コンピュータ支援設計）が使用される。しかし、図面設計それ自体は、相変わらず製図工の責任であり、製図工は、構成要素を配置し、構成要素どうしを接続するケーブルのルートを作成しなければならない。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明の目的は、航空機（またはその他の産業「機械」）の運用寿命にわたって作成される配線図の手作業による作成を、図の自動生成で置き換えることである。多くのグラフィックデザイン規則を満たさなければならない。配線図の自動作成は、多くのグラフィックデザイン規則のため、非常に複雑になる。既存の制約の中には、例えば、図に表現されるケーブルは図に表現される構成要素を横切ってはならないというものがある。また、ケーブルどうしは重なり合ってはならない。ケーブルは水平または垂直の線分によって単独で描かなければならない。２つの隣り合う「対象物」（ケーブルまたは構成要素）の間には、十分な間隔が保たれていなければならない。いくらか緩やかなその他の制約も、好ましくは同じように守らなければならない。したがって、例えば、表現される様々な構成要素は、好ましくは垂直方向に整列させなければならない。さらに、ケーブルどうしの交差の数、およびケーブルが形成する屈曲の数は、最低限に抑えなければならない。ここに挙げたこれらの制約は、例として提示したに過ぎず、網羅的な列挙を意図したものではない。
【課題を解決するための手段】
【０００７】
自動的に生成される配線図の作成を可能にするため、本発明は、ケーブリングの対象となる装置内で使用される構成要素（または構成要素の部品）を表し、横軸および縦軸に沿って配置されるボックスと、２つの構成要素間の接続を表す接続線と、接続線とボックスの間の可能な接続点に対応する端子とが配置される配線図の作成のための手順を提案する。
【０００８】
本発明によれば、この手順は、以下のステップ、すなわち、
前記配線図上に表現される構成要素を入力するステップであって、各構成要素は、予め線形方程式の形式に書き換えられた一定の制約が対応する所定のタイプに属するステップと、
前記配線図上に表現される接続を入力するステップと、
横軸上のボックスの相対配置を所定の横座標に対して最適化するとともに、前記ボックスの向きを最適化するため、第１の方程式系を生成し、前記系を解くステップと、
ボックスの相対配置を横軸に対して最適化するとともに、各ボックスの端子の相対配置を同じ前記軸に対して最適化するため、第２の方程式系を生成し、前記系を解くステップと、
ボックスを横軸および縦軸に対して絶対的方式で配置するとともに、接続のルーティングも最適化するため、第３の方程式系を生成し、前記系を解くステップとを含む。
【０００９】
上記の「入力」という語によって、例えば、データベースから獲得されるデータまたはデータベースによって出力されるデータといったデータの情報システムへの導入を可能にする手動または自動の任意の方法を意味すると理解されたい。
【００１０】
解かれる対象となる複雑な問題を細分化することによって、配線図を作成することができるように、その問題を解くことができる。また、問題を細分化することによって、ステップ毎に常に、配線図を全体として理解することができる。
【００１１】
作成される図において、表現される接続は、例えば、ケーブルと呼ばれ、ケーブルは、１本または複数本のワイヤで構成される。シースが、複数本のワイヤで構成されるケーブルに関連づけられることがある。横軸上のボックスの相対配置を行う際、ケーブルシースが、有利には、接続されるボックスに対して相対的に配置される。ケーブルシースは、特殊なタイプの構成要素を構成するので、本発明では、その他の構成要素とは少し異なる扱いをされる。実際、シースは、具体的には、ワイヤおよび／またはケーブルが横断できる構成要素を構成するという事実、およびシールドのための最終的なチェックポイントを図表現することが意図された接続点を提示できるという事実によって、その他の表現される構成要素とは異なっている。
【００１２】
上述のプロセスにおいて、第３の方程式系の生成を含むステップは、有利には、以下の２つのサブステップ、すなわち、
ボックスを縦軸に対して絶対的方式で配置するため、第３の方程式系を生成し、前記系を解くステップと、
ボックスを横軸に対して絶対的方式で配置するとともに、接続のルーティングを最適化するため、第４の方程式系を生成し、前記系を解くステップとによって実施される。
【００１３】
本発明による手順において、接続のルーティングの最適化は、有利には、文字列の配置を目的とする接続上の配置場所の存在を検証することを提供する。実際、大部分の配線図では、接続（ケーブルまたはワイヤ）が、１つまたは複数の文字列によって表記されている。文字列を配置する配置場所の存在を検証した後、接続上の前記文字列の配置が、例えば、方程式系を解くことによって決定される。
【００１４】
本発明による手順によって非線形問題も解くことができるように、例えば、本明細書で設定される線形方程式は整数（ｗｈｏｌｅ  ｎｕｍｂｅｒ）のみを使用するように提案される。
【００１５】
最初の方式では、ボックスは、そのサイズと端子によって定義され、ボックスは、図記号および／または文字列および／または１つまたは複数の端子に関連づけられたケーブル記号をもつことがあるようにする。
【００１６】
上で指摘したように、使用されるボックスは、異なるタイプに属する。ボックスのタイプは、例えば、とりわけ、ボックスの幅が可変かどうか、高さが可変かどうか、端子の順序が変更可能かどうか、ボックスがアウトレットを備えているかどうかなどを決定する。
【００１７】
上述した第１の方程式系に関して、表現される様々なボックスは、有利には、所定の本数の垂直線上に配置されるものとし、前記第１の方程式系は、前記垂直線上のボックスの高さ配置に関する制約を書き換える方程式で構成されるようにする。
【００１８】
第１の方程式系はまた、ボックスを接続する導電線に形成される屈曲の数を求める方程式と、対応するステップで提供される解くステップにおいて屈曲の数を最小化するその他の方程式とで構成することができる。
【００１９】
上述した第２の方程式系は、それ自体で、例えば、異なるボックス内の接続端子のグループ化に関連する制約を書き換える方程式で構成される。この第２の方程式系は、ボックスを接続する導電線の間で形成される交わりの数を求める方程式で構成され、その数は、対応するステップにおいて減少させられる傾向にあるようにすることもできる。
【００２０】
縦軸に沿ったボックスの絶対配置に関して、ボックスの接続端子は、有利には、すべて所定のグリッドピッチの倍数である高度に配置される。これと同じ配置に関して、同じように、接続線における切断の数を求める方程式を立て、この切断の数を最小化することができる。
【００２１】
横軸に沿ったボックスの絶対配置に関して、有利には、水平方向および垂直方向について接続線におけるオーバラップの数が求められ、その後、それが最小化される。その場合、例えば、接続線における交わりの数を求め、それを最小化することもできる。
【００２２】
様々な方程式系の方程式を立てるための本発明による手順において、有利には、一方では、例えば、位置や大きさなどに対応する変数である、実数変数を定義し、他方では、例えば、要素が集合に属するかどうかを指示したり、２つの要素の相対配置を指示したりするための、値０か値１のいずれかをとる２進変数を定義し、その後、前記変数を利用して、方程式が、作成される配線図のタイプに特有の制約の書き換えとなる。
【００２３】
配線図をモニタ画面上もしくはその他の視覚化手段上に、またはさらに紙媒体もしくは類似の媒体上にも表示するため、上述したような手順を実施した後、そのような手順がさらに、様々な方程式系を解くステップの後で、以下のステップ、すなわち、
前記解くステップの結果である解を、数値データに基づく図の作成を可能にする変換器に導入するステップと、
方程式系を解くことによって得られた数値データに対応する図を作成するステップとを含むようにする。
【００２４】
本発明はまた、上で簡単に説明したような手順を実行するように構成された手段を含む情報システムおよびコンパイラも対象とする。
【００２５】
本発明はまた、情報システムによって可読な、おそらく全体的または部分的に交換可能なデータ媒体であって、より具体的には、ＣＤ−ＲＯＭ、またはハードディスクまたはフロッピディスクなどの磁気記録媒体、または電気的または光学的信号などの伝送媒体であり、プログラムが情報システムによってロードされ、実行されたときに、上で簡単に説明したような手順の実施を可能にするコンピュータプログラムの命令を含む可読データ媒体も対象とする。
【００２６】
本発明はまた、情報記憶媒体に保存され、プログラムが情報システムによってロードされ、実行されたときに、上で簡単に説明したような手順の実施を可能にする命令を含むコンピュータプログラムも対象とする。
【００２７】
本発明の詳細および利点は、以下の説明を添付の概略図を参照しながら読むことによって、より良く理解することができるであろう。
【発明を実施するための最良の形態】
【００２８】
図１に、本発明による手順を用いて作成できる配線図の一例を示す。このような配線図は、電気的な機能を生みだすことができる装置の全部または一部に相当する。図１のケースでは、別の配線図（図１には図示せず）との接続を可能にする中立域２の存在に留意されたい。
【００２９】
図１の配線図には、ほぼ長方形をしたボックス４が存在することにも留意されたい。ボックス４のタイプには、多くの形態が存在する。これらのボックスは、ケーブルを記号化したリンク（または接続線）６を用いて相互接続される。これらの接続線６は、ボックス４に端子レベルで接続される。端子は、ボックス４上に直接、またはボックス４と一体化したアウトレット８のレベルで配置される。同じボックス４が同時に、接続線６に直接結合するための端子と、少なくとも１つの端子を備える１つ（または複数）のアウトレット８とを備えることができる。いくつかのボックス４は単に、アウトレットおよび／または端子を備える長方形の形態で存在する。これとは別に、その他のボックス４は、ボックスによって表される構成要素の識別を可能にする図形と併せて構成される。ボックスまたは対応する導電線の識別を可能にする英数字から形成された文字列が、各ボックス４および各ライン６に関連づけられて存在することにも留意されたい。
【００３０】
図２は、配線図を構成する様々な要素を要約したものである。図２の中には、その上に配線図を作成するシート１０が配置されている。このシートは、「ｓｈｅｅｔ」という英語名をもつ。このシート１０に関しては、シート上に何を図示するかだけでなく、シートの版型（例えば、Ａ３またはＡ４など）を知ることも重要である。図２の下側の部分に、シート１０を構成する様々な要素が示されている。まず最初に、上で説明した作図領域が存在し、この上に、具体的には、ボックス４およびライン６が出現する。ライン６は具体的には、上で指摘したようなケーブル（またはワイヤ）を表すが、ある場合には、このラインは、図１から分かるように、相互参照１２と見なすこともできる。
【００３１】
通例、シート１０上には、大概は長方形の形をしたカルトゥーシュ（ｃａｒｔｏｕｃｈｅ）（図１には図示せず）も存在する。このカルトゥーシュは一般に、シートの右側および／または作図領域の下側に配置される。カルトゥーシュ内には、その書類を識別し利用するのに必要かつ十分な説明書きが表記される。このようなカルトゥーシュには、対応する配線図を作成した個人名と並んで、その図を作成した企業名も大概含まれる。その他の表示（題名、日付、識別番号など）も、カルトゥーシュ内に表記される。このカルトゥーシュに加えて、具体的には図１に見ることができるような注記１４を提供することも可能である。注記は、作図領域に表される構成要素についての全体的な指摘を提供する。
【００３２】
当業者に知られているように、配線図を作成するには、作図規則を守らなければならない。説明のため、図３の表に、これらの規則のいくつかを改めて示す。この表の左欄には、正しい図表現が、右欄には、正しくない図表現が示されている。したがって、図３の表は、ライン６はボックス４と交差してはならないことを思い出させる。２本の異なるラインが重なり合うことも許されない。これらのラインは、水平または垂直の線分によって表さなければならない。また、作図領域に出現する様々な対象物（ボックスおよびライン）の間に十分な間隔（一般には５ｍｍ）をとれるようにするのがよい。最後に、図３の表は、ラインが構成要素の周りを回ってはならないことを示している。
【００３３】
図４の表は、それ自体で、可能な限り実施すべき、最適化に対する制約を示している。この表の左欄には、好ましい図表現が、右欄には、可能な限り避けるべき図表現が示されている。したがって、ボックスは縦方向に整列させ、ラインが互いに交差する数、およびラインが形成する屈曲の数は最小限に抑え、また、ラインのルートは互いに調和させることが好ましい。
【００３４】
図５は、配線図に出現するボックスの図構成を概略的に示したものである。ボックスは、配線図内の横座標ｘおよび縦座標ｙに配置される。ボックスは長方形をしており、（横軸方向に）幅ｗ、（縦軸方向に）高さｈを有する。ボックス４は、それ自体の長方形の輪郭に加えて、場合によっては、図記号、および／または文字列、および／またはそのボックスに接続されるケーブルのタイプを表す記号を有することができる。
【００３５】
図６は、端子の図構成を概略的に示したものである。本明細書では、接続点またはアース端子、さらにはデッドエンド（すなわち、接続されていない、またはシールドを被せたケーブルの端部）を端子と見なす。
【００３６】
本発明による手順を実施する場合、表現されるボックスの異なるタイプを事前に分析しておくのがよい。実際、ボックス４があるタイプの構成要素を表すのか、それとも別のタイプの構成要素を表すのかに応じて、表現されるボックスには異なる制約が適用されることに留意されたい。したがって、一例として、ボックスは一定の寸法を有することができ、または可変の寸法を有することができる。ある種の構成要素では、対応する端子を所定の順序で、または任意の順序で表すことが可能である。
【００３７】
したがって、配線図上に表現することのできるすべての構成要素を分析した後、構成要素をそのタイプによって、また配線図上の構成要素を表すボックスの作図を開始したときに守るべき制約の関数で再グループ化するのがよい。
【００３８】
図７から図９は、異なるタイプの構成要素を表す。図７には、「終端」と呼ばれる構成要素が表されている。そのような構成要素は、専ら文字列および図記号からなる。そのような構成要素は、例えば、ラインの終端に見出すことができる。
【００３９】
図８では、「装置」と恣意的に名づけられた一タイプの構成要素が説明されている。図８に示すように、「装置」タイプの構成要素を表すボックスは、１個からｎ個のアウトレットと、０個からｎ個の端子を含む。各アウトレットは、１個からｎ個のアウトレットを含み、アウトレットの端子の順序は、任意に選択してよい。「装置」タイプの構成要素では、そのサイズは、高さおよび幅に関して様々であってよい。構成要素のアウトレットは、２つの「サブアウトレット」に分割することができる。「装置」のアウトレットは、配向することができる。しかし、「装置」は、断片化することはできない。「装置」は、配線図の中立域２に存在することができる。この構成要素の端子の順序は、任意に選択してよい。
【００４０】
図９では、複数のタイプの構成要素が定義されている。例えば、最初に、「ダイオード、抵抗」タイプの構成要素がある。そのような構成要素は、２つの端子をもち、端子の順序は定められている。次に、「ＶＤ、ＶＲ」タイプの構成要素がある。そのような構成要素は、１個からｎ個の「ダイオード、抵抗」タイプの構成要素を含む。「ＶＤ、ＶＲ」タイプの構成要素は、１つのブロック内では同じ向きを維持するのがよく、ブロックの順序は任意に選択してよく、端子は２つずつ確実に接続される。「ＶＳ」タイプの構成要素もやはり、１個からｎ個の端子をもつ。端子の順序は任意に選択してよく、接続は構成要素の両サイドで行われる。最後に、図９では、「ＶＤ、ＶＲ」タイプの構成要素、または「ＶＳ」タイプの構成要素からなる、「モジュール」タイプの構成要素が定義されている。そのような「モジュール」は、幅が一定であり、高さは可変であり、断片化が可能であり、中立域（隣り合う２つのシートで共通の区域）に配置されることはない。
【００４１】
もちろん、構成要素タイプの数は、できる限り制限するのが好ましい。適用例（航空、自動車、コンピュータ化ホームエレクトロニクスシステムなど）の機能においては、構成要素タイプの数は、程度の差こそあれ多くなる。本発明による手順の実施に先立つ、タイプについての上述の定義は、以上をもって終りとする。
【００４２】
次に図を作成する前に、図に描かなければならない異なる構成要素、および構成要素を接続する方法について簡単に述べておくのがよい。この複数の情報は、例えば、作成すべき図に対応する基本平面図から獲得することができ、またはデータベースから取得することができる。
【００４３】
次に本発明による手順は、表現されるボックスおよびボックス間の導電線に関する供給された情報に対応するデータを数式で表現する。配線図の作成に関連するすべての制約を表現し直した方程式系の生成を企てることができる。（大部分の配線図がそうであるが）少ないところで高々１０個程度のボックスを表現しなくてはならない場合でも、非常に多くの数式からなる方程式系が得られるため、どのようなコンピュータでも、実際に数式を解くことができない。したがって、本発明は、方法の各ステップで配線図の包括性を常に考慮しながら、問題を複数の副問題に分割することを提案する。以下の説明では、全体として考察される問題は、４つの連続する数学的操作によって解かれる。場合によっては、第３および第４の操作は、１つの操作にまとめることができる。
【００４４】
本発明はまた、線形計画法の使用を提案する。有利には、記述された等式および不等式では、整数だけが使用される。これらの手段によって、非線形問題を解くことが可能になる。一方では、作図規則に関する制約が、他方では、表現されるボックスのタイプを定義する制約が、線形方程式の形式に書き換えられる。
【００４５】
図１０には、本発明による配線図を作成するための手順の主要ステージが、概略的に示されている。図１０でＰ．Ｄ．（すなわち、英語で主要図（Ｐｒｉｎｃｉｐａｌ  Ｄｉａｇｒａｍ）または基本平面図）と呼ばれる基本平面図中に見出されるデータと、図３および図４に概略的に示したような規則Ｒとに基づいて、様々な方程式系が設定される。第１のステージ１００で、配置されるボックスの相対位置およびボックスの向きについての制約を書き換える数式が記述される。この第１のステージでは、水平軸上へのボックス４の相対配置について考察する。第１の操作に対応する長方形の中には参照番号１５０が記入されているが、これは、水平軸上にボックスを相対的に配置した後、それとは別に、水平軸上にケーブルシースを相対的に配置することを示している。
【００４６】
参照番号２００をもつ第２のステージでは、垂直軸上への異なる構成要素の相対配置について考察する。この配置は、具体的には、接続線６どうしが作る交差に影響を及ぼす。この第２のステージにおいて記述された数式を解くことによって、垂直方向における様々な構成要素の相対的な配置が分かる。
【００４７】
様々な構成要素が互いに対して相対的に配置されたので、次に参照番号３００をもつ第３のステージに進み、異なるボックス４を垂直線上に絶対的に配置する。この配置を最適化するため、ボックスを接続する接続線が形成する屈曲の数を制限するよう試みる。
【００４８】
参照番号４００をもつ第４のステージは、水平線上への様々な要素の絶対的配置に関する。このステージ４００において、数式を記述し、それを解くことによって、ケーブルのルートが最終的に決定され、配線図に書き込まれる文字列が配置される。
【００４９】
場合によっては、ステージ３００と４００を１つのステージとして処理できることが予め分かることがある。このことは、図１０では、ステージ３００および４００を象徴するボックスの結合によって象徴的に表されている。本発明による上記の手順によって、ステージ１００、２００、３００，４００を実施した後、配線図Ｗ．Ｄ．を得ることができる。
【００５０】
図１０に示すように、ステージ５００を提供することもできる。これは、取得した図へのテキストの配置、および、例えば、航空業界向けの配線図で使用される経路設定に関するコメントまたは類似の事項の挿入に関するステージである。このステージは、本発明による手順に組み込むことができるが、全く別の手順として実施することもできる。
【００５１】
図１１に、本発明に従って、好ましい実施形態で、配線図を作成するための手順を実行するように構成された装置を概略的に示す。
【００５２】
この装置は、具体的には、コンピュータで構成される。
【００５３】
本明細書で説明する例示的な実施形態では、配線図を作成するための装置は、プロセッシングカードの入出力ポートに接続されるキーボード、モニタ画面、およびプリンタを含む。
【００５４】
プロセッシングカードは、アドレスバスおよびデータバスによって相互接続される以下の要素、すなわち、
中央処理装置すなわちＣＰＵ、
読み書きメモリすなわちＲＡＭ、
読み取り専用メモリすなわちＲＯＭ、
不揮発性メモリすなわちＤＩＳＣ、
入出力ポートすなわちＥ／８を含む。
【００５５】
図１１に示す各要素は、マイクロプロセッサ、より一般的にはデータ処理システムの分野の技術者にはよく知られている。したがって、本明細書では、これらのよく知られた要素については説明しない。
【００５６】
ＤＩＳＫ上の不揮発性メモリは、例えば、ハードディスクで構成される。
【００５７】
読み取り専用メモリすなわちＲＯＭは、中央処理装置すなわちＣＰＵのオペレーティングプログラムを格納するように構成される。より具体的には、図１０の手順フローチャートを参照して先に説明したような、本発明に従った手順を実施するプログラム命令を記憶するための「プログラム」レジスタで構成される。作成された配線図は、モニタ画面上に視覚化することができ、情報システムのプリンタによって印刷することができる。
【００５８】
以下に示す各操作の説明において、例として挙げる数式は、例示的なものとして提供されており、当業者であれば、各自の問題に応じて数式を変更して、自動的に配線図を作成することができるであろう。
【００５９】
第１の操作
この第１の操作の目的は、表現されるボックスおよびその他の要素を互いに関係させて、水平方向に配置することである。本明細書では、２次元平面図［２Ｄ］である配線図は、水平の横軸（ｘ）と垂直の縦軸（ｙ）を含むとする。横座標は、平面の後方から前方に向って増加し、縦座標は、平面の下方から上方に向って増加する。
【００６０】
第１の操作時に、構成要素の向きを定めたい。構成要素を適切な向きに配置することによって、接続線のレベルで形成される屈曲の数を制限することができる。各ボックスについて、少なくとも２つの可能な向きがある。先に指摘したように、ボックスは長方形の形をしている。ボックスは２本の水平の辺と２本の垂直の辺をもつ。ボックスの端子は垂直の辺上に配置される。したがって、ボックスの向きは、そのボックスの端子の向きをどう決めるか、すなわち、どの端子を配線図の前方に向けるかによっている。ボックスが独立の端子を含む場合、可能な端子の向きの数は非常に多くなり得る。
【００６１】
垂直線上にボックスを整列させるため、例えば、配線図上に１０本の垂直線を提供し、表現されるボックスを中心線が前記垂直線に合わさるように配置することができる。表現される図の前記垂直線の最初および／または最後の線が中立域２に対応し、かつ／または前記垂直線のどれも中立域２に対応しない。図１の例では、最後の垂直線だけが、中立域内２に存在する。中立域内では、一定のタイプの構成要素だけが見出される。
【００６２】
配置変数
まず最初に、配置変数を定義することができる。構成要素ｘについて考察する。垂直線に対応する数をｋによって表し、構成要素ｘの横座標をＸ（ｘ）によって表す。次に以下の変数を定義する。
【００６３】
構成要素ｘが横座標ｋ上にあるならば、ＩＳＸ（ｘ，ｋ）＝１であり、ｋ上にないならば、ＩＳＸ（ｘ，ｋ）＝０である。
【数１】
0004695882.tif 000002
とする。
【００６４】
明らかに、
【数２】
0004695882.tif 000003
および
【数３】
0004695882.tif 000004
が得られる。
【００６５】
シートの最初に配置される構成要素ｂと、シートの最後に配置される構成要素ｅについては、以下の制約も存在する。
【数４】
0004695882.tif 000005
【００６６】
Ｂｅｇｉｎはシートの最初に配置される構成要素の集合、Ｅｎｄはシートの最後に配置される構成要素の集合である。
【００６７】
構成要素の相対配置
次に、２つの構成要素ｘ１とｘ２について考察する。以下のように、相対位置についてのデルタ関数を定義する。
Ｘ（ｘ１）＜Ｘ（ｘ２）ならば、ｄｅｌｔａ（ｘ１，ｘ２）＝０、Ｘ（ｘ１）＞Ｘ（ｘ２）ならば、ｄｅｌｔａ（ｘ１，ｘ２）＝１
【００６８】
よって、以下が得られる。
∀ｋ  （１−ｄｅｌｔａ（ｘ１，ｘ２））≧ＩＳＸ（ｘ１，ｋ）＋（１−ＳＳ（ｘ２，ｋ））−１
∀ｋ  ｄｅｌｔａ（ｘ１，ｘ２）≧ＩＳＸ（ｘ１，ｋ）＋ＳＳ（ｘ２，ｋ−１）−１
ｘ１とｘ２が異なり、ｘ１とｘ２が接続されている場合、
∀ｋ  ＩＳＸ（ｘ１，ｋ）＋ＩＳＸ（ｘ２，ｋ）≦１
となる。
【００６９】
この最後の行は、互いに接続された２つの構成要素が同じ垂直線上に配置されないことを示している。
【００７０】
しかし、同じ垂直線上に配置された２つの構成要素を互いに接続できるようにすることもできる。構成要素の相対配置について、以下の式を定義する。
Ｘ（ｘ１）＜Ｘ（ｘ２）ならば、ｄｅｌｔａ（ｘ１，ｘ２）＝０、Ｘ（ｘ１）＞Ｘ（ｘ２）ならば、ｄｅｌｔａ（ｘ１，ｘ２）＝１
Ｘ（ｘ１）＝Ｘ（ｘ２）ならば、ｄｅｑ（ｘ１，ｘ２）＝０、Ｘ（ｘ１）≠Ｘ（ｘ２）ならば、ｄｅｑ（ｘ１，ｘ２）＝１
【００７１】
この場合（垂直接続）、以下の式を得る。
ｄｅｑ（ｘ１，ｘ２）＝ｄｅｑ（ｘ２，ｘ１）
ｄｅｌｔａ（ｘ１，ｘ２）＋ｄｅｌｔａ（ｘ２，ｘ１）＝ｄｅｑ（ｘ１，ｘ２）
∀ｋ  （１−ｄｅｌｔａ（ｘ１，ｘ２））≧ＩＳＫ（ｘ１，ｋ）＋（１−ＳＳ（ｘ２，ｋ−１））−１
∀ｋ  ｄｅｌｔａ（ｘ１，ｘ２）≧ＩＳＫ（ｘ１，ｋ）＋ＳＳ（ｘ２，ｋ−１）−１
∀ｋ  ｄｅｑ（ｘ１，ｘ２）≧ＩＳＫ（ｘ１，ｋ）−ＩＳＫ（ｘ２，ｋ）
∀ｋ  ｄｅｑ（ｘ１，ｘ２）≦ＩＳＫ（ｘ２，ｋ）−ＩＳＫ（ｘ１，ｋ）
∀ｋ  ｄｅｑ（ｘ１，ｘ２）≦２−ＩＳＫ（ｘ２，ｋ）−ＩＳＫ（ｘ１，ｋ）
上記のこれらの式は、どちらの場合でも（垂直接続であってもなくても）、対（ｘ１，ｘ２）または対（ｘ２，ｘ１）の一方についてのみ生成される。
【００７２】
向き変数
構成要素ｘの端子ｂ１について考察する。以下のように、向き関数［ｏｒｉｅｎｔ］を定義する。
ケーブルが前方に延びるならば、ｏｒｉｅｎｔ（ｂ１）＝０
ケーブルが後方に延びるならば、ｏｒｉｅｎｔ（ｂ１）＝１
【００７３】
屈曲
α）次に、端子ｂ１と端子ｂ２の間の接続線について考察する。垂直線が存在しない場合、ｂ１側での屈曲の存在は、以下の式で与えられる。
ｂｅｎｄ（ｂ１，ｂ２；ｂ１）＝｜ｏｒｉｅｎｔ（ｂ１）−ｄｅｌｔａ（ｂ１，ｂ２）｜
【００７４】
ｂ２側での屈曲の存在は、以下の式で与えられる。
ｂｅｎｄ（ｂ１，ｂ２；ｂ２）＝｜ｏｒｉｅｎｔ（ｂ２）−ｄｅｌｔａ（ｂ２，ｂ１）｜
【００７５】
この後、屈曲の位置を決定する。したがって、端子ｂ１と端子ｂ２の間の接続線が、垂直線ｋ上にｂ１側での屈曲を有するならば、以下のようになる。
屈曲が垂直線ｋ上に存在するならば、ｂｅｎｄ（ｂ１，ｂ２；ｂ１；ｋ）＝１、存在しないならば、ｂｅｎｄ（ｂ１，ｂ２；ｂ１；ｋ）＝０である。
【００７６】
したがって、垂直線ｋ上のｂ１側での屈曲と、垂直線ｋ上のｂ２側での屈曲とについて、以下の２つの式を得る。
∀ｋ  ｂｅｎｄ（ｂ１，ｂ２；ｂ１；ｋ）＝ＩＳＸ（ｂ１，ｋ）．ｂｅｎｄ（ｂ１，ｂ２；ｂ１）
∀ｋ  ｂｅｎｄ（ｂ１，ｂ２；ｂ２；ｋ）＝ＩＳＸ（ｂ２，ｋ）．ｂｅｎｄ（ｂ１，ｂ２；ｂ２）
【００７７】
上記の関数は、ｂ１側についての以下の制約を用いて実施される。
ｂｅｎｄ（ｂ１，ｂ２；ｂ１）≧ｏｒｉｅｎｔ（ｂ１）−ｄｅｌｔａ（ｂ１，ｂ２）
ｂｅｎｄ（ｂ１，ｂ２；ｂ１）≧ｄｅｌｔａ（ｂ１，ｂ２）−ｏｒｉｅｎｔ（ｂ１）
∀ｋ  ｂｅｎｄ（ｂ１，ｂ２；ｂ１；ｋ）≧ｂｅｎｄ（ｂ１，ｂ２；ｂ１）＋ＩＳＸ（ｂ１，ｋ）−１
【００７８】
ｂ２側についても同様の実施を行う。
【００７９】
β）垂直接続が計画されている場合、ｂ１側またはｂ２側での屈曲の存在は、それぞれ以下の式で与えられる。
ｂｅｎｄ（ｂ１，ｂ２；ｂ１）＝ｄｅｑ（ｂ１，ｂ２）｜ｏｒｉｅｎｔ（ｂ１）−ｄｅｌｔａ（ｂ１，ｂ２）｜
ｂｅｎｄ（ｂ１，ｂ２；ｂ２）＝ｄｅｑ（ｂ１，ｂ２）｜ｏｒｉｅｎｔ（ｂ２）−ｄｅｌｔａ（ｂ２，ｂ１）｜
【００８０】
先程と同様に、以下の式を得る。
∀ｋ  ｂｅｎｄ（ｂ１，ｂ２；ｂ１；ｋ）＝ＩＳＸ（ｂ１，ｋ）．ｂｅｎｄ（ｂ１，ｂ２；ｂ１）
（垂直線ｋ上のｂ１側での屈曲）
∀ｋ  ｂｅｎｄ（ｂ１，ｂ２；ｂ２；ｋ）＝ＩＳＸ（ｂ２，ｋ）．ｂｅｎｄ（ｂ１，ｂ２；ｂ２）
（垂直線ｋ上のｂ２側での屈曲）
【００８１】
この関数は、ｂ１側についての以下の制約を用いて実施される。
ｂｅｎｄ（ｂ１，ｂ２；ｂ１）≧ｄｅｑ（ｂ１，ｂ２）＋（ｏｒｉｅｎｔ（ｂ１）−ｄｅｌｔａ（ｂ１，ｂ２））−１
ｂｅｎｄ（ｂ１，ｂ２；ｂ１）≧ｄｅｑ（ｂ１，ｂ２）−（ｏｒｉｅｎｔ（ｂ１）−ｄｅｌｔａ（ｂ１，ｂ２））−１
∀ｋ  ｂｅｎｄ（ｂ１，ｂ２；ｂ１；ｋ）≧ｂｅｎｄ（ｂ１，ｂ２；ｂ１）＋ＩＳＸ（ｂ１，ｋ）−１
【００８２】
ｂ２側についても同様の実施を行う。
【００８３】
正しい向きの垂直接続には、２つでなければ、１つの屈曲が存在する。
【００８４】
Ｖｅｒｔｂｅｎｄ（ｂ１，ｂ２）＝（１−ｄｅｑ（ｂ１，ｂ２））（１＋｜ｏｒｉｅｎｔ（ｂ２）−ｄｅｌｔａ（ｂ２，ｂ１）｜）
は、以下の制約
Ｖｅｒｔｂｅｎｄ（ｂ１，ｂ２）≧２（１−ｄｅｑ（ｂ１，ｂ２））＋（ｏｒｉｅｎｔ（ｂ２）−ｄｅｌｔａ（ｂ２，ｂ１））−１
Ｖｅｒｔｂｅｎｄ（ｂ１，ｂ２）≧２（１−ｄｅｑ（ｂ１，ｂ２））−（ｏｒｉｅｎｔ（ｂ２）−ｄｅｌｔａ（ｂ２，ｂ１））−１
を用いて実施される。
【００８５】
上記の式は、対（ｘ１，ｘ２）または対（ｘ２，ｘ１）の一方についてのみ生成される。
【００８６】
通過点
Ｐａｓｓａｇｅ（ｘ１，ｘ２；ｋ）＝ＳＳ（ｘ１，ｋ−１）（１−ＳＳ（ｘ２，ｋ））＋ＳＳ（ｘ２，ｋ−１）（１−ＳＳ（ｘ１，ｋ））
が、
Ｐａｓｓａｇｅ（ｘ１，ｘ２；ｋ）≧ＳＳ（ｘ１，ｋ−１）＋（１−ＳＳ（ｘ２，ｋ））−１
Ｐａｓｓａｇｅ（ｘ１，ｘ２；ｋ）≧ＳＳ（ｘ２，ｋ−１）＋（１−ＳＳ（ｘ１，ｋ））−１
の形式で実施される場合、
Ｘ（ｘ１）≦ｋ−１かつＸ（ｘ２）≧ｋ＋１、またはＸ（ｘ１）≧ｋ＋１かつＸ（ｘ２）≦ｋ−１ならば、ｘ１とｘ２の間の接続に関して、垂直線ｋ上に通過点が生成される。
【００８７】
通過点は、ｘ１とｘ２が同じ垂直線上に存在するが、異なる向きを向いている場合にも生成され、
Ｖｅｒｔｐａｓｓ（ｘ１，ｘ２）＝（１−ｄｅｑ（ｘ１，ｘ２））｜ｏｒｉｅｎｔ（ｘ１）−ｏｒｉｅｎｔ（ｘ２）｜
∀ｋ  ｖｅｒｔｐａｓｓ（ｘ１，ｘ２；ｋ）＝ＩＳＸ（ｘ１，ｋ）ｖｅｒｔｐａｓｓ（ｘ１，ｘ２）
は、
ｖｅｒｔｐａｓｓ（ｘ１，ｘ２）≧（１−ｄｅｑ（ｘ１，ｘ２））＋ｏｒｉｅｎｔ（ｘ１）−ｏｒｉｅｎｔ（ｘ２））−１
ｖｅｒｔｐａｓｓ（ｘ１，ｘ２）≧（１−ｄｅｑ（ｘ１，ｘ２））−ｏｒｉｅｎｔ（ｘ１）−ｏｒｉｅｎｔ（ｘ２））−１
∀ｋ  ｖｅｒｔｐａｓｓｋ（ｘ１，ｘ２；ｋ）≧ｖｅｒｔｐａｓｓ（ｘ１，ｘ２）＋ＩＳＸ（ｘ１，ｋ）−１
の形式で実施される。
【００８８】
上記の式は、対（ｘ１，ｘ２）または対（ｘ２，ｘ１）の一方についてのみ生成される。
【００８９】
高さに関するサイズ制約
構成要素によって占有される空間的な高さについて考察する。
【００９０】
まず最初に、タイプ１の構成要素ｘについて考察する。このタイプの構成要素は、アウトレットを含むと仮定する。そのようなアウトレットをｐとする。アウトレットが右側に存在するかどうかを示す関数をＰｒ０と呼ぶ。関数Ｎｂ０は右側の端子の数を示す。
【００９１】
アウトレットｐの少なくとも１つの端子が右側に存在するならば、Ｐｒ０（ｘ，ｐ）＝１、存在しないならば、Ｐｒ０（ｘ，ｐ）＝０である。
Ｎｂ０（ｘ，ｐ）＝右側の端子の数
∀端子ｂ∈ｐ，Ｐｒ０（ｘ，ｐ）≧１−ｏｒｉｅｎｔ（ｂ）
【数５】
0004695882.tif 000006
【００９２】
左側については、
アウトレットｐの少なくとも１つの端子が左側に存在するならば、Ｐｒ１（ｘ，ｐ）＝１、存在しないならば、Ｐｒ１（ｘ，ｐ）＝０である。
Ｎｂ１（ｘ，ｐ）＝左側の端子の数
∀端子ｂ∈ｐ，Ｐｒ１（ｘ，ｐ）≧ｏｒｉｅｎｔ（ｂ）
【数６】
0004695882.tif 000007
となる。
【００９３】
Ｈ（ｘ）を構成要素ｘの高さであると見なす場合、この高さは、構成要素ｘの各辺の最大の高さである。したがって、
【数７】
0004695882.tif 000008
となる。
【００９４】
すべての構成要素、すなわち、タイプ１とは異なるタイプの構成要素についても考察し、線ｋ上のそれらの構成要素によって占められる高さを知りたい場合、以下の式を得る。
【数８】
0004695882.tif 000009
ただし、Ｅｋは垂直線ｋ上のすべての構成要素によって占められる高さであり、ｓｉｚｅ（ｘ）はタイプ１以外の構成要素ｘの高さである。
【００９５】
同様に、屈曲［Ｃ］によって占有される領域を、
【数９】
0004695882.tif 000010
のように定義し、通過点によって占有される領域を、
【数１０】
0004695882.tif 000011
のように定義する。
【００９６】
したがって、全体的な制約は、
∀Ｋ  Ｅｋ＋ＷｂｅｎｄＣｋ＋ＷｐａｓｓＰｋ≦シート高さ
のように記述される。
【００９７】
ＷｂｅｎｄおよびＷｐａｓｓは、例えば、１に設定される。
【００９８】
図に描かなければならない構成要素のタイプの関数に、さらに制約を追加することができる。これらの制約は、上で定義された式のタイプに追加しなければならない線形方程式の形式に書き換えられる。
【００９９】
この第１の操作において、構成要素の相対的な順序を、例えば、屈曲および通過点の数を制限することによって、水平方向について最適化することも可能である。したがって、垂直接続が存在しない場合、追加の制約として、以下の関数を最適化することを提案する。
【数１１】
0004695882.tif 000012
ただし、例えば、Ｃ１＝２０、Ｃ２＝１とする。
【０１００】
垂直接続が存在する場合、例えば、以下の関数を最小化する。
【数１２】
0004695882.tif 000013
ただし、例えば、Ｃ１＝２０、Ｃ２＝１とする。
【０１０１】
上で示した式および様々な制約をもつ系を解くことによって、各構成要素ｘおよびすべての垂直線ｋに関するＩＳＸ（ｘ，ｋ）関数のすべての値を決定することができる。
【０１０２】
制約を課されたこの方程式系を解くことによって、様々な構成要素ｘの向きを知ることもできる。したがって、構成要素ｘの各端子ｂに関するｏｒｉｅｎｔ（ｂ）関数の値を知ることもできる。
【０１０３】
シースに関連する後処理
この後処理ステップの目的は、シースをそれが接続される構成要素の近くに出現させることである。したがって、シース、より具体的には、シースを表すボックスを垂直線上に残し、方程式系を上述したように解くことで得た順序づけプロセス配置の制約を考慮しつつ、シースを個々に「浮動」させながら、ブロック内で動かす。したがって、先に達成された屈曲の最適化は依然として有効である。
【０１０４】
垂直線０，．．．，ＸＭＡＸは、座標Ｘ０，．．．，ＸＸＭＡＸ（整数変数）のレベルで動かされる。したがって、順序づけプロセス構成を維持するため、以下の制約
∀ｉ≦１  Ｘｉ≧Ｘｉ−１＋δｉ−１
を得る。ただし、垂直線ｉ−１がシースでない少なくとも１つの構成要素をもつならば、δｉ−１は１に等しく、もたないならば、δｉ−１は０に等しい（シース以外何も含まない垂直線には関心がない）。
【０１０５】
さらに、２本の主要垂直線の間には、何も存在しないか、またはシースが構成要素の近くにあるように見えるよう、少なくとも２本の副垂直線が存在する。（Ｘｉ−Ｘｉ−１）は、１以下、または３以上にしなければならず、２に等しくしてはならない。したがって、２進変数ＩＳＢｉを、以下の制約
Ｘｉ−Ｘｉ−１≦１＋ＩＳＢｉ．ＸＭＡＸ
Ｘｉ−Ｘｉ−１≧３−（１−ＩＳＢｉ）．ＸＭＡＸ
とともに使用する。
【０１０６】
各シースｇは、新しい座標ｘｇ（整数変数）をもつ。シースは、構成要素ｘに関して定義された配置の制約に従わなければならない。シースが関連づけられる（非シースの）すべての上流の構成要素について、ｘ０（ｇ）がこれらの構成要素の最大の座標であるならば、
ｘｇ≧Ｘｘ０（ｇ）＋１
である。
【０１０７】
同様に、シースｇが関連づけられる（非シースの）すべての下流の構成要素について、ｘ１（ｇ）がこれらの構成要素の最小の座標であるならば、
ｘｇ≦Ｘｘ１（ｇ）−１
である。
【０１０８】
シースｇが関連づけられるすべての上流のシースｇ’について、
ｘｇ≧ｘｇ’＋１
であり、すべての下流のシースについて、
ｘｇ≦ｘｇ’−１
である。
【０１０９】
シースはまた、構成要素を含む垂直線上にも配置してはならない。ｘ１（ｇ）−ｘ０（ｇ）≧２ならば、
∀ｘ  ｘ０（ｇ）＋１≦ｘ≦ｘ１（ｇ）−１    ｘｇ≦−１＋（ＸＭＡＸ＋１）．ｄｇ，ｘ
∀ｘ  ｘ０（ｇ）＋１≦ｘ≦ｘ１（ｇ）−１    ｘｇ≧１−ＸＭＡＸ（１−ｄｇ，ｘ）
でなければならず、ｄｇ，ｘは、ｘｇ＜ｘならば、０に等しく、ｘｇ＞ｘならば、１に等しい２進変数である。
【０１１０】
新しい変数ｘｍｓｈｅｅｔ（シート内の垂直線の最大数）は、以下の制約
∀ｋ  ｘｍｓｈｅｅｔ≧Ｘ（ｋ＋１）ＸＭＡＸＳＨＥＥＴ−Ｘｋ．ＸＭＡＸＳＨＥＥＴ
を用いて取り戻され、ＸＭＡＸＳＨＥＥＴは、構成要素当たりの垂直線の最大数である。
【０１１１】
シース（ｇ）がその通過点によって接続される（シースではない）すべての上流の構成要素について、ｘ’０（ｇ）はこれらの構成要素の最大座標であり、すべての下流の構成要素について、ｘ’１（ｇ）はこれらの構成要素の最大座標である。次に、
例えば、Ｋ１＝２０、Ｋ２＝１とし、関数
【数１３】
0004695882.tif 000014
を最小化する。
【０１１２】
第２の操作
第１の操作は、水平方向におけるボックスの相対順序に関するが、第２の操作は、垂直方向においてボックスを互いに対して相対的に配置する目的を有する。この垂直配置は、ボックス４を接続する接続線６どうしの交差に影響を及ぼす。この第２の操作は、一方でボックスを図の各垂直線上に配置する目的（相対レイアウト）を有し、他方で各ボックス内において端子を互いに対して配置する目的を有する。ボックスおよび端子の相対位置は、接続線６どうしの交わりの数を最小化するように選択される。
【０１１３】
端子配置の表現
同じ垂直線上に２つの縦座標ｘとｙがあるとする。第１の操作のデルタ関数に類似する関数ｄを定義する。ｄは以下のように定義される。
ｘ＜ｙならば、ｄ（ｘ，ｙ）＝０、ｘ＞ｙならば、ｄ（ｘ，ｙ）＝１
（ｘおよびｙは整数とし、ｘ＝ｙの場合は考えない）
ｘ−ｙ＝（２ｄ（ｘ，ｙ）−１）（１＋（Ｍ−１）ｕ）を得るが、
Ｍは｜ｘ−ｙ｜の上限であり、ｕは［０，１］内の連続媒介変数であり、ｄ（ｘ，ｙ）＝０ならば、（ｘ−ｙ）は［−Ｍ，−１］内にあり、ｄ（ｘ，ｙ）＝１ならば、（ｘ−ｙ）は［１，Ｍ］内にあることを表す。
【０１１４】
関数ｄ（ｘ，ｙ）には、以下に示すいくつかの制約が関連づけられる。
ｘ−ｙ−２ｄ（ｘ，ｙ）−２（Ｍ−１）ｖ−（Ｍ−１）ｕ＝−１
ｖ≦ｄ（ｘ，ｙ）（ｖはｘｙを表す）
ｖ≦ｕ
ｖ≧ｄ（ｘ，ｙ）＋ｕ−１
０≦ｕ≦１
０≦ｄ（ｘ，ｙ）≦１
０≦ｖ≦１
端子のグループ化
【０１１５】
次に、端子ｂの集合Ｂが存在し、すべてが同じ列に配置され、集合Ｂのすべての端子はグループ化しておかなければならない、所定のタイプの構成要素について考察する。この制約を書き換えるため、Ｂのすべての端子は、Ｂに属さない各端子と同じ方法で順番に配置されると考えることができる。したがって、Ｂに属さないどの端子も、Ｂに属する２つの端子の間に配置することはできない。以下の式を得る。
【数１４】
0004695882.tif 000015
ここで、（ｅ，ｑ，ｃ）は端子を表す。
【０１１６】
ｅは端子が属する構成要素に対応し、
ｑは端子が配置されることがあるアウトレットであり、
ｃはこの端子の名前である。
【０１１７】
交わりの最適化
α）水平接続どうしの交わり
（接続の方向に関して）理想的な仕方ですべての向きが定められていると考える。（ｅ，ｐ，ｂ）は横座標ｘの端子、（ｆ，ｑ，ｃ）は横座標ｘ＋１の端子、（ｅ，ｐ，ｂ）⇔（ｆ，ｑ，ｃ）について、式
【数１５】
0004695882.tif 000016
はライン（ｅ，ｐ，ｂ）⇔（ｆ，ｑ，ｃ）と交わるケーブルの数を算定する。
【数１６】
0004695882.tif 000017
を最小化しなければならない。
【０１１８】
β）垂直接続どうしの交わり
同じ垂直線上に、一方で端子ｂ１とｂ２の間の接続が存在し、他方で端子ｃ１とｃ２の間の接続が存在する場合、接続が交わるのを避けるため、
［ｄ（ｂ１，ｃ１）＋ｄ（ｂ１，ｃ２）＋ｄ（ｂ２，ｃ１）＋ｄ（ｂ２，ｃ２）］は偶数でなければならない。
【０１１９】
Ｎが０または４である場合、接続は完全に分離されている。
【０１２０】
Ｎが２である場合、一方が他方の内部に存在する。したがって、
ｄ（ｂ１，ｃ１）＋ｄ（ｂ１，ｃ２）＋ｄ（ｂ２，ｃ１）＋ｄ（ｂ２，ｃ２）＝２Ａ（ｂ１，ｂ２，ｃ１，ｃ２）＋Ｂ（ｂ１，ｂ２，ｃ１，ｃ２）
と記述され、Ａ（ｂ１，ｂ２，ｃ１，ｃ２）およびＢ（ｂ１，ｂ２，ｃ１，ｃ２）は、整数である変数として宣言される（Ａ（ｂ１，ｂ２，ｃ１，ｃ２）≦２、Ｂ（ｂ１，ｂ２，ｃ１，ｃ２）≦１、Ｂ（ｂ１，ｂ２，ｃ１，ｃ２）をコスト関数に加える）。
【０１２１】
したがって、垂直線の間の交わりの総数は、
【数１７】
0004695882.tif 000018
である。
【０１２２】
γ）垂直接続と水平接続の間の交わり
端子ｂ１とｃ２の間に垂直接続が存在し、水平接続が端子ｃ１から始まる場合、接続が交わらないように、ｄ（ｂ１，ｃ１）＝ｄ（ｂ２，ｃ１）である必要がある。
【０１２３】
したがって、｜ｄ（ｂ１，ｃ１）−ｄ（ｂ２，ｃ１）｜をコスト関数に加える。
ＩＶＨ（ｂ１，ｂ２，ｃ１）＋ｄ（ｂ１，ｃ１）−ｄ（ｂ１，ｃ２）≧０
ＩＶＨ（ｂ１，ｂ２，ｃ１）−ｄ（ｂ１，ｃ１）＋ｄ（ｂ１，ｃ２）≧０
【０１２４】
したがって、垂直線と水平線の間の交わりの総数は、
【数１８】
0004695882.tif 000019
である。
【０１２５】
δ）リモート接続および屈曲
いわゆる、「リモート」接続（ｘｆ−ｘｅ≧２）のため、媒介通過点（仮想構成要素）を生成し、上記のケースを再び参照する。
【０１２６】
向きが接続の方向と矛盾する端子の場合、（構成要素と共にグループ化される）屈曲のための仮想通過点を生成し、上記の式において、端子をこの通過点で置き換える必要がある。
【０１２７】
この場合、仮想通過点および関連する端子の個々の順序は、同じ構成要素の２つの端子どうしの接続の場合と同じ方法で取り扱わなければならない。
【０１２８】
複数ワイヤケーブルのグループ化
複数ワイヤケーブルの場合、対応するケーブルを形成する１組のワイヤをグループ化するのが好ましい。しかし、場合によっては、実行不可能リスクが存在する。もちろん、端子集合Ｂのすべての端子ｂは、並んで結合させておくのが好ましい。しかし、場合によっては、例えば、複数ワイヤケーブルの場合のように、同じ集合Ｂの２つの端子の間に端子が挿入されるのを許容することができる。例えば、それを「弱い」グループと呼ぶ。
【０１２９】
そのような場合、外部端子が集合Ｂの中に挿入される回数を数えることができ、この回数をＰｂｌｉｎｄとする。
【数１９】
0004695882.tif 000020
を得る。
【０１３０】
最適化の対象となり、交わりの数に関係するコスト関数は、ペナルティとして現れることができる。
【０１３１】
構成要素の異なるタイプの関数では、追加の制約が現れることができる。定義された構成要素のタイプの関数では、これらの制約は、上に示したような式に定式化される。
【０１３２】
コスト関数
Ｃ１ＮＨＨ＋Ｃ２ＮＶＶ＋Ｃ３ＮＶＨ＋Ｃ４Ｐｂｌｉｎｄを最小化する。
例えば、Ｃ１＝Ｃ２＝Ｃ３＝Ｃ４＝１とする。
【０１３３】
もちろん、式の形式で、別の制約を同じように実施することもできる。これは当然ながら、表現することの可能な構成要素のタイプに依存する。これらの様々な制約は、上述したコスト関数のレベルで現れることもできる。
【０１３４】
最適化の対象となる系を単純化して、２つの副系に分割することも可能である。
【０１３５】
段落「端子配置の表現」で説明した１組の式において、１対の端子（ｂ，ｂ’）は実際には、ｄ（ｅ，ｅ’）によって配置され、ｅおよびｅ’は、ｂおよびｂ’の識別「エンティティ」である。その結果、ｄ（ｅ，ｅ’）が同じになる複数の対（ｂ，ｂ’）が存在し得る。１つの対がｄ（ｅ，ｅ’）についての正式な定義を有しさえすれば十分である。したがって、使用される手順は以下のようになる。
１）表Ｔｅ，ｅ’＝｛（ｂ，ｂ’）：ｄ（ｂ，ｂ’）≡ｄ（ｅ，ｅ’）｝および表Ｂｂ，ｂ’＝｛（ｂ，ｂ’）：ｄ（ｄ，ｄ’）≡ｄ（ｅ，ｅ’）｝を設定する。
２）Ｔの各（ｅ，ｅ’）について、Ｔｅ，ｅ’の（ｂ，ｂ’）の１つ（一般には最初）およびその他のすべての制約のため、段落「端子配置の表現」で説明した１組の式を生成する。
３）コスト関数のためのこのようにして得た系を最適化する。したがって、ｄ（ｅ，ｅ’）は正しいものを得るが、高度は「あいまいな」ものを得る。
４）取得したｄ（ｅ，ｅ’）を再度読む。各対（ｂ，ｂ’）について、ｄ（ｂ，ｂ’）（すなわち、ｄ（Ｂｅ，ｅ’））が０に等しいならば、制約ｙｂ≦ｙｂ’−１を生成し、等しくないならば、ｙｂ≧ｙｂ’＋１を生成する。
５）∀ｂ，ｙｍ≧ｙｂのときのｙｂｓの最大値、および最小値であるｙｍを最小化する。
【０１３６】
第３の操作
第１および第２の操作において定義されたコスト関数の最適化によって、配線図上に表現される構成要素のすべてについての相対配置を作成することができる。したがって、この第３の操作は、同じ垂直線上に配置される構成要素のタイプに対応する行動制約を守りながら、垂直方向における構成要素の絶対配置を作成する目的を有する。
【０１３７】
構成要素の水平配置に関しては、構成要素が配置される限定された数の垂直線を提供する。したがって、グリッドピッチからの整数で構成される高度に端子を配置する。接続線のレベルでの切断の数、したがって、同じく屈曲の数を最小化するため、互いに接続される端子が同じ高度に配置されない場合の数を最小化する。
【０１３８】
制約
図１に見ることができるような構成要素の場合、対応する文字列が構成要素の下側に配置される。
構成要素ｅｋに対する文字列の高度をｔｘｔｅｋ、
構成要素ｅｋの頂部の高度をｔｏｐｅｋ、
構成要素ｅｋの底部の高度をｌｏｗｅｋと呼ぶ。
【０１３９】
以下の制約を得る。
ｔｘｔｅｋ≧ｔｏｐｅｋ−１＋Ｄｍｉｎ、Ｄｍｉｎは２つの構成要素を隔てる最小間隔である。
ｌｏｗｅｋ＝ｔｘｔｅｋ＋ｔｅｘｔｈｅｉｇｈｔ（ｅｋ）
【０１４０】
２つの端子の間に
Δ−（ｂｊ）＝ｍｉｎ（Δ−（ｂｊ，０），Δ−（ｂｊ，１））、
Δ＋（ｂｊ）＝ｍａｘ（Δ＋（ｂｊ，０），Δ＋（ｂｊ，１））
を置き、構成要素またはそれが表すボックスが引き伸ばしできるならば、
【数２０】
0004695882.tif 000021
できないならば、
【数２１】
0004695882.tif 000022
である。
【０１４１】
これは構成要素のタイプに依存し、行動仕様によって定められる。
【０１４２】
Ｄｅｌｔａｏｕｔｌｅｔの項は、ｂｊ−１が前のアウトレットの最後の端子であり、ｂｊが処理中のアウトレットの最初の端子である場合にのみ存在する。Ｄｅｌｔａｏｕｔｌｅｔの項はアウトレット間の距離である。これは構成要素のタイプに依存する。
【０１４３】
構成要素の最初の端子の場合、さらに、
【数２２】
0004695882.tif 000023
を得、Ｃは、構成要素をそのタイプの関数において定義する仕様によって定められる。
【０１４４】
構成要素の実際のドラフト（または広がり、または広さ）は、
ＤＲＡＦＴｅ＝ｔｏｐｅ−ｌｏｗｅ−ｓｉｚｅ（ｅ）
である。
【０１４５】
シートｓの内部で使用される実際の高さは、
【数２３】
0004695882.tif 000024
であり、
【数２４】
0004695882.tif 000025
は整数変数である。
【０１４６】
構成要素が引き伸ばせない（または拡大できない）場合、各アウトレットの最初の端子が整数として宣言され、引き伸ばせる場合、すべての端子が整数として宣言される。
【０１４７】
最適化
主要な基準は、切断の数である。
【０１４８】
２本の連続する垂直線上に配置され、互いに接続される端子の各接続（ｂ，ｂ’）について、Ｄ（ｂ，ｂ’）を
Ｍａｘｈｅｉｇｈｔ．Ｄ（ｂ，ｂ’）＋ｙｂ−ｙｂ’≧０
Ｍａｘｈｅｉｇｈｔ．Ｄ（ｂ，ｂ’）−ｙｂ＋ｙｂ’≧０
によって、可変２進数として定義する。
【０１４９】
したがって、切断が存在しなければ、Ｄ（ｂ，ｂ’）は０に等しく、存在すれば、１に等しい。
【０１５０】
事後に追加される第２の基準は、必要性なしに無制限に引き伸ばし（または拡大、または拡張）を行ってはならない構成要素の長さである。
【０１５１】
したがって、コスト関数は、
【数２５】
0004695882.tif 000026
である。
【０１５２】
Ｗ１は、例えば、ドラフト可能な構成要素の数とシート数の積に定められる。Ｗ２はシート数の値をもち、Ｗ３は、例えば、
【数２６】
0004695882.tif 000027
に等しい。
【０１５３】
第４の操作
この第４の最後の操作の目的は、水平線上への構成要素の絶対配置を作成することである。ここでは、より具体的には、ケーブルのルーティングおよび文字列の配置が関心の対象となる。
【０１５４】
ケーブルのルーティング
接続：
（ｙｉ，ｚｉ）を、垂直線ｔおよびｔ＋１上の接続Ｃｉにおいて接続された端子の知られている高度とする。
（ｙｊ，ｚｊ）を、垂直線ｔおよびｔ＋１上の接続Ｃｊにおいて接続された端子の知られている高度とする。
ＰｉおよびＰｊは、決定したい通過点の横座標とする。
ｉ＜ｊの場合、高度がｙｉ＜ｙｊとなるように、接続を選り分ける。
ｉ＜ｊである対｛Ｃｉ，Ｃｊ｝のすべてを検査する。
【０１５５】
基本制約は、以下のように記述される。
Ｐｉ−Ｐｊ＝Ｚｉｊ（２Ｄｉｊ−１）（１＋（Ｍ−１）Ｕｉｊ）
ただし、
Ｐｉ＜Ｐｊならば、Ｄｉｊ＝０、Ｐｉ＞Ｐｊならば、Ｄｉｊ＝１、Ｐｉ＝Ｐｊならば、問題としない。
Ｐｉ＝Ｐｊならば、Ｚｉｊ＝０、Ｐｉ≠Ｐｊならば、Ｚｉｊ＝１
【０１５６】
Ｍは、すべての可能な（ｉ，ｊ）についての｜Ｐｉ−Ｐｊ｜の可能な最大値である（事前に知られる定数である）。
【０１５７】
Ｕｉｊは、Ｄｉｊ＝０ならば、Ｐｉ−Ｐｊは［−Ｍ，−１］の範囲内にあり、Ｄｉｊ＝１ならば、［１，Ｍ］の範囲内にあり、またはＺｉｊ＝０ならば、Ｐｉ＝Ｐｊであるという事実を実施するのに使用される［０，１］の範囲の連続媒介変数である。
【０１５８】
積ＺｉｊＤｉｊは、
ＺＤｉｊ≦Ｚｉｊ
ＺＤｉｊ≦Ｄｉｊ
ＺＤｉｊ≧Ｚｉｊ＋Ｄｉｊ−１
によって実施される。
【０１５９】
同じことがＺｉｊＵｉｊにも適用され、
ＺＵｉｊ≦Ｚｉｊ
ＺＵｉｊ≦Ｕｉｊ
ＺＵｉｊ≧Ｚｉｊ＋Ｕｉｊ−１
である。
【０１６０】
積ＺｉｊＤｉｊＵｉｊは、
ＺＤＵｉｊ≦Ｚｉｊ
ＺＤＵｉｊ≦Ｄｉｊ
ＺＤＵｉｊ≦Ｕｉｊ
ＺＤＵｉｊ≧Ｚｉｊ＋Ｄｉｊ＋Ｕｉｊ−２
によって実施される。
【０１６１】
最後に全体的な制約は、
Ｐｉ−Ｐｊ＝−Ｚｉｊ＋２ＺＤｉｊ−（Ｍ−１）ＺＵｉｊ＋２（Ｍ−１）ＺＤＵｉｊ
と記述される。
【０１６２】
ｙｉ＝ｚｉの場合は、通過点は必要ない。接続Ｃｉは水平である。
【０１６３】
［ｙｉ，ｚｉ］が［ｙｊ，ｚｊ］と交わらない場合、その対｛Ｃｉ，Ｃｊ｝については何もする必要はない。
【０１６４】
［ｙｉ，ｚｉ］が［ｙｊ，ｚｊ］と交わる場合、Ｚｉｊ＝１としなければならない。通過点は、異なる点に配置されるが、そうしないと、垂直線が互いに重なり合い、垂直オーバラップが発生する。
【０１６５】
同じことがｙｊ＝ｚｊの場合にも適用される。Ｐｉ≦Ｐｊ−１の場合、水平オーバラップが発生し、すなわち、Ｄｉｊ＝１、Ｚｉｊ＝１となる。
【０１６６】
ＯＶｉｊを、接続ＣｉおよびＣｊについて水平オーバラップが発生しているかどうかを示す変数とする。
ＯＶｉｊ≧Ｄｉｊ＋Ｚｉｊ−１
である。
【０１６７】
同じことがｙｊ＝ｚｊの場合にも適用される。Ｐｊ≦Ｐｉ−１の場合、水平オーバラップが発生し、すなわち、Ｄｉｊ＝０、Ｚｉｊ＝１となる。
ＯＶｉｊ≧（１−Ｄｉｊ）＋Ｚｉｊ−１
である。
【０１６８】
また、接続ＣｉとＣｊの間の交わりを確定するため、変数ＩＮＴｉｊも決定する。
【０１６９】
接続ＣｉとＣｊが異なる方向に伸びている場合、すなわち、ｚｉ＞ｙｉかつｚｊ＜ｙｉ、またはｚｊ＜ｙｉかつｚｊ＞ｙｊである場合、どのような場合にも、交わりが存在する。
【０１７０】
ｙｉ＜ｙｊのように、２本の接続ＣｉおよびＣｊが上昇している場合、Ｄｉｊ＝０ならば、交わりが存在し、または、
ＩＮＴｉｊ＝１−Ｄｉｊ
である。
【０１７１】
ケーブルのルーティングを最適化するため、
∀Ｉ  Ｐｍａｘ＞Ｐｉ
によって定義される、Ｐｍａｘと呼ばれる最大通過点を定義する。
【０１７２】
次に、関数
【数２７】
0004695882.tif 000028
を最小化する。
【０１７３】
Ｋは定数である。
【０１７４】
ケーブル上への文字列配置の可能性の検証
レイアウトしたい文字列を各シートに配置できるかどうか、シート毎に検証する。
【０１７５】
第１の制約は、文字列を挿入するのに利用できる領域が、記入したい文字列の長さよりも大きくなければならないことである。この制約は、数学の形式で書き表すことができる。
【０１７６】
制約
これはシート毎に行われる。１つのシートに対して、
１組の文字列
【数２８】
0004695882.tif 000029
が存在し、各文字列について、一連の可能な配置範囲は、
Ｐｔ＝｛（Ｘｔ，１，Ｘ’ｔ，１），．．．，（Ｘｔ，ｎｔ，Ｘ’ｔ，ｎｔ）｝
である。
【０１７７】
さらに、各文字列は、長さがＬｔ，１，．．．，Ｌｔ，ｍｔであるｍｔ個の文字列断片から構成される。ｘｉｊは整数によって表される相対座標である。絶対配置を得るため、係数Ｆｘを各区間［ｘ，ｘ＋１］に関連づける必要があり、場合によっては、Ｆｘ＝１となる。
【０１７８】
範囲（Ｘｔ，ｉ，Ｘ’ｔ，ｉ’）の実際の長さ、すなわち、利用できる領域は、
【数２９】
0004695882.tif 000030
である。
【０１７９】
文字列Ｔｔの各断片ｍを配置するため、文字列断片が範囲ｉ上に存在すれば１に等しく、存在しなければ０に等しい、ｎｔ個の２進変数τｔ，ｍ，ｉを必要とする。
【０１８０】
したがって、Ｔｔの各断片を配置するための制約は、
【数３０】
0004695882.tif 000031
である。
【０１８１】
利用できる領域が所望の文字列を記入するのに必要な領域よりも大きいことを、
【数３１】
0004695882.tif 000032
によって示す。
【０１８２】
ｓｐａｒｅｓｐａｃｅは、例えば、使用されるフォントのサイズの関数となる所定の定数である。
【０１８３】
また、
【数３２】
0004695882.tif 000033
も得る。
【０１８４】
記入したい文字列のタイプに応じて、また所望の配置に応じて、その他の制約についても言及しなければならないかもしれない。
【０１８５】
使用したい文字列が、対応する配線図に対して大き過ぎることがあり得る。その場合、それは実現可能ではなく、問題を解決することはできない。その場合、図面の各シート上の垂直線の数を減らし、作図シートの数を増やすことによって、最初から計算をやり直すことができる。
【０１８６】
ケーブル上への文字列の配置
このステージは、第４の操作に統合することができ、または反対に、本明細書で説明する配線図のための作成プロセスからは独立して作成することもできる。全く異なる２つのアプリケーションソフトウェア、すなわち、配線図を作成するためのソフトウェアと、文字列をケーブル上の位置に設定するためのソフトウェアを提示することができる。
【０１８７】
ここで考察するシートの基本オブジェクトはワイヤと呼ばれる。シート上のすべてのワイヤは、全体としてＦで表され、ｆ∈Ｆは、ｆが与えられたシート上のワイヤであることを示し、「ｎｂｆｉｌ」は、シート上のワイヤの総数である。ワイヤｆ∈Ｆの間には、順序ｆ＜ｆ’が存在するものと考える。
【０１８８】
あるワイヤは、より複雑な、ケーブルと呼ばれる構造に属すことができる。シート上のケーブルの全体をＣで表し、ｎｂｃａｂｌｅは、シート上のケーブルの総数である。各ワイヤは、ただ１本のケーブルｃに属すことができ、ケーブルに全く属さないワイヤが存在することもある。
【０１８９】
ｘが増加する方向を向いたワイヤと、無指向的と呼ばれる戻りを有するワイヤとを区別する。指向性ワイヤに対してはｆ∈ｏという表記を、無指向性ワイヤに対してはｆ∈ｎｏという表記を用いる。
【０１９０】
ケーブルに関して２つのクラスを利用できる。第１のクラスは、タイプ１の文字列をそこに融合させることのできるケーブルを含み、第２のクラスは、タイプ１およびタイプ２の文字列を同時にそこに融合させることのできるケーブルのグループを含む。クラス１およびクラス２のケーブルをそれぞれ、ｃ∈１、ｃ∈２と表記する。
【０１９１】
セグメント
各ワイヤには、１組のセグメントが関連づけられる。
【０１９２】
ｎｂｓｅｑ（ｆ）は、ワイヤｆのセグメント数である。
【０１９３】
セグメントは、文字列用に予約された領域を構成する。ワイヤに関連づけられた各文字列は、そのワイヤのセグメントの１つに１回しか現れることができない。ワイヤの垂直部分に配置される文字列はないので、セグメントは、各ワイヤの水平部分によって定義されるサブ区間を構成する。セグメントの座標は、第４の操作の結果に基づいて決定されなければならない。その構造は、始点用、終点用ノード、およびワイヤと他のワイヤの交差によるノードが追加される屈曲用ノードの間の接続のリストによって記述されるワイヤのグラフに基づく。したがって、セグメントは、その他の様々なワイヤとの安全距離ｄを考慮しながら、グラフノード間の連続する水平部分から構成される。
【０１９４】
セグメントｓに対して、左端、右端、高さ高度を導入し、点（ｘ，ｙ）＝（ｌｅｆｔ（ｓ），ｈｉｇｈ（ｓ））と点（ｘ，ｙ）＝（ｒｉｇｈｔ（ｓ），ｈｉｇｈ（ｓ））の間の水平の直線としてｓを幾何学的に識別する。
０≦ｌｅｆｔ（ｓ）＜ｒｉｇｈｔ（ｓ）≦Ｌ
と定める。
【０１９５】
Ｌはシートの長さである。
【０１９６】
各ワイヤｆに対して極限端を導入する。
ｌｅｆｔ（ｆ）：＝ｍｉｎ．ｌｅｆｔ（ｓ），      ｒｉｇｈｔ（ｆ）：＝ｍａｘ．ｒｉｇｈｔ（ｓ）
Ｓ⊂ｆ                                          Ｓ⊂ｆ
文字列ｔ∈ｆのｘ座標について、ｌｅｆｔ（ｆ）≦ｘ≦ｒｉｇｈｔ（ｆ）でなければならない。
【０１９７】
ワイヤｆのセグメントｓの集合は、ｓ＜ｓ’という関係によって順序づけられているものとするが、これはｓがワイヤｆ上に現れる順序とは無関係とすることができる。
【０１９８】
セグメントおよびケーブル上への文字列の融合
ケーブルｃに属するワイヤｆのセグメントｓは、文字列１の融合を許容するか、許容しないかに応じて、（それぞれ１および２の）２つのカテゴリに分類しなければならない。文字列の融合を許容するセグメントｓは、対応するケーブルｃに属する２つのシースの間に必ず配置しなければならない。
【０１９９】
タイプ１の文字列の融合を許容するクラス２のケーブルに関連づけられたセグメントは、タイプ１および２の文字列の融合を許容するセグメントと同じものであると見なす。
【０２００】
文字列のタイプ
ブロックのワイヤ上に、１０の異なるタイプが区別される文字列を配置しなければならない。各ワイヤｆ上に、ｎｂｔｅｘｔ（ｆ）の異なるテキストを配置しなければならず、したがって、ｎｂｔｅｘｔ（ｆ）≦１０である。
【０２０１】
ｔ∈ｆによって、ｔ∈文字列タイプ｛１，．．．，１０｝である文字列ｔが、ワイヤｆ上に配置されることを表す。従来の規則に基づいて、文字列タイプの付番順序は、優先順に従い、すなわち、タイプ１はケーブル番号、タイプ２は尺度タイプ、タイプ３は色となる。（タイプ４、５など）他の文字列タイプについては、恣意的に、しかし重複なく取り決める。
【０２０２】
ワイヤ間の近接性の構造
コスト関数を準備するため、ワイヤ間の近接関係を定義するのに利用可能な構造がなければならない。例えば、以下の指示により整列させられたセグメントｓ⊂ｆおよびｓ’⊂ｆ’が存在する場合、ワイヤｆとｆ’は近接ワイヤであるとし、ｆ⇔ｆ’のように表記することができる。
【０２０３】
１）区間Ｉ：＝（ｌｅｆｔ（ｓ），ｒｉｇｈｔ（ｓ））と区間Ｉ’：＝（ｌｅｆｔ（ｓ’），ｒｉｇｈｔ（ｓ’））は、空でない交わりを有する。
２）セグメントｓとｓ’の間を通るワイヤがあってはならない。
３）２つのワイヤに属する少なくとも１つの文字列タイプｔ、ｔ∈ｆ、ｔ∈ｆ’が、ＩとＩ’の交わりの中にある。
４）ｈｉｇｈ（ｓ）≠ｈｉｇｈ（ｓ’）、これによって、ワイヤがそれ自体の近接ワイヤとなることを防止する。
【０２０４】
ワイヤｆの近くのワイヤｆ’の１）および２）に従って整列させられたセグメントが、文字列用の十分な領域をもたない場合、ワイヤｆは近接ワイヤをもたないことも可能である。
【０２０５】
決定変数
２つのタイプの決定変数、すなわち、実数変数と２進変数が存在する。ラテン文字（ｘおよびｅ）は実数変数を表し、ギリシャ文字（λ，ω，γ，α）は２進変数を表す（λ，ω，γ，α∈｛０，１｝）。
【０２０６】
文字列配置用の連続変数
すべてのワイヤｆ、および前記ワイヤ上に配置されるすべてのタイプの文字列ｔに対して、変数
ｘ（ｆ，ｔ）＝ワイヤｆ上の文字列ｔの中央の横座標
を導入する。
【０２０７】
したがって、自然な端
∀ｊ∈ｆ，∀ｔ∈ｆ，ｌｅｆｔ（ｊ）≦ｘ（ｆ，ｔ）≦ｒｉｇｈｔ（ｆ）
が得られる。
【０２０８】
セグメントに属する２進変数
すべてのワイヤｆ、すべてのタイプの文字列ｔ、およびすべてのセグメントｓ、ｆに対して、
文字列ｔの横座標がワイヤのセグメントｓ内にあるならば、λ（ｆ，ｔ，ｓ）＝１、ないならば、λ（ｆ，ｔ，ｓ）＝０である２進変数を考える。
【０２０９】
これらの変数の総数は、
【数３３】
0004695882.tif 000034
である。
【０２１０】
この数の推定値は、
ｎｂｆｉｌ．ｎｂｔｅｘｔ．ｎｂｓｅｇ［ｎｂｆｉｌ＝ワイヤ数］
によって与えられる。
【０２１１】
ワイヤ上の配置についての２進変数
すべてのワイヤｆ、およびすべての文字列の対ｔ１＜ｔ２に対して、
文字列ｔ１の横座標が文字列ｔ２の左側にあるならば、ω（ｆ，ｔ１，ｔ２）＝１、左側にないならば、ω（ｆ，ｔ１，ｔ２）＝０である配置についての変数を導入する。
【０２１２】
条件ｔ１＜ｔ２の下でのみ変数ω（ｆ，ｔ１，ｔ２）を導入することによって、最適化問題のための２進変数の総数を減らすことができる。
【０２１３】
ケーブル上への文字列の融合に関連する２進変数
各ケーブルに対して、
ワイヤｃ上にタイプ１の文字列を融合させるならば、γ（ｃ，１）＝１、そうでなければ、γ（ｃ，１）＝０である２進変数を導入する。
【０２１４】
第２の２進変数γ（ｃ，２）は、クラス２のケーブルｃ用に追加される。
【０２１５】
ワイヤｃ上にタイプ１およびタイプ２の文字列を同時に融合させるならば、γ（ｃ，２）＝１、そうでなければ、γ（ｃ，２）＝０である。
【０２１６】
文字列の整列に関連する２進変数
ｆ＜ｆ’であり、ｆとｆ’が近接ワイヤｆ⇔ｆ’であるようなすべてのワイヤの対（ｆ，ｆ’）、および２本のワイヤのリスト上にあるすべてのタイプの文字列ｔ、ｔ∈ｆ、ｔ∈ｆ’に対して、
文字列がワイヤｆとｆ’の間に整列させられるならば、α（ｆ，ｆ’，ｔ）＝１、そうでなければ、α（ｆ，ｆ’，ｔ）＝０である２進変数を導入する。
【０２１７】
最適化問題に対する制約
いくつかの制約が提示され、以下に示す式に定式化される。その他の制約は、定める規則に応じて考えることができる。
α）ワイヤ上に文字列が存在することの保証
【数３４】
0004695882.tif 000035
【０２１８】
どのようなワイヤｆでも、また前記ワイヤに関連づけられた文字列ｔ、ｔ∈ｆがどのようなタイプでも、文字列は、そこに配置されることが予め分かっている、前記ワイヤｆのセグメントｓの１つにただ１回だけ配置されなければならない。
【０２１９】
β）セグメント上への文字列の配置
制約の第２のクラス（Ｃ２）は、
ｔ⊂ｓであるような、∀ｆ∈Ｆ，∀ｔ∈ｆ，∀ｓ∈ｆについて、
【数３５】
0004695882.tif 000036
【数３６】
0004695882.tif 000037
の形式を有する。
【０２２０】
これら２つの制約の第１のものは、ワイヤｆの文字列ｔが前記ワイヤのセグメントｓ内にある場合、文字列ｔの左端（すなわち、ｘ（ｆ，ｔ）−ｌｏｎｇ（ｔ）／２）は、セグメントｓ自体の左端（すなわち、ｌｅｆｔ（ｓ））の右側になければならず、ｔがこのセグメント内にない場合でも、文字列の左端は、全ワイヤの少なくとも左端（すなわち、ｌｅｆｔ（ｆ））の右側にあることを示している。
【０２２１】
第２の制約は、セグメントの右端および文字列の右端について同じことを表している。
γ）同一ワイヤの異なる文字列どうしの相対配置
ワイヤの文字列の相対配置について、制約（Ｃ３）を考える。
【０２２２】
ｔ＜ｔ’かつｔ⊂ｓ，ｔ’⊂ｓであるような∀ｆ∈Ｆ，∀ｓ⊂ｆ，∀ｔ，ｔ’∈ｆについて、
（ｆ∈Ｃ，Ｃ∈２，ｔ＝１かつｔ’＝２である場合、この制約は用いない）
【数３７】
0004695882.tif 000038
【０２２３】
これら２つの制約の第１のものは、文字列ｔおよびｔ’がワイヤｆの同じセグメントｓ内にあり、ｔがｔ’の前に配置されなければならない場合、ｔの右端は、安全距離ｄを常に維持しつつ、文字列ｔ’の左端の左側になければならないことを述べている。
【０２２４】
制約（Ｃ３）は、ｃがクラス２のケーブルであり、ｆ∈ｃであり、ｔ，ｔ’ ∈ｆがタイプ１およびタイプ２の文字列である場合、取り除かなければならない。このような場合、これら２つの文字列は融合させられる傾向にあり、制約（Ｃ３）と矛盾する。この特殊な場合には、制約（Ｃ３）は、条件付きの制約で置き換えられる。
【０２２５】
導入の際、制約（Ｃ３）は非線形である。したがって、その後、それを線形にする工夫を用いる。この工夫は次のように記述することができる。
【０２２６】
β１，．．．，βｒを２進変数、ｘを既知の上限ｘ≦ｃを有する実数変数（または離散変数）とする。
１）β１＝１，．．．，βｒ＝１ならば、ｘ≦ｃ２
２）β１．．．βｒ（ｘ−ｃ２）≦０
【数３８】
0004695882.tif 000039
は等価である。
【０２２７】
以下で再び使用するこの工夫を用いて、制約（Ｃ３）は、
ｔ＜ｔ’かつｔ⊂ｓ，ｔ’⊂ｓであるような∀ｆ，∀ｓ⊂ｆ，∀ｔ，ｔ’について、
（ｆ∈ｃ，Ｃ∈２，ｔ＝１かつｔ’＝２である場合、この制約は用いない）
【数３９】
0004695882.tif 000040
と書き換えられる。
【０２２８】
δ）文字列の整列
文字列の整列は、変数α（ｆ，ｆ’，ｔ）によって管理される。これらの変数は、以下の制約（Ｃ４）を伴う。
∀ｆ，ｆ’∈Ｆ  ｆ＜ｆ’  ｆ⇔ｆ’
α（ｆ，ｆ’，ｔ）（ｘ（ｆ，ｔ）−ｘ（ｆ’，ｔ））＝０
ｔがｆとｆ’の間で整列させられる場合、その横座標は、２本のワイヤ内で同じでなければならない。
【０２２９】
（Ｃ４）のために線形形式を定める。
∀ｆ，ｆ’∈Ｆ  ｆ＜ｆ’  ｆ⇔ｆ’
ｘ（ｆ，ｔ）−ｘ（ｆ’，ｔ）≦Ｌ（１−α（ｆ，ｆ’，ｔ））
ｘ（ｆ’，ｔ）−ｘ（ｆ，ｔ）≦Ｌ（１−α（ｆ，ｆ’，ｔ））
【０２３０】
コスト関数
上述のごとく、上述した制約の関数において、文字列の配置を得るために最適化するコスト関数を決定する。
【０２３１】
先の４つの操作に関して、示された変数および制約は、本発明による手順においてどのように式を定めることができるかを示すため、例示的な実施形態として提供されている。その他の変数および対応する制約を考慮することもできる。特殊な場合の実施形態では、ここで述べた変数および制約のいくつかが無用となることも同様にあり得る。
【０２３２】
ルートおよびステッチング
ここでは、航空学の分野に特有の応用例を扱う。ルートは、ケーブルから始まり、ケーブル上に情報を提供する文字列が関連づけられる、矢印の形式で提示される。
【０２３３】
文字列の配置と同様の方法で、以下に示すように、本発明による配線図の作成プロセスに統合できる応用例を扱うが、この応用例は、前記プロセスから完全に切り離すこともできる。
【０２３４】
導入
ルートの配置は最後に行われる。天文学的な数の可能なルートが存在する。可能性の数を最小限に減らすことが絶対に必要である。ワイヤのステッチングは、有利には、ルートと同じ時に扱われる。
【０２３５】
候補ルートの決定
可能なルートは、６つの値＜ｒ，ｘ，ｙ１，ｙ２，ｄ，ｏ＞で構成されるベクトルとなる。
ｒは、ルート識別子である。
ｘは、ルートが配置される垂直線である。
ｙ１は、ルート用の文字列（および矢印の始点）の高度である。
ｙ２は、ルート用の矢印の終点の高度である。
ｄは、矢印の方向である（上／下）。
ｏは、矢印用の文字列が配置される側である（左／右）。
【０２３６】
可能なステッチングは、５つの値＜ｒ，ｘ，ｙ１，ｙ２，ｄ＞で構成されるベクトルとなる。
ｒは、ステッチング識別子である。
ｘは、ステッチングが配置される垂直線である。
ｙ１は、矢印の始点の高度である。
ステッチングの第２の線は、矢印が上向きならば下側に、下向きならば上側に存在する。
ｙ２は、ステッチング用の矢印の終点の高度である。
ｄは、矢印の方向である（上／下）。
ステッチング用の文字列は常に、矢印の中央に置かれる。
【０２３７】
予備計算
まず最初に、図に対応する（グリッド点を要素とする）行列Ｍが、
Ｍｘ，ｙ＝ＡＶＡＩＬＡＢＬＥ：文字列用またはルーティングもしくはステッチング矢印用に利用可能な点
Ｍｘ，ｙ＝＜ｒ，ｆ＞：文字列なしのケーブル（ワイヤｆ、ルートｒ）。矢印によって垂直に縦断可能な点（注：仮想通過点を含む）
Ｍｘ，ｙ＝ＵＮＡＶＡＩＬＡＢＬＥ：利用できない点（構成要素、文字列、垂直線などの内部）
を用いて計算される。
【０２３８】
可能なルートの生成
ルートの決定が、例えば、ルート毎および垂直線毎に実行される。最も頻繁に使用されるルートは配線図のデフォルトルートであるので、そのようなルートのための処理ステップは省略される。
【０２３９】
垂直線の解析
各ルートおよび各垂直線Ｘについて、垂直線の点を以下の方法で解析する。ＬＲはルート長とする。
１）ルート用の文字列を配置できる点：
左側への配置について、∀ｘ∈［Ｘ−ＬＲ，Ｘ］，Ｍｘ，ｙ＝ＡＶＡＩＬＡＢＬＥ
右側への配置について、∀ｘ∈［Ｘ，Ｘ＋ＬＲ］，Ｍｘ，ｙ＝ＡＶＡＩＬＡＢＬＥ
２）上記の条件を満たさないＡＶＡＩＬＡＢＬＥ点：ここにはルート用の文字列を配置することはできないが、これらの点は、ルートの矢印用に使用することができる。
３）ＵＮＡＶＡＩＬＡＢＬＥ点。ここには何も配置することは許されず、これらはブロッキング点となる。
４）ルートＲをもつケーブルが通過する点（すなわち、Ｍｘ，ｙ＝＜Ｒ，＊＞）
５）Ｒ以外のルートをもつケーブルが通過する点（すなわち、Ｍｘ，ｙ＝＜Ｒ’，＊＞，Ｒ’≠Ｒ）
【０２４０】
ルート選択
ルートの選択は、垂直線の解析の後で直ちに実行され、ルート／垂直線の二重ループの内部にも配置される。
【０２４１】
ＵＮＡＶＡＩＬＡＢＬＥ点は絶対停止点であるので、２つのそのような連続する点の間にあり、少なくとも１本の進行中のルートのケーブルを含む点からなるブロックは別個に取り扱う。次に、連続するブラック点をサブグループに再グループ化する（これは、同じルートをもつ隣接したケーブルの自然な分解である）。
【０２４２】
上行する候補ルート（方向＝上）：ルートは、ＡＶＡＩＬＡＢＬＥ点からのみ始まることができ、固有のルートをもつケーブルの最初のサブグループに到達する前に、別のＡＶＡＩＬＡＢＬＥ点と遭遇してはならない。実際、ルートをそれが関連づけられるケーブルから意味なく遠ざけるもっともな理由はほとんどない。
【０２４３】
最初のサブグループの前に遭遇可能なＡＶＡＩＬＡＢＬＥ点の数についてのパラメータを作成することができる。上記の手法は、このパラメータの値０に影響を及ぼすが、選択を抑制し、極端な状況では、特殊なねじれた場合に対して問題を実行不可能にすることができる。
【０２４４】
上記の条件を満たす各始点ｙについて、ｙの後に配置されるケーブルのサブグループｇ１＝＜ｙｍｉｎ１，ｙｍａｘ１＞，．．．，ｇｎ＝＜ｙｍｉｎｎ，ｙｍａｘｎ＞を考え、可能な各累積分解（ｃｕｍｕｌａｔｉｖｅ  ｆａｃｔｏｒｉｚａｔｉｏｎ）（ｙ，ｇ１），（ｙ，ｇ１，ｇ２），．．．，（ｙ，ｇ１，ｇ２），．．．，（ｙ，ｇ１，ｇ２，．．．，ｇｎ）毎に、ルートを生成する。したがって、第ｎ番目のｋのルートは、パラメータ＜Ｒ，Ｘ，ｙ，ｙｍａｘｋ，ｕｐ，ｏ＞をもち、ｏは、場合に応じて、Ｌ（左）またはＲ（右）となる。
【０２４５】
同様の方法で、垂直線を逆方向に進むことによって、下行ルート（方向＝下）を生成する。
【０２４６】
この方法で生成される潜在的な各ルート毎に、ルートが実際に存在するならば１に等しく、そうでなければ０に等しい、２進変数ＩＲＳ（Ｒ，Ｘ，ｙ，ｙ’，ｄ，ｏ）を生成する。
【０２４７】
ルート内にルートＲをもつケーブルが通過することのない点の数であるＷ（Ｒ，Ｘ，ｙ，ｙ’，ｄ，ｏ）（すなわち、無駄な点の数）と、ルートＲをもたない横切られるケーブルの数であるＴ（Ｒ，Ｘ，ｙ，ｙ’，ｄ，ｏ）を計算する。
ルート＜Ｒ，Ｘ，ｙ，ｙ’，ｄ，ｏ＞が、
Ｗ（Ｒ，Ｘ，ｙ，ｙ’，ｄ，ｏ）≧  ｍｉｎ  Ｗ（Ｒ，Ｘ，ｙ，ｙ’，ｄ，ｏ）＋Ｗｏ
Ｘ，ｙ，ｙ’，ｄ，ｏ
となり、同時に、
Ｔ（Ｒ，Ｘ，ｙ，ｙ’，ｄ，ｏ）≧  ｍｉｎ  Ｔ（Ｒ，Ｘ，ｙ，ｙ’，ｄ，ｏ）＋ｔｏ
Ｘ，ｙ，ｙ’，ｄ，ｏ
となり、例えば、Ｗ０＝８、ｔ０＝３である場合、そのルートは、例えば、無視される。
【０２４８】
Ｆｆをルートの集合とする。＜Ｒ，Ｘ，ｙ，ｙ’，ｄ，ｏ＞は、ルートｆがＲであり、サブグループ＜Ｒ，Ｘ，ｙ，ｙ’，ｄ，ｏ＞の１つの少なくとも１本のケーブルがｆであるような、すべてのＦｆに含まれる。Ｆｆはワイヤｆを含む可能なルートのリストである。
【０２４９】
Ｇｕ，ｚをルートの集合とする。＜Ｒ，Ｘ，ｙ，ｙ’，ｄ，ｏ＞は、ｚ∈［ｙ，ｙ’］であるすべてのＧｘ，ｚに含まれ、またルートの左側についてｕ∈［Ｘ−ＬＲ，Ｘ］であり、またはルートの右側についてｕ∈［Ｘ，Ｘ＋ＬＲ］であるすべてのＧｕ，ｙに含まれる。したがって、Ｇｕ，ｚは、グリッド点（ｕ，ｚ）を使用するすべての可能なルートを含む。
【０２５０】
可能なステッチングの生成および選択
ＡＶＡＩＬＡＢＬＥ点が以下のタイプ
【数４０】
0004695882.tif 000041
になることと、ステッチングの始点が２つの連続するＡＶＡＩＬＡＢＬＥ点をもたなければならないことを除いて、ルートの場合と非常に類似している。
【０２５１】
この方法で生成される潜在的な各ルート毎に、ステッチングが実際に存在するならば１に等しく、そうでなければ０に等しい、２進変数ＩＳＰ（Ｐ，Ｘ，ｙ，ｙ’，ｄ）を生成する。
【０２５２】
ｙは、ステッチング用の文字列の内部線の高度を表す。無駄な点の数であるＷＰ（Ｐ，Ｘ，ｙ，ｙ’，ｄ）と、ステッチングＰ０がのることのない横切られるケーブルの数であるＴＰ（Ｐ，Ｘ，ｙ，ｙ’，ｄ）を計算する。
【０２５３】
先の場合と同様に、ステッチング＜Ｐ，Ｘ，ｙ，ｙ’，ｄ＞が、
ＷＰ（Ｐ，Ｘ，ｙ，ｙ’，ｄ）≧３
となり、同時に、
ＴＰ（Ｐ，Ｘ，ｙ，ｙ’，ｄ）≧２
となる場合、そのステッチングは、例えば、無視される。
【０２５４】
また、ステッチングＧＰｕ，ｚの集合を生成し、＜Ｐ，Ｘ，ｙ，ｙ’，ｄ＞は、
ｄ＝ＤＯＷＮならば、ｚ∈［ｙ＋１，ｙ’］、ｄ＝ＵＰならば、ｚ∈［ｙ−１，ｙ’］
であるようなすべてのＧＰｘ，ｚに含まれ、ｕ∈［Ｘ−ＬＰ／２，Ｘ＋ＬＰ／２］であるようなすべてのＧｕ，ｙに含まれ、
ｄ＝ＤＯＷＮならば、ｕ∈［Ｘ−ＬＰ／２，Ｘ＋ＬＰ／２］であるような、すべてのＧｕ，ｙ＋１に含まれ、
ｄ＝ＵＰならば、ｕ∈［Ｘ−ＬＰ／２，Ｘ＋ＬＰ／２］であるような、すべてのＧｕ，ｙ−１に含まれ、
したがって、ＧＰｕ，ｚは、グリッド点（ｕ，ｚ）を使用するすべての可能なステッチングを含む。
【０２５５】
制約
１つ１つのワイヤは、少なくとも１回そのルートを利用しなければならず、
【数４１】
0004695882.tif 000042
となるが、好ましくは、３回より多くなく、
【数４２】
0004695882.tif 000043
となる。
【０２５６】
１つ１つのステッチングは、１回存在しなければならず、
【数４３】
0004695882.tif 000044
となる。
【０２５７】
ステッチングおよびルートは、交わってはならず、
｜Ｇｕ，ｚ｜＋｜ＧＰｕ，ｚ｜≧２である∀ｕ，ｚについて、
【数４４】
0004695882.tif 000045
となる。
【０２５８】
最適化
ルートの数は、
【数４５】
0004695882.tif 000046
となる。
【０２５９】
ルートによって横切られるケーブルの数は、
【数４６】
0004695882.tif 000047
となる。
【０２６０】
ステッチングによって横切られるケーブルの数は、
【数４７】
0004695882.tif 000048
となる。
【０２６１】
無駄な長さは、
【数４８】
0004695882.tif 000049
となる。
【０２６２】
例えば、Ｃｒ＝４，Ｃｔｒ＝５，Ｃｔｐ＝２，Ｃｇ＝２として、
ＣｒＮＲＯＵＴＥ＋ＣｔｒＮＴＲＡＶｒ＋ＣｔｐＮＴＲＡＶｐ＋ＣｇＬＧ
を最小化する。
【０２６３】
まとめ
上述の説明は、方程式系および最適化系の解法に関して知られている技法を用いてコンピュータによって解くよう提示された技術的問題を、どのように定式化するかについて当業者に示している。複数の解法技法を、上で定義したような線形方程式系に適用することができる。例えば、「分枝限界（ｂｒａｎｃｈ  ａｎｄ  ｂｏｕｎｄ）」法（またはフランス語で、いわゆる、分離および評価技法）、または「分枝切除（ｂｒａｎｃｈ  ａｎｄ  ｃｕｔ）」法（またはフランス語で、いわゆる、分離および切除技法）などがある。
【０２６４】
前記方程式系を解くことで得た解は、受け取ったデータを解釈して、図の作成を可能にする情報に変換する変換器に転送される。この情報は、「端末」、例えば、モニタ画面またはプリンタに送られ、ユーザは、最初に導入されたデータに対応する図を見ることができる。
【０２６５】
線形方程式とその解法を複数の操作において使用することによって、自動的に行われる配線図の作成の際に生じる技術的問題の解決が可能になる。実際、単一の操作によったのでは、コンピュータは、「適度な」サイズのケーブルルート用のものであっても、配線図を作成するために、制約を記述するすべての方程式を解くことはできないであろう。
【図面の簡単な説明】
【０２６６】
【図１】本発明による手順によって作成される配線図の一例を示す図である。
【図２】配線図の図構成を概略的に示す図である。
【図３】配線図の作成時に守らなければならない制約を表した表を示す図である。
【図４】配線図の作成時の最適化に関する制約を表した表を示す図である。
【図５】配線図に描かれるボックスの図構成を概略的に示す図である。
【図６】ボックスに関連する端子の図構成を概略的に示す図である。
【図７】配線図に描くことのできる一タイプの構成要素を概略的に示す図である。
【図８】配線図に描くことのできる一タイプの構成要素を概略的に示す図である。
【図９】配線図に描くことのできる一タイプの構成要素を概略的に示す図である。
【図１０】本発明による配線図の作成のための手順フローチャートを概略的に示す図である。
【図１１】図１０に概略的に示す手順を実施するように構成された手段からなる情報システムを示す図である。
【符号の説明】
【０２６７】
２  中立域
４  ボックス
６  ライン
８  アウトレット
１０  シート
１２  相互参照
１４  注記
ＷＤ  配線図
【図１】
0004695882.tif 000050
【図２】
0004695882.tif 000051
【図３】
0004695882.tif 000052
【図４】
0004695882.tif 000053
【図５】
0004695882.tif 000054
【図６】
0004695882.tif 000055
【図７】
0004695882.tif 000056
【図８】
0004695882.tif 000057
【図９】
0004695882.tif 000058
【図１０】
0004695882.tif 000059
【図１１】
0004695882.tif 000060