# Dr.-Ing. Felix Brandt

###### Abteilungsleiter

### Werdegang

Felix Brandt studierte Informatik am Karlsruher Institut für Technologie mit den Schwerpunkten Algorithmen- und Softwaretechnik. Er arbeitet als wissenschaftlicher Mitarbeiter und Projektleiter am FZI im Forschungsbereich IPE mit dem Schwerpunkt Logistik und Supply Chain Optimierung. Seine Interessen liegen in der Planung und Optimierung komplexer Systeme durch die Entwicklung effizienter Algorithmen und den Einsatz verschiedenster Methoden der künstlichen Intelligenz (kombinatorische Optimierung, Constraint-Programmierung, Bildverarbeitung).

2017 promovierte Felix Brandt am Karlsruher Institut für Technologie (KIT) summa cum laude zum Thema "The Air Cargo Load Planning Problem".

### Publikationen

#### Zeitungs- oder Zeitschriftenartikel (2)

- Constraint-based large neighborhood search for machine reassignmentInfoDetails
Felix Brandt and Jochen Speck and Markus Völker, 2014

This paper addresses a process-to-machine reassignment problem arising in cloud computing environments. The problem formulation has been posed as the ROADEF/EURO challenge 2012. Our presented approach is basically a large neighborhood search that iteratively improves a given solution. In each iteration only a subset of processes is considered for reassignment and the newassignments are evaluated by a constraint program. In this paper we present our general solution approach. Furthermore, we evaluate different process selection strategies and other optimization means to improve the performance on larger instances. In addition, we present a simple way to compute tight lower bounds of the necessary costs.

- A constraint programming-based approach to a large-scale energy management problem with varied constraintsInfoDetails
Felix Brandt and Reinhard Bauer and Markus Völker and Andreas Cardeneo, 2013

This paper addresses a large-scale power plant maintenance scheduling and production planning problem, which has been proposed by the ROADEF/EURO Challenge 2010. We develop two lower bounds for the problem: a greedy heuristic and a flow network for which a minimum cost flow problem has to be solved. Furthermore, we present a solution approach that combines a constraint programming formulation of the problem with several heuristics. The problem is decomposed into an outage scheduling and a production planning phase. The first phase is solved by a constraint program, which additionally ensures the feasibility of the remaining problem. In the second phase we utilize a greedy heuristic -- developed from our greedy lower bound -- to assign production levels and refueling amounts for a given outage schedule. All proposed strategies are shown to be competitive in an experimental evaluation.

#### Thesis (2)

- The Air Cargo Load Planning ProblemInfoDetails
Felix Brandt, 2017

A major operational planning problem in the air cargo industry is how to arrange cargo in an aircraft to fly safely and profitably. Therefore, a challenging planning puzzle has to be solved for each flight. Besides its complexity, the planning is mostly done manually today, which is a time consuming process with uncertain solution quality. The literature on loading problems in an air cargo context is scarce and the term is used ambiguously for different subproblems like selecting containers, packing items into containers, or loading containers into aircraft. All of the presented models only focus on certain aspects of what is in practice a larger planning problem. Additionally, some practical aspects have not been covered in the literature. In this work, we provide a comprehensive overview of the air cargo load planning problem as seen in the operational practice of our industrial partner. We formalize its requirements and the objectives of the respective stakeholders. Furthermore, we develop and evaluate suitable solution approaches. Therefore, we decompose the problem into four steps: aircraft configuration, build-up scheduling, air cargo palletization, and weight and balance. We solve these steps by employing mainly mixed-integer linear programming. Two subproblems are further decomposed by adding a rolling horizon planning approach and a Logic-based Benders Decomposition (LBBD). The actual three-dimensional packing problem is solved as a constraint program in the subproblem of the LBBD. We evaluated our approaches on instances containing 513 real and synthetic flights. The numerical results show that the developed approaches are suitable to automatically generate load plans for cargo flights. Compared to load plans from practice, we could achieve a 20 percent higher packing density and significantly reduce the handling effort in the air cargo terminal. The achieved costs of additional fuel burn due to aircraft imbalances and reloading operations at stop-over airports are almost negligible. The required runtimes range between 13 and 38 minutes per flight on standard hardware, which is acceptable for non-interactive planning. Cargo airlines can significantly profit from employing the developed approaches in their operational practice. More and especially the profitable last-minute cargo can be transported. Furthermore, the costs of load planning, handling effort, and aircraft operations can be significantly reduced.

- Solving a Large-Scale Energy Management Problem With Varied ConstraintsInfoDetails
Felix Brandt, 2010

Diese Arbeit beschäftigt sich mit dem Problem der Wartungs- und Produktionsplanung eines großen konventionellen Kraftwerksparks unter Berücksichtigung vielfältiger Nebenbedingungen und Unsicherheit über einen Zeitraum von bis zu 5 Jahren. Die Aufgabenstellung entstammt dem ROADEF/EURO Challenge 2010, einem Wettbewerb der gemeinsam von der französischen Organisation für Operations Research und Decision Support (ROADEF) und der Europäischen Organisation für Operations Research (EURO) ausgeschrieben wurde.

#### Betreute Thesis (7)

- Schulungsplanung als ZuordnungsproblemDetails
Frauke Tabert, 2014

- Models for Freighter Scheduling at Combination CarriersDetails
Ulf Hansen, 2014

- Konzeptionelle Bestimmung von Schulungsstandorten bei der Lufthansa Cargo AGDetails
Mirko Wichmann, 2013

- Analyse des Systems zur Flugplanevaluierung der Lufthansa Cargo AGDetails
Maximilian Möller, 2013

- Tourenplanung mit stochastischer korrelierter NachfrageInfoDetails
Jacqueline Wirnitzer, 2012

In practice, many parameters of truck scheduling problems are inherently uncertain. Thus, many extensions of the basic Vehicle Routing Problem (VRP) have been established. One of them is the VRP with Stochastic Demands (VRPSD). Almost all published models solving this optimization problem assume independency between demand distributions of customers, although this assumption does not apply for many cases in reality. In this work, a generalisation of the VRPSD is introduced, in which correlation between customers is taken into account. We call this problem VRP with Correlated Stochastic Demand (VRPCSD). The aim of this thesis is to develop a two-stage heuristic solution to the problem. A regular tour schedule is created on the basis of stochastic data before actual demands are announced. Afterwards, when demands are known, the tour schedule is checked for infeasibilities and adjusted by recourse strategies if necessary. The overall objective is to minimize total costs. We refrain from reoptimisation (replanning when demands are announced) to save costs by regularities in tours (see Gröer, Golden und Wasil (2009)). In this work various methods and recourse strategies for the VRPCSD are developed. An improved Savings heuristic is the basis of this process. To create a regular tour schedule, the only approach to the VRPCSD found in literature is implemented and refined (Yee and Golden (1979)). Both the original and the adapted approach turn out to be inefficient, therefore, new methods are developed. Likewise, new recourse strategies are developed besides the established Back-To-Depot strategy. Finally, the various methods are combined with the recourse strategies and experiments are conducted. As a benchmark we use the average reoptimisation results. The best combinations of methods and recourse strategies achieve results that differ on average less than 20% from the benchmark.

- Algorithmische Packplanung für LuftfrachtInfoDetails
Mathias Leu, 2012

In dieser Arbeit wird ein Verfahren entwickelt, dass die praktische Anwendbarkeit von automatisierter Frachtplanung in der Luftfracht beweisen soll. Das entwickelte Verfahren basiert auf einem Packalgorithmus, der aus Frachtstücken, die in einer Reihenfolge übergeben werden, eine Packanordnung erstellt. Für die Ermittlung einer guten Reihenfolge wird eine Nachbarschaftssuche über verschiedene Nachbarschaften durchgeführt. Das Verfahren beinhaltet verschiedene praxisrelevante Restriktionen wie beispielsweise Stapelbarkeit, Stabilität, Priorisierung und Trennungs- bzw. Zusammenladbarkeitsvorschriften. Anhand eines praxisnahen Referenzdatensatzes sowie verschiedener Realdaten wird das Verfahren ausführlich getestet und bewertet. Abschließend wird ein Ausblick über mögliche weitere Entwicklungmöglichkeiten gegeben.

- Entwicklung einer schnellen Heuristik für das Tourenplanungsproblem mit AlternativenDetails
Martin Ziegler, 2011

#### Whitepaper (6)

- Packing with Item Availability and Bin Due DatesInfoDetails
Felix Brandt and Jan-Nikola Popratnjak and Enrico Schulz, 2014

In this work, we present a new generalisation of the multiple heterogeneous knapsack problem (MHKP), by considering earliest availability dates of items and latest usage dates of bins. In the standard MHKP it is assumed that all the items to pack into bins are available and there are no restrictions about the time of bin assembly. In logistics however, especially in an air cargo environment this is not necessarily the case. Instead, the items for a flight arrive at the hub at different times, due to their inbound connection or delivery by the shipper. Furthermore, we assume there already exists a general production schedule for the bins of all flights. For a given flight to pack, we interpret this schedule as a sequence of possible due dates of its bins. In a solution each of these due dates can be assigned to at most one bin, i.e., the order of assembly of the bins is determined by the procedure. Accordingly, each bin can only be filled with items that are available before its due date. We propose an integrated problem formulation, from which we derive and solve a MIP model. Furthermore, we present our preliminary experiments to motivate the benefits of an integrated approach and compare its performance to simple decompositions into a sequence of standard MHKP.

- A Multi-Temperature Truck Layout and Loading ProblemInfoDetails
Felix Brandt and Anne Meyer, 2014

In this work we consider a mixed vehicle layout and loading problem arising in the delivery of convenience products to stores by using multi-temperature vehicles. The vehicle's loading spaces have movable/retractable wall segments - both in longitudinal and lateral direction. The walls can be reconfigured for each tour into temperature zones, which are flexible in size and shape. For each tour, the order of stops and transport units per customer and temperature zone are given. We want to find a feasible wall setup and unit assignment, which results in a sequential unloading with a minimum number of unit reshuffles. In our talk, we present an integer programming model capturing the layout constraints as well as the reshuffling aspects of the problem. As the number of transport units per truck is naturally small and limited, the model can be solved to optimality within a reasonable amount of time. We give an overview of our experiments using real world data from our industrial partner PTV group. Our results show that there are significant time savings achievable - both during tour preparation and throughout the tour - compared to straight-forward manual loading strategies.

- A Set-Covering Based Heuristic for Rich Vehicle Routing Problems with a Heterogneous FleetInfoDetails
Felix Brandt and Nitin Ahuja and Werner Heid and Anne Meyer and Frank Radaschewski, 2013

The Heterogeneous Vehicle Routing Problem (HVRP), as defined by Golden et. al, assumes a fleet that is composed of different types of vehicles. Usually, the vehicles are differing in their loading capacities as well as fixed or variable costs. The objective is to minimize the total cost of all vehicles used in the solution. One way to tackle the problem, presented by Taillard, is to solve a homogeneous fleet VRP for each vehicle type independently with an unlimited number of vehicles. Thereby, a lot of (partly overlapping) tours are generated. From these tours, the least cost subset visiting each customer once is found by solving a Set Partitioning Problem. In our work, we apply and extend the ideas of Taillard, to enable a commercial library for rich but homogeneous fleet VRPs to handle heterogeneous fleets. For the creation of tour plans, we rely on the VRP software package PTV xTour Server. Thereby, we are able to incorporate all of its supported types of restrictions from real world problems, like break and rest rules or multi-trips. We propose different strategies to create a number of preferably diverse solutions from the homogeneous fleet VRPs. To find the least cost subset of tours, we choose a Set Covering formulation. To make each customer visited exactly once, we introduce one additional step to repair the solution. The main idea of this step is to generate promising subtours out of the tours that contain customers, which are visited more than once in the current solution. These subtours are added to the Set Covering problem, which is solved repeatedly until no more duplicate visits exist. In this talk we present our solution approach, our insights of the experiment phase and from a real world application. Furthermore, we talk about some experience gained from implementing our approach into PTV xTour Server, a commercial vehicle routing solution.

- Constraint-based large neighborhood search for machine reassignmentInfoDetails
Felix Brandt and Markus Völker and Jochen Speck, 2012

The presented approach is basically a large neighbourhood search that iteratively improves the given solution. In each iteration a subset of processes is released, while all other processes stay on their current machine. Released processes are then reassigned to the machines by a constraint program and the first improving solution is selected. We evaluate different neighbourhood selection strategies, branching techniques and optimization to improve performance on big instances. Furthermore, we present a network flow formulation that allows to compute lower bounds on the necessary costs.

- Constraint-based construction heuristics for rich vehicle routing problemsInfoDetails
Felix Brandt and Anne Meyer, 2012

Constraint programming (CP) is successfully applied to rich vehicle routing problems. However, during the construction phase CP is used as a mere satisfiability checker, if at all, not using its power for finding an actual solution. Thus initial solutions might be poor or need additional repair procedures. In this work we want to show how constraint programming can be applied during a construction phase. We develop branching techniques analogous to established construction heuristics from literature. We present our first results and compare the performance of different approaches.

- Merge-Savings - A Construction Heuristic for Rich Vehicle Routing ProblemsInfoDetails
Felix Brandt and Andreas Cardeneo and Werner Heid and Alexander Kleff, 2010

This contribution presents a new construction heuristic for general vehicle routing problems. The Merge-Savings algorithm is a generalization of the well-known Clarke & Wright Savings-algorithm. Moreover, our new approach implicitly includes the customer insertion operations found in the family of classical sequential and parallel insertion algorithms. We present the design goals of this algorithm, e.g. improved handling of time-windows and duration constraints compared to the Clarke & Wright algorithm, the optimization of planning problems with both depot-related as well as pickup and delivery transports in arbitrary proportions , and incremental planning, i.e. the extension of a given plan with unscheduled orders. The idea of Merge-Savings is, at each iteration, to merge two subtours into a new tour while maintaining each tour?s precedence relations. Algorithmically, this is realized by dynamic programming where each state represents the new tour constructed so far. The action set consists of choosing the next stop either from the first or the second tour. This algorithmic approach is fairly general and allows for the inclusion of constraints like multiple time windows, pickup and delivery transports, waiting time restrictions, and others as typically found in rich problems. We present computational results on real world instances realized with an implementation of Merge-Savings in the commercial vehicle routing package PTV Intertour and relate our approach to benchmark problems from the literature.

Export Suchergebnis .bib

### Kontakt

Telefon: +49 721 9654-304

Fax: +49 721 9654-305

E-Mail: brandt@ fzi.de- Constraint-based large neighborhood search for machine reassignmentInfoDetails