Cookies Policy
We use cookies to improve our site and your experience. By continuing to browse our site you accept our cookie policy. Find out More
Close
  • Menu
Publications

Publications by CEGI

2019

A co-evolutionary matheuristic for the car rental capacity-pricing stochastic problem

Authors
Oliveira, BB; Carravilla, MA; Oliveira, JF; Costa, AM;

Publication
European Journal of Operational Research

Abstract

2019

Data mining based framework to assess solution quality for the rectangular 2D strip-packing problem

Authors
Júnior, AN; Silva, E; Gomes, AM; Soares, C; Oliveira, JF;

Publication
Expert Syst. Appl.

Abstract

2019

Data mining based framework to assess solution quality for the rectangular 2D strip-packing problem

Authors
Neuenfeldt Junior, A; Silva, E; Gomes, M; Soares, C; Oliveira, JF;

Publication
Expert Systems with Applications

Abstract
In this paper, we explore the use of reference values (predictors) for the optimal objective function value of hard combinatorial optimization problems, instead of bounds, obtained by data mining techniques, and that may be used to assess the quality of heuristic solutions for the problem. With this purpose, we resort to the rectangular two-dimensional strip-packing problem (2D-SPP), which can be found in many industrial contexts. Mostly this problem is solved by heuristic methods, which provide good solutions. However, heuristic approaches do not guarantee optimality, and lower bounds are generally used to give information on the solution quality, in particular, the area lower bound. But this bound has a severe accuracy problem. Therefore, we propose a data mining-based framework capable of assessing the quality of heuristic solutions for the 2D-SPP. A regression model was fitted by comparing the strip height solutions obtained with the bottom-left-fill heuristic and 19 predictors provided by problem characteristics. Random forest was selected as the data mining technique with the best level of generalisation for the problem, and 30,000 problem instances were generated to represent different 2D-SPP variations found in real-world applications. Height predictions for new problem instances can be found in the regression model fitted. In the computational experimentation, we demonstrate that the data mining-based framework proposed is consistent, opening the doors for its application to finding predictions for other combinatorial optimisation problems, in particular, other cutting and packing problems. However, how to use a reference value instead of a bound, has still a large room for discussion and innovative ideas. Some directions for the use of reference values as a stopping criterion in search algorithms are also provided. © 2018 Elsevier Ltd

2019

A Benders Decomposition Algorithm for the Berth Allocation Problem

Authors
Barbosa, F; Oliveira, JF; Carravilla, MA; Curcio, EF;

Publication
Springer Proceedings in Mathematics and Statistics

Abstract
In this paper we present a Benders decomposition approach for the Berth Allocation Problem (BAP). Benders decomposition is a cutting plane method that has been widely used for solving large-scale mixed integer linear optimization problems. On the other hand, the Berth Allocation Problem is a NP-hard and large-scale problem that has been gaining relevance both from the practical and scientific points of view. In this work we address the discrete and dynamic version of the problem, and develop a new decomposition approach and apply it to a reformulation of the BAP based on the Heterogeneous Vehicle Routing Problem with Time Windows (HVRPTW) model. In a discrete and dynamic BAP each berth can moor one vessel at a time, and the vessels are not all available to moor at the beginning of the planning horizon (there is an availability time window). Computational tests are run to compare the proposed Benders Decomposition with a state-of-the-art commercial solver. © 2019, Springer Nature Switzerland AG.

2019

Exact approaches for the cutting path determination problem

Authors
Silva, EF; Oliveira, LT; Oliveira, JF; Bragion Toledo, FMB;

Publication
COMPUTERS & OPERATIONS RESEARCH

Abstract
Cutting phases occur in many production processes when a larger object must be cut into multiple smaller pieces. Some examples of relevant industries being clothing, footwear, metalware and furniture. The cutting phase is composed of two stages. The first stage consists of finding a good layout for the set of small pieces that must be cut from the larger object and minimizing some objective such as raw-material waste (The Cutting and Packing Problem). Once this good layout has been established, it is provided as input for the second stage which consists of determining the path to cut the pieces which minimizes another objective, such as the total cutting time or distance (The Cutting Path Determination Problem). This second stage is crucial for efficient production planning. Only one linear mathematical model has previously been proposed for the Cutting Path Determination Problem. In this paper, this problem is addressed using two exact approaches based on the Rural Postman Problem (RPP) and the Traveling Salesman Problem (TSP). The RPP approach, in particular, is able to produce optimal solutions for instances containing more than 2000 edges in under 1 h.

2019

Optimality in nesting problems: New constraint programming models and a new global constraint for non-overlap

Authors
Cherri, LH; Carravilla, MA; Ribeiro, C; Toledo, FMB;

Publication
Operations Research Perspectives

Abstract
In two-dimensional nesting problems (irregular packing problems) small pieces with irregular shapes must be packed in large objects. A small number of exact methods have been proposed to solve nesting problems, typically focusing on a single problem variant, the strip packing problem. There are however several other variants of the nesting problem which were identified in the literature and are very relevant in the industry. In this paper, constraint programming (CP) is used to model and solve all the variants of irregular cutting and packing problems proposed in the literature. Three approaches, which differ in the representation of the variable domains, in the way they deal with the core constraints and in the objective functions, are the basis for the three models proposed for each variant of the problem. The non-overlap among pieces, which must be enforced for all the problem variants, is guaranteed through the new global constraint NoOverlap in one of the proposed approaches. Taking the benchmark instances for the strip-packing problem, new instances were generated for each problem variant. Extensive computational experiments were run with these problem instances from the literature to evaluate the performance of each approach applied to each problem variant. The models based on the global constraint NoOverlap performed consistently better for all variants due to the increased propagation and to the low memory usage. The performance of the CP model for the strip packing problem with the global constraint NoOverlap was then compared with the Dotted Board with Rotations using larger instances from the literature. The experiments show that the CP model with global constraint NoOverlap can quickly find good quality solutions in shorter computational times even for large instances. © 2019

  • 1
  • 106