MODELING MOVEMENT OF OBJECTS WITHOUT STOPS IN A NETWORK OF CROSSING ROUTES

Abstract

Modeling of movement of objects without stops in a network of crossing routes is studied. The problem is formulated in terms of disjunctive linear programming, mixed integer linear programming and graph theory. Several variants for representing constraints on convergence of objects are considered. NP-completeness of the problem in the strong sense is proved.

Keywords

• routing
• scheduling
• flight safety
• difference logic
• satisfiability modulo theories
• linear programming
• disjunctive programming