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
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
Science is modelling! We create models -- a schematic description or representation of a problem -- for the purpose of understanding how things work, of explaining and predicting phenomena, of controlling our environment, of improving our work processes. And technology is the application of scientific models in order to increase the quality of life.
Mathematics is an excellent language 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 was involved in various industrial projects: At Holcim, a large company in cement production, a multi-commodity production model was used to planify the production and distribution on a strategic and operational level. The Federal Food Supply Office of Switzerland uses a decision support system in regard to changes of the domestic food production, processing and stockpiling. ABB Finland improved the energy efficiency in iron and steel making using our tools on model building. Various feasibility studies and prototypes in truck tour planning have been made for small companies in Switzerland. Challenging seasonal sport schedules for the tournament of National Leagues in Football and other sports are based on Operations Research tools that we developed in our group.
Research Projects with Industrial Partners
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)
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