CEGI - Indexed Articles in Journals

Permanent URI for this collection


Recent Submissions

Now showing 1 - 5 of 213
  • Item
    Data mining based framework to assess solution quality for the rectangular 2D strip-packing problem
    ( 2019) Alvaro Luiz Júnior ; José Fernando Oliveira ; Carlos Manuel Soares ; António Miguel Gomes ; Elsa Marília Silva ; 5001 ; 265 ; 5675 ; 6300 ; 1249
    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
  • Item
    Load balance recovery for multi-drop distribution problems: A mixed integer linear programming approach
    ( 2018) Elsa Marília Silva ; António Galrão Ramos ; José Fernando Oliveira ; 5675 ; 5899 ; 265
    In road freight transport, a loaded vehicle with a distribution route and a compliant load balance at the depot can become non-compliant during the route, since the total weight of the cargo and its centre of gravity change with each delivery. Nowadays, vehicles circulating on our roads either undermine safety regulations or lack operational efficiency when these regulations are taken into account and cargo is extensively rearranged after each delivery. This issue has been completely ignored both in the vehicle routing literature and in the container loading literature. The aim of this work is to provide tools capable of ensuring that a cargo arrangement is load balanced along the complete distribution trip. It proposes a multi-drop load balance recovery algorithm (MDLBRA), which seeks to ensure that, when both a complete route and the respective cargo arrangement are provided, the boxes to be removed from the cargo arrangement at the depot and the boxes to be rearranged at each customer are identified, allowing the cargo to remain balanced after every delivery. It is important to notice that a MDLBRA is not a container loading algorithm: a MDLBRA modifies solutions generated by any container loading algorithm so that load balance is guaranteed when the truck leaves the depot and during the entire distribution route. A mixed integer linear programming (MILP) model is proposed to balance the cargo at each customer stop. The MILP model incorporates load distribution diagram constraints in order to determine the feasible domain for the location of the centre of gravity of the cargo arrangement, taking into account the regulatory requirements and the technical characteristics of the vehicle. Extensive computational experiments show that a MDLBRA can be used in practical contexts, as the MILP model was able to find a solution in less than ten minutes in 93% of the unbalanced test instances. © 2018 Elsevier Ltd
  • Item
    Solving the grocery backroom layout problem
    ( 2020) Elsa Marília Silva ; Pires,M ; Pedro Amorim ; 5964 ; 5675
  • Item
    The time window assignment vehicle routing problem with product dependent deliveries
    ( 2018) Fábio Silva Moreira ; Bernardo Almada-Lobo ; Pedro Amorim ; Luís Guimarães ; da Silva,DP ; 5964 ; 5428 ; 6114 ; 5965
  • Item
    Solving a large multi-product production-Routing problem with delivery time windows
    ( 2019) Fábio Silva Moreira ; Jans,R ; Luís Guimarães ; Cordeau,JF ; Bernardo Almada-Lobo ; 5428 ; 6114 ; 5965