Complexity Results for the Feasibility Problems of the UAM Service

Urban Air Mobility (UAM) using battery-powered aircraft is attracting much attention as a new mobility service, but it has a variety of issues that need to be resolved in the actual operation process. In this paper, we would like to tackle the problem to check the feasibility of daily customer request and optimize the routing of aircraft. Specifically, we propose two problems of minimizing the total travel time by aircraft and minimizing the imbalance of the travel time between aircraft. By analyzing the computational complexity of each problem, we show that the first problem can be solved in strongly polynomial time by transforming the problem into the minimum cost flow problem while the second problem is strongly NP-hard through the reduction from the numerical 3-dimensional matching problem.