Robust optimization methodologies for the free route concept

A technique called robust optimization has been proposed previously for addressing (dynamic) decision problems with uncertainty. This approach starts from a "nominal" optimization problem, say a linear program. Assuming bounds, and structure, of the uncertainty are known, we seek a robust solution, that is, one which minimizes the (worst-case) objective while satisfying the constraints robustly. Such solutions can be approximately computed in modest computing time, using Lagrangian relaxations and convex optimization. The method is computationally cheaper than stochastic programming, yet produces guarantees (that constraints are satisfied despite uncertainty). The paper outlines some potential applications of the method to robust collision detection in the context of free route.