Models and algorithms for optimising two-dimensional LEGO constructions

doi:10.1016/j.ejor.2020.07.004

Models and algorithms for optimising two-dimensional LEGO constructions

2021-02-01

4

PRE

AI

DOI：10.1016/j.ejor.2020.07.004

原文链接

原文求助

摘要

En 中文

The LEGO Construction Problem is the problem of deciding which bricks to place where in a predefined LEGO construction. The input consists of coloured voxels that each correspond to the size of a LEGO unit, such that all LEGO bricks are multiples of this LEGO unit. A solution to the LEGO Construction Problem is feasible if all bricks are within the design domain, the bricks do not overlap, the bricks satisfy the colour constraints, and all bricks connect into a stable construction. In this article, we propose an automated approach for optimising LEGO constructions, and in particular, we focus on 2D constructions. We introduce mathematical programming formulations of the problem as well as a fast constructive heuristic algorithm that is very efficient for constructing regular walls. Further, we integrate the models and the heuristic into a matheuristic algorithm, where the heuristic algorithm defines most of the construction, in particular, large elements that require regular patterns, while the mathematical models are used to tackle critical parts of the construction and to ensure the overall stability of the result. The article concludes with computational experiments on regular and irregular constructions showing the efficacy of the proposed algorithm when compared with two recent approaches from the literature. (C) 2020 Elsevier B.V. All rights reserved.

Keyword:

Cutting

LEGO construction problem

Mathematical models

Matheuristic

Structural integrity

Models and algorithms for optimising two-dimensional LEGO constructions

摘要

AI总结

期刊

机构