Research

Research Topics

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).

  Contact: Prof. Bernard Ries,  Dr. Clément Dallard and Dr. Nour Tellache

• 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.

  Contact: Prof. Marino Widmer

• 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) 

  Contact: Prof. Bernard Ries, Dr. Meritxell Pacheco and Dr. Nour Teallache

Research Projects with Industrial Partners

• A column generation approach for the routing of electricity technicians

  Industrial Partner: Electricité de France (EDF)

  Funding Institution: Fondation mathématique Jacques Hadamard

  Start and end dates: November 2023 to November 2025

  Contact: Dr. David Schindl, Elise Bangerter, Dr. Meritxell Pacheco

   

  The maintenance of an electricity distribution network requires numerous technical interventions on a given day. The optimization of technicians’ rounds represents a critical element to guarantee operations efficiency and can be used to attain additional objectives like the reduction of the carbon emissions generated by the trips. However, this problem is notoriously difficult to solve. In this project, we are going to test an approach using advanced mathematical modeling and optimization techniques. These kinds of approaches have proven to be successful for an important class of optimization problems encompassing this one, namely the class of "vehicle routing" problems, but were not tested yet for this particular case.

• 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

   

  The industrial production of medicine bottles usually involves the following two main stages:

  1) Preparation of a large quantity of product stored in a bulk;

  2) Transfer of the product from the bulk into bottles via filling lines.

  This project is about optimizing the second stage, i.e. given the bulks production planning, assign a compatible filling line and a timeslot to each of them. Besides basic constraints such as the bulk and filling line availability, a number of specific product-related constraints have to be taken into account: some filling lines are not compatible with some bulks,  filling line setup should match the bottles format, some pairs of products should not treated consecutively on the same line without a thorough cleaning between them, and so on.  The main objective is to minimize the total tardiness of bulks treatment, with a special focus on priority ones.

   

  We developed a decision support tool based on mixed integer linear programming to model and solve the problem within a Julia program. On the user end, an Excel file was set up for the ease of data handling and planning visualization, with VBA macros ensuring the link between the two environments.

• 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)

  Contact: Dr. Meritxell Pacheco, Dr. David Schindl, Prof. Bernard Ries

  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

   

  In most companies, task scheduling is strongly intertwined with employees timetabling. In this project, we tackle both problems at the same time by assigning to each task a time period and a set of qualified employees. Each task has given associated duration, time window, location, number of necessary employees and set of required skills. Each job cannot be started before the beginning of its time window. In contrast, it may be completed after the end of its time window, but the tardiness is penalized in the objective function. To allow dynamic insertion of new tasks, our model allows to fix previously treated tasks, whose schedules and employee assignments have then to be taken into account while planning the new tasks. Additional constraints include employees availabilities, travel times between locations and synchronization aspects.

   

  We developed a decision support tool based on mixed integer linear programming to model and solve the problem within a Julia program. On the user end, an Excel file was set up for the ease of data handling and planning visualization, with VBA macros ensuring the link between the two environments.

• 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 

  Contact: Dr. David Schindl, Prof. Bernard Ries

   

  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.