Capacitated Location-Allocation-Routing Problem with Time Windows for On-Demand Urban Air Taxi Operation

Abstract

Urban air taxi (UAT) operation has gained traction with the advancements in distributed electric propulsion and the emergence of electric vertical take-off and landing aircraft. Start-up companies and aircraft manufacturers are pursuing the possibility of operating UAT at scale in urban and suburban areas and at an affordable price. However, considerable uncertainties remain about several strategic, tactical, and operational aspects that affect UAT adoption. We envision a mature state of UAT operation in which the UAT operator offers door-to-door, multimodal, on-demand, and per-seat service. We propose the concept of flexible meeting points for UAT operation where passengers are flexible about the location of the UAT pads for boarding and deboarding, and could therefore be pooled together to share an aircraft. Consequently, we model UAT fleet operation as a capacitated location-allocation-routing problem with time windows and present a mixed integer programming formulation. The formulation addresses decisions on request acceptance and rejection, allocation of requests to flights, and aircraft routing and scheduling. Additionally, it allows for consolidating the demand to increase the aircraft’s utilization and service rate. The numerical results indicate that the demand consolidation scheme could significantly decrease the number of rejected requests and the aerial mileage. Depending on the operator’s business model, the proposed formulation could be used offline in a static and deterministic setting when all requests are known in advance, or it could be employed online by sequentially solving the static and deterministic snapshot problems with no knowledge about future requests.