State Space Search for Safe Time Petri Nets Based on Binary Decision Diagrams Tools: Application to Air Traffic Flow Management Problem

摘要

The highly concurrent time discrete event systems modeled by Time Petri Net (TPN) suffer from the problem of the state space explosion owing to a large number of accessible markings. To handle this problem, this paper proposes a new solution based on modelling in discrete time the reachable markings of TPN using a new structure so-called Time Reduced Ordered Binary Decision Diagrams (TROBDDs). In this work a new efficient methodology is presented to generate and store a big state space to deal with the time execution and memory space constraints. This new approach is used to resolve the Flight Rescheduling Problem (FRP) subject to capacity constraints due to adverse weather conditions. An optimization algorithm is proposed to minimize the cost function and determine the optimal flight plan according to the new capacity constraints. A number of instances on the FRP is presented in order to illustrate such approach, which allows us to save the memory space and CPU requirements.