Seating Arrangement Optimization in COVID-19 Era: a quantum computing approach

2020 year has been a turning point for the entire humanity. The COVID-19 pandemic has not only revolutionized our way of thinking, but it has changed the way we live, leading to having limitations on any aspect of our daily life, from the smallest things to the biggest. This extraordinary situation has afflicted the railway world, too, since the movements have been limited drastically and new rules have been introduced. This thesis focuses on analyzing passenger transport's current situation on high-speed trains in this particular historical period we are experiencing, the COVID-19 Era. It aims to create hypothetical scenarios of passengers' distribution inside a train wagon with current health and hygiene rules. The main goal of what has been defined as the Seating Arrangement Optimization problem is to fill the train wagon as much as possible and therefore transport the largest number of people by maximizing the number of passengers belonging to the same family sitting in nearest seats. In this work, two different optimization models for formalizing the identified problem are presented and compared: a Mixed-Integer Linear Programming (MILP) model, one of the most common formulations in literature in the optimization field, and a Quadratic Unconstrained Binary Optimization (QUBO) model, a novel type of problem that can be solved on a quantum computer. In particular, for the resolution of the first type of model, the Gurobi commercial solver is used while, for the latter one, the QBSolv and a classical-quantum hybrid solver provided by D-Wave Systems Inc., a leader company in the quantum computing field, are considered. Quantum computing is an innovative research field currently still under development, on which time and money have begun to be invested only in recent years. What makes this research field attractive is the particular way with which quantum technology operates and the great potential it can offer to solve real-world problems. Due to the current physical capabilities, quantum computers' computational resources are not sufficient to execute too large optimization problems. Still, even with small instances like the ones considered in this work, it can be seen how much they can find highly optimized solutions in a short time.