5B2 AN ITERATED LOCAL SEARCH ALGORITHM BASED ON NONLINEAR PROGRAMMING FOR THE IRREGULAR STRIP PACKING PROBLEM(Technical session 5B: Packing problem)
スポンサーリンク
概要
- 論文の詳細を見る
The irregular strip packing problem is a combinatorial optimization problem that asks to place a set of 2-dimensional polygons within a rectangular container so that no two polygons overlap each other and no polygon protrudes from the container, where each polygon is not necessarily convex. The container has a fixed width, while its length can change so that all polygons are placed in it. The objective is to find a layout that minimizes the length of the container. This problem has many applications in material industry such as paper and textile industries, where raw materials are usually given in rolls. We propose a new separation algorithm based on nonlinear programming, and an algorithm that swaps two polygons in a sophisticated way ; it tries to find their positions with the least overlap. We incorporate these algorithms as components in an iterated local search algorithm for the overlap minimization problem and then develop an algorithm for the irregular strip packing problem using the iterated local search algorithm. Computational comparisons on representative instances disclose that our algorithm is competitive with other existing algorithms. Moreover, our algorithm updates several best known results.
- 一般社団法人日本機械学会の論文
- 2006-07-18
著者
-
NAGAMOCHI Hiroshi
Department of Applied Mathematics and Physics, Kyoto University
-
Yagiura Mutsunori
Department of Computer Science and Mathematical Informatics, Nagoya University
-
Nagamochi Hiroshi
Department Of Applied Mathematics And Physics Kyoto University
-
IMAMICHI Takashi
Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University
-
Imamichi Takashi
Department Of Applied Mathematics And Physics Graduate School Of Informatics Kyoto University
-
Imamichi Takashi
Department Of Applied Mathematics And Physics Kyoto University
-
Yagiura Mutsunori
Department Of Computer Science And Mathematical Informatics Nagoya University
-
Yagiura Mutsunori
Department Of Applied Mathematics And Physics Graduate School Of Informatics Kyoto University
-
Nagamochi Hiroshi
Department Of Applied Mathematics And Physics Graduate School Of Engineering Kyoto University
関連論文
- Optimization Problems and Algorithms in Double-layered Food Packing Systems
- 局所探索法とその拡張 : タブー探索法を中心として
- A Set Covering Approach for the Pickup and Delivery Problem with Additional Constraints (Numerical Optimization methods, theory and applications)
- 多制約配送計画問題に対する集合被覆アプローチ
- 分枝限定法 : さらなる計算効率の希求(堅く柔らかく…数理計画アプローチ再訪)
- 2-A-3 MAX-2-SATに対する分枝限定法の改良(離散最適化(3))
- 1-A-5 矩形パッキング問題に対する厳密解法(離散最適化(2))
- 矩形パッキング問題に対する厳密解法
- MAX-2-SATに対する分枝限定法(組合せ最適化(4))
- CONSTRUCTING CACTUS REPRESENTATION FOR ALL MINIMUM CUTS IN AN UNDIRECTED NETWORK
- Generation of Symmetric and Asymmetric Biconnected Rooted Outerplanar Graphs
- Generation of Symmetric and Asymmetric Biconnected Rooted Triangulated Planar Graphs
- 1A1 COMBINATORIAL OPTIMIZATION PROBLEMS AND ALGORITHMS IN DOUBLE-LAYERED FOOD PACKING EQUIPMENTS
- MAX-2-SATに対する分枝限定法
- ルール生成に必要なデータ量に関するランダム性に基づいた解析
- 1-D-1 ルール生成に必要なデータ量に関するランダム性に基づいた解析(マーケティング(1))
- 6B2 AN ITERATED LOCAL SEARCH ALGORITHM FOR THE MULTI-RESOURCE GENERALIZED ASSIGNMENT PROBLEM WITH FLEXIBLE ASSIGNMENT COST(Technical session 6B: General model for scheduling and assignment problem)
- 5B1 A GUIDED LOCAL SEARCH ALGORITHM BASED ON A FAST NEIGHBORHOOD SEARCH FOR THE IRREGULAR STRIP PACKING PROBLEM(Technical session 5B: Packing problem)
- オプションプライシングと凸計画問題の関係について(金融工学(3))
- 長方形詰込み問題に対する可変近傍探索法(組合せ最適化(4))
- 移動時間コスト関数を考慮した時間枠つき配送計画問題に対する局所探索法 (数理最適化から見た「凸性の深み,非凸性の魅惑」)
- Constructing a Cactus for Minimum Cuts of a Graph in ★(mn+n^2logn) Time and ★(m) Space (Special Issue on Selected Papers from LA Symposium)
- 点容量付き内向木詰込問題の計算複雑度
- A Clustering Method for Analysis of Sequence Similarity Networks of Proteins Using Maximal Components of Graphs
- Computing a Minimum Cut in a Graph with Dynamic Edges Incident to a Designated Vertex(Graph Algorithms,Foundations of Computer Science)
- A Simple Proof of a Minimum Cut Algorithm and Its Applications
- Approximating a Generalization of Metric TSP(Graph Algorithms,Foundations of Computer Science)
- Approximation to the Minimum Cost Edge Installation Problem
- A Randomness Based Analysis on the Data Size Needed for Removing Deceptive Patterns
- BI-CRITERIA FOOD PACKING BY DYNAMIC PROGRAMMING(the 50th Anniversary of the Operations Research Society of Japan)
- APPROXIMATING MINIMUM COST MULTIGRAPHS OF SPECIFIED EDGE-CONNECTIVITY UNDER DEGREE BOUNDS(the 50th Anniversary of the Operations Research Society of Japan)
- Performance Analysis of a Collision Detection Algorithm of Spheres Based on Slab Partitioning
- 4C1 SCHEDULING MULTIPROCESSOR TASKS WITH PROMPT SERVICE CONSTRAINTS ON ALIGNED IDENTICAL PROCESSORS
- Worst Case Analysis for Pickup and Delivery Problems with Transfer
- 4A1 A LOCAL SEARCH ALGORITHM FOR ROUTING AND SCHEDULING PROBLEMS WITH TIME WINDOW AND TRAVELING TIME CONSTRAINTS(Technical session 4A : Vehicle routing)
- Orthogonal Drawings for Plane Graphs with Specified Face Areas(Theory of Computer Science and Its Applications)
- 1A2 AN IMPROVED APPROXIMATION ALGORITHM FOR CAPACITATED MULTICAST ROUTINGS IN NETWORKS(Technical session 1A: Combinatorial optimization)
- 5B2 AN ITERATED LOCAL SEARCH ALGORITHM BASED ON NONLINEAR PROGRAMMING FOR THE IRREGULAR STRIP PACKING PROBLEM(Technical session 5B: Packing problem)
- 2B1 A DP-BASED HEURISTIC ALGORITHM FOR THE DISCRETE SPLIT DELIVERY VEHICLE ROUTING PROBLEM(Technical session 2B: Vehicle scheduling and communication)
- A Fast Edge-Splitting Algorithm in Edge-Weighted Graphs(Discrete Mathematics and Its Applications)
- A Note on Approximating the Survivable Network Design Problem in Hypergraphs(Special Issue on Selected Papers from LA Symposium)
- Approximation Algorithms for Multicast Routings in a Network with Multi-Sources(Discrete Mathematics and Its Applications)
- An LP-Based Local Search to the One Dimensional Cutting Stock Problem Using a Given Number of Cutting Patterns
- A Fast Algorithm for Cactus Representations of Minimum Cuts
- Solving the Single-Vehicle Scheduling Problems for All Home Locations under Depth-First Routing on a Tree (Special Section on Discrete Mathematics and Its Applications)
- VEHICLE SCHEDULING ON A TREE TO MINIMIZE MAXIMUM LATENESS
- Approximability of the Minimum Maximal Matching Problem in Planar Graphs(Graphs and Networks)
- An Approximation of the Minimum Vertex Cover in a Graph
- Approximating the Minmax Rooted-Subtree Cover Problem(Graphs and Networks)
- A Clustering Method for Analysis of Sequence Similarity Networks of Proteins Using Maximal Components of Graphs
- A Clustering Method for Analysis of Sequence Similarity Networks of Proteins Using Maximal Components of Graphs
- Heuristic Algorithms for Rectilinear Block Packing (アルゴリズムと計算理論の新展開 : RIMS研究集会報告集)
- A Dynamic Programming Based Improvement Heuristic for a Repetitive Routing Problem of Grasp-and-Delivery Robots
- 1-D-4 Heuristics for the Rectilinear Block Packing Problem
- 一般化上界制約付き集合多重被覆問題に対する発見的解法 (最適化手法の理論と応用の繋がり)
- 3次元箱詰め問題に対する構築型解法の効率的実現法
- 2-A-9 一般化上界制約付き集合多重被覆問題に対する発見的解法(特別セッション スモールビジネスOR(1))
- 汎用ソルバーによる研究集会開催日程スケジューリングの自動化(論文・事例研究)
- 2-A-5 最適化アルゴリズムを実装する際の留意点について : 組合せ最適化問題に対するメタヒューリスティクスの場合を中心として(特別セッション 最適化の実装技術)
- Better Approximation Algorithms for Grasp-and-Delivery Robot Routing Problems
- RA-005 3次元パッキング問題に対するbest-fit法の効率的実現法(アルゴリズム・コンピュテーション(3),A分野:モデル・アルゴリズム・プログラミング)
- 4A2 NETWORK TRANSFORMATION HEURISTICS FOR MULTI-STORY STORAGE RACK PROBLEMS(Technical session 4A: Material handling system)
- 5B1 IMPROVED IMPLEMENTATION OF AN APPROXIMATION ALGORITHM WITH FACTOR TWO FOR A CYCLIC ROUTING PROBLEM OF GRASP-AND-DELIVERY ROBOTS(Technical session 5B: Routing problems)
- 5B3 APPROXIMATING CYCLIC ROUTING PROBLEMS OF GRASP-AND-DELIVERY ROBOTS IN PRODUCTION OF PRINTED CIRCUIT BOARDS(Technical session 5B: Routing problems)
- 頂点容量制約付き有向全域木パッキング問題に対するラグランジュ緩和に基づく列生成法
- Scheduling Capacitated One-Way Vehicles on Paths with Deadlines
- A DP-based Heuristic Algorithm for the Discrete Split Delivery Vehicle Routing Problem