Land layout optimisation for virtual land sales in the metaverse: two-dimensional assortment problem
研究了元宇宙中虚拟土地销售时，如何优化布局买家请求的矩形地块以最小化所需开放土地面积，提出了二元邻接算法（BAA），在求解质量和计算时间上优于现有方法。
With the growing popularity of the metaverse, the virtual real estate in the metaverse has generated immense investment enthusiasm. Considering the virtual land sale mode allowing the potential buyers to request the purchase of rectangular land parcels of a specified size, this study investigates how to lay out the requested land parcels for minimising the size of the required rectangular open land, which can be formulated completely as the two-dimensional assortment problem (2DAP). Due to the strong NP-hardness of the 2DAP, an effective and efficient heuristic solution approach named binary adjoining algorithm (BAA) is presented for tackling the 2DAPs in large scales. The conducted computational experiments show that the BAA can outperform the state-of-the-art piecewise-linearisation mixed integer linear programming model as well as four existing advanced metaheuristic techniques designed for the 2DAP, in both solution quality and computational time, on the small-size instances. The superiority of the BAA over either foregoing reference method on the large-size instances with up to 60 requested land parcels is also demonstrated.