Optimization Online


An Integrated Rolling Horizon and Adaptive-Refinement Approach for Disjoint Trajectories Optimization

Benno Hoch (Benno.Hoch***at***fau.de)
Frauke Liers (Frauke.Liers***at***fau.de)

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

Keywords: disjoint trajectories, adaptive-refinement, rolling horizon, optimization, integer programming

Category 1: Applications -- OR and Management Sciences

Citation: 2021

Download: [PDF]

Entry Submitted: 10/20/2021
Entry Accepted: 10/20/2021
Entry Last Modified: 11/18/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society