The following research areas are currently addressed:
Combinatorial Optimization and Graph Theory
In combinatorial optimisation, we are interested in finding a best solution among a finite number of possible solutions. Even though there is a finite number of possible solutions, this number may be exponential and therefore we cannot check every single solution in order to find a best one. Thus, more sophisticated solution methods must be developed. One major motivation for studying combinatorial optimisation is the fact that many real world problems can be formulated as combinatorial optimisation problems.
Such formulations often use graphs, i.e. mathematical structures able to model pairwise relations between objects. They form a powerful modelling tool that can be used in various domains: computer science (communication networks, link structure of a website, data organisation), biology (migration paths of species, virus spreading), chemistry (study of molecules), sociology (social networks, rumour spreading), transportation and logistics (shortest path, vehicle routing, scheduling), etc.
In our group, we mainly focus on combinatorial optimisation problems related to graph theory and analyse these problems both from an algorithmic point of view (design and analysis of algorithms) and from a structural point of view (detecting structural properties of the underlying graphs to develop efficient algorithms).
Heuristic and metaheuristic methods
Despite the permanent evolution of computers and the progress of information technology, finding a best solution among a finite set of solutions is not an easy task. There will always be a critical size for the solution set above which even a partial listing of feasible solutions becomes prohibitive. Because of these issues, combinatorial optimization specialists have focused their research on developing heuristic methods.
A heuristic method is often defined as a procedure that uses the structure of the considered problem in order to find a solution of reasonably good quality in as little computing time as possible. Although obtaining an optimal solution is not guaranteed, the use of a heuristic method provides multiple advantages when compared to exact methods: for example, when it is applicable, an exact method is often much slower than a heuristic method, what generates additional computing costs and a typically very long response time. Moreover, a heuristic method can be easily adapted or combined with other types of methods. This flexibility increases the range of problems to which heuristic methods can be applied.
Even though a good knowledge of the problem to be solved is the main contributor to an efficient and successful use of a heuristic method, there are several general rules that can be used to guide the search in promising regions of the solution space. The research principles of these approaches constitute a basis for several known metaheuristic methods such as local search methods (tabu search, simulated annealing), evolutionary algorithms (genetic algorithms) or nature-inspired metaheuristics (ant colony optimization, particle swarm optimization). Very general in their concept, these methods do, however, require a large modeling effort if one wishes to obtain good results.
One of the objectives of our research group is the development and the application of such solution methods to real life problems mainly in supply chain management and logistics.
Decision Support: models, methods and applications
Mathematics is an excellent tool to represent formal models. In Decision Support and Operations Research, we use mathematical models to represent complex problems arising in all kind of economical activities. Together with the speed of computers we are able to solve large real-life problems. To be successful in practice, one must have a good and profound understanding of the problem at hand, translate it into the language of mathematics, implement and solve it on a computer, and be able to communicate the results to the management. Our group is/was involved in various industrial projects (see here below)
Research Projects with Industrial Partners
Make-and-Fill Production Scheduling in the Pharmaceutical Industry
Industrial Partner: private company (direct funding)
Start and end dates: June 2020 to June 2021
Contact: Dr. David Schindl
Development of a decision support tool for automatically scheduling the orders in a make-and-fill production environment.
Efficient and Sustainable Waste Collection
Academic Partner: International Institute of Management in Technology, University of Fribourg
Industrial Partner: Schwendimann AG
Funding Institution: Innosuisse under Grant 36157.1 IP-EE
Start and end dates: September 2019 to August 2022 (projected)
Data: can be found here
In Swiss municipalities, a curbside system is often used to collect the non-recoverable solid waste. In principle, the trucks stop at every household for the collection. Due to the many stops of the heavy trucks, this classic strategy causes high fuel consumption, emissions and noise.
The objective of this project is to improve the municipal solid waste collection process by designing efficient and sustainable waste collection strategies targeted to the needs of the municipalities. This objective is pursued through the following three components. First, new waste collection concepts are proposed using modern physical waste collection elements, such as electric vehicles and containers with compressors. For example, small, agile vehicles may bring the garbage bags to larger containers in intermediate depots and large vehicles may then regularly discharge these containers. Second, mathematical models and optimization algorithms are developed for deciding how to design a waste collection concept for a given municipality in the best possible way. Typical decisions are about the locations of the waste collection points, the types of vehicles used to collect the waste at all collection points and the routing of each vehicle. Third, an interactive decision support tool is developed. It enables to specify the inputs, such as the street network and the waste quantities, and to display the results of the optimization algorithms for all alternatives. This tool will help the decision-makers to choose the best waste collection concept for their municipality.
Dynamic Task Scheduling in the Pharmaceutical Industry
Industrial Partner: private company (direct funding)
Start and end dates: February 2019 to December 2019
Contact: Dr. David Schindl
Development of a decision support tool for employee assignment and scheduling of tasks that are entering into the scheduling system in a dynamic fashion.
Optimization of train crew assignment to activity segment
Industrial Partner: SBB-CFF
Funding Institution: SBB Research Fund
Start and end dates: March 2022 to March 2023
Scheduling problems are part of the most difficult problems in operations research, especially for railway companies. Due to this difficulty, the SBB has decomposed scheduling problems of its trains and crews in several steps. One of them consists in assigning its activity segments (which can be for instance the portion of the Intercity 711 route, from 7:42 am in Geneva to 9:03 am in Fribourg) to depots, which are possible places where train crews start and end their working days. The SBB is looking for some general insight on how to compute these assignments, in order to end up with as efficient crew schedules as possible, which are built in subsequent steps. In this project, the DS & OR group will analyse the current assignment method of the SBB and propose some directions to improve it through strategic decisions.
Decoding plant communication to grow more food
Industrial Partner: Vivent SA
Funding institution: Innovation Booster
Start and end dates: March 2023 to September 2023
Contact: Dr. Jérôme De Boeck
The understanding of plant language is at it’s very beginning. Several types of existing sensors provide measurements on a plant which are now mainly interpreted through statistical methods and artificial intelligence. These measurements provided information from an external perspective without taking into consideration the internal structure of a plant. As a results, there are open question on how to interpret properly the information provided by the measurements of sensors or where sensors should be placed to detect the most relevant information. Decoding the internal communication system of a plant, called excitable system, would provide a lead to answer these questions. Therefore, growers could change their way to observe the health of a plant, allowing to detect plant stresses at earlier stage than through visual indicators. This would lead to a better reactivity of grower on their crops, reducing crop losses and increasing their yield. Vivent SA and the Decision Support & Operations Research (DS&OR) service of the University of Fribourg will work jointly on this plant communication decoding problem using graph theory, a powerful modeling tool for systems representing communication networks.