Friday , March 29 2024

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

Mohamed Ali KAMMOUN1, Nidhal REZG1,2, Zied ACHOUR1,2, Sadok REZIG1,2
1 Industrial Engineering and Production Laboratory of Maintenance,
Enim, Lorraine University,
Metz, France
mohamed-ali.kammoun@univ-lorraine.fr, nidhal.rezg@univ-lorraine.fr, zied.achour@univ-lorraine.fr, sadok.rezig@univ-lorraine.fr
2 ICN Business School,
Metz-Nancy, France

Abstract: 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.

Keywords: Discrete event system, Time Petri Net, binary decision diagram, rescheduling problem.

>>Full text<<
CITE THIS PAPER AS:

Mohamed Ali KAMMOUN, Nidhal REZG, Zied ACHOUR, Sadok REZIG, State Space Search for Safe Time Petri Nets Based on Binary Decision Diagrams Tools: Application to Air Traffic Flow Management Problem, Studies in Informatics and Control, ISSN 1220-1766, vol. 25(1), pp. 39-50, 2016. https://doi.org/10.24846/v25i1y201605