Optimising eVTOL vehicle scheduling problem in on-demand urban air mobility system with capacitated vertiports

Urban Air Mobility (UAM), utilising Electric Vertical Takeoff and Landing (eVTOL) vehicles, is set to revolutionise urban transportation. This paper addresses the critical eVTOL Vehicle Scheduling Problem (eVTOL-VSP) for optimising services in an on-demand UAM system with capacitated vertiports. After delineating the differences between the eVTOL-VSP, the Airline Scheduling Problem (ASP), and the Electric Vehicle Routing Problem with Time Windows (EVRPTW), we define the eVTOL-VSP by integrating flight assignment, eVTOL routing, charging, and takeoff-landing strategies. By detailing eVTOL operational processes, we construct a discrete space-time-state network and formulate a mixed-integer linear programming model (MILP) to simultaneously optimise the aforementioned subproblems. The objective is to minimise costs and maximise the benefits of the serviced flights. Utilising the Alternating Direction Method of Multipliers (ADMM), we decompose the complex model into manageable subproblems, which are efficiently solved using a forward dynamic programming algorithm. Validation using both illustrative and real-world UAM networks demonstrates the effectiveness of our ADMM-based solution framework, thereby establishing a theoretical foundation for eVTOL scheduling optimisation and enhancing the efficiency and safety of UAM systems.