In many application examples of discrete optimization, time aspects have to be considered in the derivation of suitable models. One way to integrate the aspect of time into the models are additional continuous variables representing for example arrival times at certain locations. These kinds of models have the disadvantage that their linear relaxation is usually very weak, which has negative effects when solving them by a branch-and-bound approach. Alternatively, it is possible to model every possible combination of arrival times and locations as nodes in a graph, the so-called time-expanded graph. Edges in this graph may only be used if the movement between locations takes less time than the difference of the arrival times of its nodes. Using these graphs, it is often possible to derive formulations whose linear relaxation is strong. The problem of these formulations is that the number of required nodes and possible edges is very large leading to very large models. In the DFG project "Solving time-dependent logistic optimization problems using time-reduced relaxations", the goal is to find graphs that still allow a relatively strong relaxation of the problem, but require significantly fewer nodes and edges. In principle, these graphs may also admit solutions that violate some of the temporal constraints. In an iterative procedure, the graphs are then adjusted until a solution is found that no longer violates any of the temporal constraints. During the project, such approaches were applied to two real-world problems. In the first, the goal was to optimize the routing of small passenger aircrafts used on safaris in Africa. In the second, the sequence in which customers are served by autonomously driving electric delivery robots was optimized.

Partner Universities

TU Dortmund University

Funding

Deutsche Forschungsgemeinschaft, grant number FU 860/1-1.

Related talks

• Refinement Algorithms for the Time and Battery VRP, Workshop Optimierung 2021, Cottbus, 24th of March 2021
• The Branch and Refine Algorithm for Time Dependent Discrete Optimization Problems, OR 2019/ International Conference on Operations Research, Dresden, 5th of September 2019.
• A Time-Flow Approach for Scheduling and Routing Fly-in Safari Airplanes, Workshop Optimierung 2019, Olbernhau, 15th of March 2019.
• A Time-Flow Approach for Scheduling and Routing of Fly-in Safari Airplanes, OR 2018/ International Conference on Operations Research, Brussels, 12th of September 2018.

Related publications

• Fabian Gnegel, Stefan Schaudt, Uwe Clausen, Armin Fügenschuh, A 2D Layered Graph Approach for Scheduling Delivery Robots, 2021, Preprint. DOI:10.26127/btuopen-5493
• Fabian Gnegel and Armin Fügenschuh, Branch-and-Refine for Solving Time-Dependent Problems, 2020, Preprint. DOI: 10.26127/btuopen-5199
• Fabian Gnegel and Armin Fügenschuh, An Iterative Graph Expansion Approach for the Scheduling and Routing of Airplanes, Computers & Operations Research 114:104832, 2020. DOI: 10.1016/j.cor.2019.104832