2021/08/07 by Claudio Contardo, Contardo, Claudio, Luciano Costa +1
Business, Management and Accounting · Computer Science · Engineering · Mathematics · #Advanced Manufacturing and Logistics Optimization #Consumer Retail Behavior Studies #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Other Computer Science (cs.OH) #cs.OH #math.OC
paper · pdf · doi:10.48550/arxiv.2108.04233
openalex publication_date 2021/08/07 · arxiv created 2022/01/18 · arxiv updated 2022/01/19 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
We consider the problem of maximizing the number of people that a dining room can accommodate provided that the chairs belonging to different tables are socially distant. We introduce an optimization model that incorporates several characteristics of the problem, namely: the type and size of surface of the dining room, the shapes and sizes of the tables, the positions of the chairs, the sitting sense of the customers, and the possibility of adding space separators to increase the capacity. We propose a simple, yet general, set-packing formulation for the problem. We investigate the efficiency of space separators and the impact of considering the sitting sense of customers in the room capacity. We also perform an algorithmic analysis of the model, and assess its scalability to the problem size, the presence of (or lack thereof) room separators, and the consideration of the sitting sense of customers. We also propose two constructive heuristics capable of coping with large problem instances otherwise intractable for the optimization model.