Improving Decision Making in Real-world Applications by Solving Combinatorial Optimization Problems

The motivation for this work is to study complex real-world scenarios and provide tools that can actually improve decision-making in those problems. To do so, we mainly adopt techniques from the fields of Operations Research and Combinatorial Optimization. In this dissertation, we focus on three real-world applications from different industries that can be modeled as combinatorial optimization problems and address them with operations research techniques. The dissertation is divided in chapters, each of which is related to a different topic. In Chapter 1, a problem concerning the transportation of biological samples from draw centers to a main laboratory for analysis is presented. The problem arises from a healthcare application in Bologna, Italy, where the healthcare authority decided to centralize the analysis of all biological samples of the area to a main laboratory, in order to exploit economies of scales and reduce the costs for samples’ analysis. Of course, such an improvement goal also created a new complex problem: all the samples must be transported from draw centers to the main lab. A fleet of vehicle is available for the transportation and must collect the samples from draw centers during given times of the day and deliver them within a certain time, since samples are perishable. Vehicles can also exploit the existence of dedicated centers that can extend the lifespan of the samples and where samples can be transferred from one vehicle to another. It is clear from this brief description how hard it could be to decide which is the routing of all the vehicles which minimizes the traveling costs while delivering all samples on time. For this problem we developed different mixed integer linear programming models, metaheuristic algorithms, and grouping policies for the samples that are able to tackle the complexity of the problem and improve routing decisions. All methods have been tested through an extensive computational campaign using real-world data, showing the effectiveness of the proposed approaches. In Chapter 2, a problem related to the agricultural industry is presented. The problem arises from a real-world application in Italy and it is that of planning the use of the available land of a farm for a given number of years, given a set of crops that can be grown. The objective is to maximize the farmer’s profit, but the farmer is subject to several rules both from an agronomic and from a regulation point of view. In fact, many constraints exist regarding agronomic principles, such as maximum replanting, botanical family constraints and crop rotation issues. One of the goals of this work is indeed that of evaluating the risks and benefits of following or not the best practices regarding crop rotation issues in the Mediterranean pedo-climatic context. Furthermore, we want to evaluate the effectiveness of public and private initiatives regarding sustainable agriculture. In fact, it is more and more important nowadays to face these challenges in the food supply chain, which is one of the most discussed industries when it comes to sustainability. In particular, we analyze two different initiatives, namely the Common Agricultural Policy by the European Union and “La Carta del Mulino” by Barilla Group S.p.A.. Both initiatives introduce economic incentives for the farmers following virtuous behaviors from a sustainability point of view. Practically, these behaviors are constraints increasing the complexity of the problem and the difficulty in the decision-making process. For this problem, we will give a formal characterization and study its complexity, also analyzing special cases. We will also present a network-flow based model to solve a special case of the problem and integer linear programming models developed to solve three variants accounting for different sustainability scenarios. Real-world data from 23 Italian farms were used in an extensive computational campaign. The analysis of the results shows that the models can be helpful tools for farmers to plan their production and for authorities to evaluate the effectiveness (and efficiency) of their sustainability initiatives. In Chapter 3, we discuss a problem concerning the sequencing of unreliable jobs on parallel machines. Even if the problem is not taken from a specific application, it may have several applications in real-world scenarios, such as in manufacturing and planning of complex computations on multi-processors computers. In this problem, we have n unreliable jobs providing a reward when successfully completed, but each job has a probability of not being carried out. We have m parallel identical machines at our disposal, and we want to schedule the jobs on the machines in order to maximize the total expected reward. To increase the probability of completing the jobs, we create m copies of each job and schedule each copy on a different machine. For this problem, we will present a complexity analysis showing that the problem is NP-complete for two machines. For the problem with two machines, we derived some theoretical properties and developed a quadratic integer programming model, a tabu search algorithm, and an upper bound based on the Three-Dimensional Assignment problem. A computational campaign on different sets of instances shows that the tabu search outperforms the model. Then we focused on the general case with m machines. In particular, we developed several heuristics and proved some theoretical results, including the worst case performance guarantee of two heuristics. We also devised a generalized tabu search algorithm and a new, improved, upper bounding scheme based on a relaxation of the problem. Computational experiments are performed for the new methods on the problems with two and three machines. The results show that good optimality gaps are reached on all the instances.