Planning of trajectories, i.e. paths over time, is a challenging task. Thereby, the trajectories for involved commodities often have to be considered jointly as separation constraints have to be respected. This is for example the case in robot motion or air traffic management. Involving these discrete separation constraints in the planning of best possible continuous trajectories makes the task even more complex. Hence, in current practice, the resulting optimization problems are solved sequentially or with restricted planning space. This leads to potential losses in the usage of sparse resources. To overcome these drawbacks, we develop a graph based model for disjoint trajectories optimization. Further, we present a discretization technique to depict the full available space, while respecting potentially non-convex restricted areas. As a result, an integer linear optimization program needs to be solved whose size scales with the number of discretization points. Thereby, even for moderately sized instances a sufficiently detailed representation of space and time leads to models too large for state of the art hard- and software. To tackle this, we develop an adaptive-refinement algorithm that works as follows: Starting from an optimal solution to the integer program in a coarse discretization the algorithm re-optimizes trajectories in an adaptively refined discretized neighborhood of the current solution. This is further integrated into a rolling horizon approach. We apply our approach to the integrated trajectory optimization and runway scheduling in the surrounding of airports. Computational experiments with realistic instances show efficiency of the method.
Citation
2021