1980年ごろ、CAD=GDS1のユーザ言語GPL1(APL)で擬似的にTSPを解いてCAM(マウンター）で使用した話

１）CAD=CDS1の時代のユーザ要求：電子部品マウンターを効率よく使いたい

電子部品のマウンターとは、プリント基盤に電子部品を自動的に装着する機械です。古賀電子のyoutubeに動画が有りました。これは表面実装ですが、当時は穴に部品を刺すタイプで大きな機械でした。

CAD=GDS1でPCB設計し部品をマウンター用のNCデータにして(=CAM)出力するのですが、装着順序を最適化してマウント時間を短くしたいとの要望がありました。

たとえば１０万台のオーディオプレイヤーを作る場合、１枚のPCB基盤で１０秒遅いと製造時間が１２日(=10万x10秒/(3600秒x24))伸びる事になります。

なのでCAD出力時に効率の良い順序（＝経路）でNCデータを作るのが要求でした。「上司からは全ての経路で一番短い経路を求めれば良いので、簡単だろう」とは言われませんでしたが似た様な軽い要求でした。

部品種類は１００種類程度で、トータル部品数は200点程度です。全ての経路は２００の階乗になるので天文学的数字です。２０の階乗でも全ての経路を求めるのは非現実的になります。

例１）5!=5×4×3×2×1=1205
例２）10!=10×9×8×7×6×5×4×3×2×1=3,628,800
例３）20!=2,432,902,008,176,640,000

この様な問題をTSP(=巡回セールスマン問題）と言う数学で有名な問題です＝量子コンピュータなら最適解が瞬時に求まると思われますが、ノイマン型コンピュータでは膨大な時間がかかる問題です。

２）最適な経路作成はできないが「ほどほどに良い経路」はできる

経路は沢山ありますが最悪に近い経路がX％、最適に近い経路がX%とするとX%でも相当な数があるはずですから、適当に経路を決めて改善していけば良い経路が作成できる…との考えて、CAD=GDS1のユーザ言語GPL1でマウンター用のTSPSORTを作成しました。当時のプログラムは無いし今見てもAPLなので何しているか理解不能なので、調べてそれに似ている記事を見つけたので参考にして、pythonで以下の経路図を作成しました。

参考にしたサイト「巡回セールスマン問題(TSP)のアルゴリズムを極めた話」：2020年の記事で40年以上前に同じ様な事をして居た事になります。

そこそこ良い例＝10519〜9276 ：貪欲法・クラスカル法などで近くの点を繋げていく方法で経路を求めた例。
　最悪/そこそこ＝43127/9276=4.65倍良くなった。

最適に近い例=8970~8374　：「一筆書き」になるように改善を繰り返した例。
最悪/最適に近い＝43127/8374=5.15倍良くなった。

距離の変化グラフ全体です。近くの点を繋げていくなどの単純なアルゴリズムでも経路は格段に良くなり、その後は少しづつ改善されていきます…が、改善率は徐々に小さくなっていきます。

３）TSPSORTのアルゴリズム

全体フローは「初期経路」「一筆書き」「改善」になります。

3-1)初期経路を作成する

近い点を繋いでいく事を繰り返して、全部の点を繋ぐ(始終点も繋ぐ）。この結果最悪に近い経路ではなくそこそこの経路はできる。

３−２）「クロス」を取り除き「一筆書き」する

３−3）その他の改善

いろんな人が今も改善方法を考えてる様です。参考に面白そうなサイトを以下に載せておきます。

以下は2022年の記事です。

巡回セールスマン問題をいろんな近似解法で解く（その1: 総当たり法とグリーディ法）
巡回セールスマン問題をいろんな近似解法で解く（その2: 局所探索法と2-opt近傍）
巡回セールスマン問題をいろんな近似解法で解く（その3: ランダム化最近近傍法とGRASP法）
巡回セールスマン問題をいろんな近似解法で解く（その4: 反復局所探索法）
巡回セールスマン問題をいろんな近似解法で解く（その5: 焼きなまし法）
巡回セールスマン問題をいろんな近似解法で解く（その6: さまざまな近傍）

4)現実的なマウンター用TSPSORT

TSPの改善状況を見ると例では最適経路でも8000以下にはなりそうもありません。色々な改善方法は時間が有れば試せば良いと思いますが「一筆書き(=8970)」経路にするだけでも「実用十分」な場合があります。

実際のマウンターでは部品カセットの並びや、始終点はマウンター原点近くが良い…なども考慮する必要があり、単純なTSPだけでは有りませんので、時間が許す範囲でパラメータを弄りながらトータル時間が短くなる様なヒューリスティック探索になります。

まあ「大体よければ全て良し」の精神で、当時はTSPSORTを作って居ました。3-3)の様な資料や文献は皆無の古い時代の話で、「計算複雑性理論」や「NP困難」と言う言葉を初めて知った時でした。以後は１００％は狙わず、８０〜９０％でも「早く作って」「実際の業務に役立てる」様な事を重要視して行ったと思います（＝１００％目指すのは趣味の範囲で工学は役に立てば良い＝量子コンピュータが実用化されたら１００％狙います）

５）TSPSORTのその後

マウンター以外では、タンクローリのガソリンスタンド回り問題が有りました。タンクローリーは長いのでガソリンスタンドへの侵入口に制限が有ったり、道路幅や通行規制を考慮して経路を決める必要が有りました（＝距離だけでは無く、通行規制が入ると本当に大変す）。

今後GeoDiveExaでは効率的な調査経路作成にTSPSORTは利用できそうです。

今Amazonで検索したら以下の様な本がありました。興味がある人は見てみてください。ノイマン型コンピュータの限界と量子コンピュータへの期待が出てくるかも知れません。