プリント基板検査経路最適化問題に対する分枝カット法に基づく解法

カテゴリ: 研究会(論文単位)

論文No: IS18026

グループ名: 【C】電子・情報・システム部門 情報システム研究会

発行日: 2018/05/27

タイトル(英語): A solution algorithm based on a branch and cut method for a route-length minimization problem in PCB inspection

著者名: 片桐 英樹(神奈川大学),宇野 剛史(徳島大学)

著者名(英語): Hideki Katagiri(Kanagawa University),Takeshi Uno(Tokushima University)

キーワード: 分枝カット法|プリント基板|検査経路最適化|妥当不等式|巡回セールスマン問題|branch-and-cut method|printed circuit board|inspection route optimization|valid inequality|traveling salesman problem

要約(日本語): 本研究では，複数台カメラによるアライメント撮像を行う検査機でプリント基板を検査する状況において，検査の経路長を最小化する問題の厳密最適解を分枝カット法により求解するアルゴリズムを提案する．問題が一般化集荷配達巡回セールスマン問題として定式化できることを示した後，いくつかの妥当不等式及び分枝カット法に基づくアルゴリズムを提案する．現場の実データを用いた数値実験を行い，提案手法の有用性を検討する．

要約(英語): This study proposes a branch-and-cut method for solving a route-length minimization problem in PCB inspection via multiple cameras. The problem is formulated as a generalized pickup and delivery traveling salesman problem. Some valid inequalities to the formulated problem is proposed. Some numerical experiments using real data are conducted to show the effectiveness of the proposed algorithm.

原稿種別: 日本語

PDFファイルサイズ: 1,229 Kバイト