Logic-Constrained Shortest Paths for Flight Planning

ArXi:2412.13235v4 Announce Type: replace The logic-constrained shortest path problem (LCSPP) combines a one-to-one shortest path problem with satisfiability constraints imposed on the routing graph. This setting arises in flight planning, where air traffic control (ATC) authorities are enforcing a set of traffic flow restrictions (TFRs) on aircraft routes in order to increase safety and throughput. We propose a new branch and bound-based algorithm for the LCSPP. The resulting algorithm has three main degrees of freedom: the node selection rule, the branching rule and the conflict.