An Exact Algorithm for the Two-Dimensional Orthogonal Packing Problem with Unloading Constraints

• 成果类型: Article
• 署名作者: Cote, Jean-Francois; Gendreau, Michel; Potvin, Jean-Yves
• 署名单位: Laval University; Universite de Montreal; Laval University; Universite de Montreal; Polytechnique Montreal; Universite de Montreal; Universite de Montreal
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2014.1307
• 发表日期: 2014
• 页码: 1126-1141
• 关键词: vehicle-routing problem; combinatorial benders cuts; loading constraints; tabu search; lp bounds

摘要

This paper describes an exact algorithm for solving a two-dimensional orthogonal packing problem with unloading constraints, which occurs as a subproblem of mixed vehicle routing and loading problems. The packing considered in this work is basically a feasibility problem involving a single bin. The problem is addressed through a decomposition approach wherein a branch-and-cut algorithm is designed for solving a one-dimensional relaxation of the original problem. When an integer solution is found in the branching tree, a subsidiary problem is solved to identify a two-dimensional packing that does not lead to any overlap and satisfies the unloading constraints. Cuts are added when the subsidiary problem proves to be infeasible. Several preprocessing techniques aimed at reducing the size of the solution space and uncovering infeasibility are also described. A numerical comparison with the best known exact method is reported at the end based on benchmark instances.