Abstract: In the Generalized Assignment Problem (GAP), tasks must be allocated to machines with limited resources, in order to minimize processing costs. This problem has several industrial applications and often appears as a substructure in other combinatorial optimization problems. We propose a hybrid method inspired by Scatter Search metaheuristic, that efficiently generates a pool of solutions using a Tabu list criteria and an Ejection Chain mechanism. Common characteristics are extracted from the pool and solutions are combined by exploring a restricted search space, as a Binary Programming (BP) model. This method was implemented as a parallel approach to run in a Graphics Processing Unit (GPU). Experimental results show that the proposed method is very competitive to the algorithms found in the literature. On average, a gap of 0.09% is obtained over a set of 45 instances, when compared to lower bounds. Due to the integration of the method with an exact BP solver, it was capable of proving the optimality of small size instances, also finding new best known solutions for 21 instances. In terms of computational times, the proposed method performs on average 8 times faster than literature, also indicating that the proposed approach is scalable and robust for practical applications.

Abstract: The Probabilistic Traveling Salesman Problem (PTSP) is an extension of the classical Traveling Salesman Problem (TSP). The main difference is the stochastic presence of the customers, that is, the number of them to be visited each time is a random variable, where each customer associates with a given probability of occurrence. The resolution of problem consists in finding an a priori tour visiting all customers which minimizes the expected length over all possibilities. In this paper, we propose an exact algorithm for the solution of the PTSP. In this context, we derive new expressions for the lower bound and transitional, permanent evaluations as well as the mechanism of separation. The numerical results demonstrate the advantage of the proposed evaluations.

Abstract: There are some rules for 3,000 V DC electrification in the network ruled by the Spanish Railway Infrastructure Authority (ADIF). As far as we know, the correction of the installations is nowadays manually checked by an expert, as used to be done for expert systems years ago. We propose a computer tool that is an aid for the expert in checking that the positioning of the insulators, circuit breakers, load disconnectors, feeders,... fulfills the requirements established. The computer tool allows the expert to automatically check the sections fed in the different scenarios proposed in the requirements.

Abstract: We introduce a novel approach for a competitive facility location problem in which multiple competitors aim to gain market share. The problem is called the Competitive Maximal Covering Location Problem (CMCLP) based on the classical Maximal Covering Location Problem. Typically, the CMCLP is modeled as a Stackelberg game in which the first player and then the other one locate a fixed number of facilities. On the other hand, the present work considers multiple competitors, and the objective is on discovering a set of the competitors’ decision tuples that are not dominated by any other decision tuples in the solution space. Thereby, our modeling paradigm aims to help competing firms understand tradeoffs when they engage in negotiations. We introduce a mathematical model for the CMCLP with two competitors and a genetic algorithm to solve the problems with multiple competitors. We present computational experiments to demonstrate that the proposed algorithm is able to approximate the true Pareto front.

Abstract: Engineering design is typically a complex process that involves finding a set of designs satisfying various performance criteria. As a result, optimisation algorithms dealing with only single-objective are not sufficient to deal with many real-life problems. Meanwhile, scientific workflows have been shown to be an effective technology for automating and encapsulating scientific processes. While optimisation algorithms have been integrated into workflow tools, they are generally single-objective. This paper first presents our latest development to incorporate multi-objective optimisation algorithms into scientific workflows. We demonstrate the efficacy of these capabilities with the formulation of a three-objective aerodynamics optimisation problem. We target to improve the aerodynamic characteristics of a typical 2D airfoil profile considering also the laminar-turbulent transition location for more accurate estimation of the total drag. We deploy two different heuristic optimisation algorithms and compare the preliminary results.