文献

J-GLOBAL ID：201702260042358515   整理番号：17A1095628

2次元Disjunctively制約付きナップサック問題:ヒューリスティックと厳密なアプローチ【Powered by NICT】

Two-dimensional Disjunctively Constrained Knapsack Problem: Heuristic and exact approaches

著者 (4件)： de Queiroz Thiago Alves (Institute of Mathematics and Technology, IMTec, UFG/RC, 75704-020 Catalao, GO, Brazil) ,  Hokama Pedro Henrique Del Bianco (Institute of Computing, IC, UNICAMP, 13084-971 Campinas, SP, Brazil) ,  Schouery Rafael Crivellari Saliba (Institute of Computing, IC, UNICAMP, 13084-971 Campinas, SP, Brazil) ,  Miyazawa Flavio Keidi (Institute of Computing, IC, UNICAMP, 13084-971 Campinas, SP, Brazil)
資料名： Computers & Industrial Engineering  (Computers & Industrial Engineering)
巻： 105  ページ： 313-328  発行年： 2017年 
JST資料番号： D0502B  ISSN： 0360-8352  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： イギリス (GBR)  言語： 英語 (EN)

抄録/ポイント： 本研究では,コンフリクトグラフを考慮した二次元版,このグラフにおける各エッジを一緒に充填してはいけないことを項目の対を表す)における0 1ナップサック問題を扱った。この問題は,ビンパッキング問題の部分問題として,サプライチェーンシナリオに発生する。分枝切除アルゴリズムで解かれることをいくつかの整数計画法定式化を提案した。定式化はこの問題の一次元および二次元バージョンを混合配置変数に基づいている。候補解が見出される場合,制約プログラミングアルゴリズム,二次元パッキング制約条件を満たすかどうかを検証を実施した実現可能性試験。さらに,限界と有効カットも研究した。反復解を生成し,タブー探索とシミュレーテッドアニーリングアプローチの成分を持つことを発見的方法を提案した。結果は,項目の完全な出荷を考慮するために拡張し,項目のサブセットは,すべての負荷または完全に除外しなければならない。この制約は多くの現実のパッキング問題,機械の充填部品など,異なる顧客へのカーゴを送達する時に適用した。文献から誘導したいくつかの例での実験で,このアルゴリズムの競争力,事例の99%を解決した短い計算時間を要する最適性を示した。Copyright 2017 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： 制約プログラミング ,  グラフ ,  パッキング問題 ,  整数計画法 ,  *二次元 ,  タブー探索 ,  ビンパッキング問題 ,  定式化 ,  *ナップサック問題 ,  発見的方法 ,  CPU時間 ,  部分集合 ,  アルゴリズム
準シソーラス用語： 部分問題 ,  *ヒューリスティック , 【Automatic Indexing@JST】

著者キーワード (6件)： 2次元0 1ナップサック問題 ,  コンフリクトグラフ ,  選言的制約 ,  完全出荷 ,  整数計画法 ,  タブー探索

分類 (3件)： 数理計画法  (KA03030M) ,  工程管理  (KB03030P) ,  その他のオペレーションズリサーチの手法  (KA03070E)

タイトルに関連する用語 (4件)： 2次元 ,  制約 ,  ナップサック問題 ,  ヒューリスティック