New swarm-based metaheuristics for resource allocation and scheduling problems

Laburpena

Optimization problems have been intensively studied, especially since the development of operations research and computer science. Nowadays a huge number of complex problems are NP-hard, which implies that they cannot be optimally solved in a reasonable amount of time if the size of the problem is too large. This is the case for the Vehicle Routing Problem (VRP) that consists in finding a set of routes to serve a list of customers with a specific fleet of vehicles; a brute force approach is not efficient if the amount of customers is too large. Another example is the Course Timetabling Problem whose objective is to find a timetable with no clashes for students and teachers and that considers, most of the time, a lot of additional constraints such as teacher availability or room capacity. Due to this complexity, several metaheuristics have been proposed to find near optimal solutions that go from basic strategies, such as random search, to more sophisticated approaches, such as bio-inspired metaheuristics. An important component of the latter is the Genetic Algorithm (GA), which applies the selection processes found in nature to the solutions of an optimization problem. Another important bio-inspired metaheuristic is the Ant Colony Optimization (ACO), which is based on the foraging behavior of ants. This dissertation is focused on how heuristic approaches and metaheuristics can be adapted to solve real optimization problems. The analysis and the adaptation of the ACO metaheuristic in particular is done for several combinatorial problems, among them Resource Allocation Problems and Scheduling Problems, such as Timetabling and VRP. Those problems are first modeled as Constraint Satisfaction Optimization Problems (CSOP). Then new heuristic algorithms, metaheuristics and hybrid metaheuristics are designed and applied to solve those CSOP. The results are then compared to different resolution methods such as GA or commercial tools in order to analyze their performance. One of the problems studied in this dissertation consists in allocating students to classes in Swiss secondary schools, where students have different profiles due to their level in some fields or to the elective courses they attend. The pedagogical objective is to have a high diversity of profiles within a class and similarity between classes. In order to achieve this goal, the problem is modeled as a Resource Allocation Problem, where students are resources. The Resource Allocation Problem is then solved in two different ways, with a standard solver for CSOP, and with ACO. Eight real datasets are used to compare their performance. ACO provides better solutions than the CSOP solver and in a shorter time. Results show that the pheromones used in ACO help to find better solutions in a much smaller amount of time. The same problem has been modeled as a many-objective optimization problem, where the composition of classes combines pedagogical objectives with resource and economic objectives. In a many-objective problem, usually objectives are not compatible and improving one objective will penalize one or more of the other objectives. Therefore, there are several optimal solutions, whose set is called the Pareto front. To solve this many-objective problem, we adapt three approaches based on ACO, Harmony Search, and GA (NSGA-II). Eight real datasets from different schools are used and all approaches find several non-dominated solutions for each of them. Two methods are proposed to compare their performance, a simple one with a direct hypervolume comparison and a smoothing method where Pareto fronts are approximated with several runs for each approach. In four datasets, the three approaches are competitive, in the other four datasets NSGA-II outperforms the other approaches. Resource allocation and timetabling problems can both be found in universities where students can select courses before or after the timetabling is done. In this dissertation, both problems, seat allocation and timetabling, are modeled separately and combined as CSOP. Two algorithms are designed and implemented to find a solution to both problems simultaneously maximizing the satisfaction of students using a CSOP solver and ACO for the timetabling problem. The results of both algorithms are then compared. Three real datasets from the Ecole Hôtelière de Lausanne have been used to carry out a complete experimental analysis. High quality solutions are obtained in a few minutes with both approaches; those solutions are currently used at the Ecole Hôtelière de Lausanne. Another type of problem described in this dissertation is a complex VRP with many different constraints: time windows, heterogeneous fleet, multiple depots, multiple routes and incompatibilities. Five different approaches are presented and applied to fifteen real datasets. Those approaches are based on ACO and GA and are applied in their standard formulation and combined as hybrid metaheuristics, ACO-GA and GA-ACO. The results are compared regarding quality and computation time with two commercial tools. Considering the number of customers that cannot be served, one of the tools and ACO-GA outperform the others. Considering the cost, GA and GA-ACO provide better results. The computation time needed for one iteration is much better in GA and GA-ACO.