The urban air mobility problem

Over the next two decades, Urban Air Mobility (UAM) Systems are anticipated to revolutionize the mass transportation industry. As envisioned presently, these systems will consist of electric vertical take-off and landing aircraft (eVTOLs) that operate from specially designed ports dispersed throughout a city. We consider the network logistics associated with the operation of a UAM system in its early phases, and focus on a problem of ‘routing and scheduling eVTOLs to maximize passenger throughput’. Key challenges for providers are the temporal nature of the demand, time windows for customers, and battery management constraints of the eVTOLs. We develop a three-index, arc-based formulation, routing eVTOLs over a time-expanded network. Due to the computational limitations of the arc-based formulation, we develop an alternate path-based formulation, and design a corresponding column generation procedure, identifying charge-feasible routes by way of a resource-constrained shortest path problem. The path-based approach is computationally robust, and can be applied in a heuristic manner by (i) sparsifying the time-expanded network, (ii) limiting column generation to the root node in a branch-and-bound scheme, and (iii) applying early termination criteria in the column generation procedure. Our computational experience on a large set of test instances indicates that the path-based approach identifies high-quality solutions for large instances. We conduct a case study using Washington D.C. taxi data, to demonstrate the viability of the column generation based heuristic procedure on real-world data.