ABSTRACT. Urban freight transport is becoming increasingly complex due to an increment in the number of journeys and the associated volume and frequency. These transport activities have a significant negative impact on the environment and population welfare, which motivates decision-makers to study the transport efficiency from a sustainability perspective. This work proposes a metaheuristic approach for solving the multi-depot vehicle routing problem with the goal of minimizing the distribution costs considering sustainability, which include a cost per accident rate and carbon emissions. A computational experiments is presented.

ABSTRACT. We propose an Adaptive Large Neighborhood Search metaheuristic to solve a vehicle reloca-tion problem arising in the management of electric carsharing systems. The solution approach, aimed to optimize the total profit, is tested on two real-like benchmark sets of instances and com-pared with both a previous Ruin and Recreate metaheuristic and the optimal results obtained through a Mixed Integer Linear Programming formulation, when available.

ABSTRACT. The concept of vendor managed inventories (VMI) constitutes a promising supply chain management concept. By centralizing inventory management and route planning decisions, overall value chain costs can be reduced. From an optimization perspective, VMI strategies result in the complex inventory routing problem (IRP). This work develops a fast and efficient variable neighborhood search metaheuristic to solve the IRP in an agricultural supply chain. A case study about the integration of real-time animal feed level monitoring systems developed by UBIKWA into the metaheuristic solving methodology is presented.

ABSTRACT. The technician routing problem with conventional and electric vehicles (TRP-CEV) consists in designing service routes taking into account the customers' time windows and the technicians' skills, shifts, and lunch breaks. In the TRP-CEV routes are covered using a fixed and heterogeneous fleet of conventional and electric vehicles (EVs). Due to their relatively limited driving ranges, EVs may need to include in their routes one or more recharging stops. In this talk we present a parallel matheuristic for the TRP-CEV. The approach works in two phases. In the first phase it decomposes the problem into a number of ``easier to solve'' vehicle routing problems with time windows and solves these problems in parallel using a GRASP. During the execution of this phase, the routes making up the local optima are stored in a long-term memory. In the second phase, the approach uses the routes stored in the long-term memory to assemble a solution to the TRP-CEV. We discuss computational experiments carried on real-world TRP-CEV instances provided by a French public utility and instances for the closely-related electric fleet size and mix vehicle routing problem with time windows and recharging stations taken from the literature.

ABSTRACT. This paper studies the flexible open shop scheduling problem with travel times between workstations and sequence dependent setup times. We study the performance of a simple but yet effective genetic algorithm (GA) algorithm. Our contribution is that we propose a new schedule generation scheme that intelligently reduces the search space. The performance of the algorithm is tested on two sets of instances from the literature. The results reveal that the schedule generation scheme has the greatest influence on performance and that the proposed GA exhibits very competitive performance in comparison with other algorithms that use the same solution representation on classical open shop instances.

ABSTRACT. We present an original migrating birds optimization (MBO) algorithm to minimize the total tardiness and solve the permutation flowshop with sequence dependent setup times. Although this scheduling problem presents several real aspects, we found very few papers in the literature that deal with this problem. Our MBO algorithm uses a tabu-list, a restart mechanism and an original leader selection process. Computational experiments show that the proposed MBO significantly outperforms the best algorithms from the literature. We extend the experimentation to the weighted problem and our algorithm also outperforms the reference one.

ABSTRACT. The no-wait flowshop scheduling problem is a variant of the classical permutation flowshop problem, with the additional constraint that jobs have to be processed by the successive machines without waiting time. To efficiently address this NP-hard combinatorial problem we conducted an analysis of the structure of good quality solutions. This study shows that the No-Wait specificity gives them a common structure: they share identical sub-sequences of jobs. After a discussion on the way to identify these sub-sequences, we propose to exploit them into the well-known Iterated Greedy algorithm. Experiments are conducted on Taillard’s instances. The experimental results show the proposed approach is efficient and robust, and is able to find out new best solutions for all the largest instances.

ABSTRACT. This paper proposes a Heuristic Algorithm based on genetic algorithm to solve the no-wait flowshop scheduling problem with the makespan criterion. The problem has important applications in industrial systems. The main contribution of this study is due to the fact that our heuristic was used with a local search which intensifies the search to find good solutions. In addition, the algorithm is not hybridized as does most of the resolution methods used recently to solve the problem and was more effective than many algorithms applied to the specific problem. The technique took into account the diversification and intensification of the search to solve the problem. Computational experiments are reported for the literature instances and the obtained results are compared with other techniques.

ABSTRACT. Cross-docking is a logistics strategy in which freight is unloaded from inbound vehicles and (almost) directly loaded into outbound vehicles, often without storage. The Cross-Docking Assignment Prob-lem (CDAP) uses a terminal (facility, depot or distribution center) to unload products incoming from origins and to reload these products into trucks outgoing to specific destinations. The goal is to find the assignment of the origins to the indoors and the destinations to the outdoors that minimizes the sum of distance traveled when moving products from indoors to outdoors while satisfying the capac-ity constraints of indoors and outdoors [3, 5]. Since CDAP is an NP-Hard optimization problem, we develop a Probabilistic Tabu Search heuristic with multiple neighborhood structures to solve it. The proposed algorithm is evaluated on a total of 50 benchmark instances from the literature. Computa-tional results disclose that the proposed tabu search method outperforms recent state-of-the-art ap-proaches. In particular, our approach is able to reach 46 best-known solutions and discover 3 new best known solutions.

ABSTRACT. The Uncapacitated Facility Location Problem (UFLP) consists of choosing a subset of facilities to be opened from a set of potential candidates, and allocating each customer to an opened facility in order to meet the customers’ demands. The objective is to minimize the overall cost including the costs of opening facilities and the costs of allocations. In this work we propose a simple multi-wave algo-rithm for solving the UFLP and report experimentation that shows it outperforms all previous meth-ods on a standard set of benchmarks for this widely-studied class of problems.

ABSTRACT. This paper presents a Tabu Search method with Path Relinking for solving the quadratic assignment problem (QAP). Our approach leverages advances made in solving the unconstrained quadratic binary program (UBQP) by embedding procedures that implicitly enforce the QAP constraints into the UBQP model. Substantial computational experience is presented, along with comparisons made with the performance of the well-established GRASP with Path Relinking algorithm, widely considered one of the best approaches from the literature for solving QAP problems. We give a detailed discussion of the results and look ahead at extensions for our future work in this area.

ABSTRACT. Given two sets of vertices V and W, where each vertex in V covers a subset of W, the multi-vehicle covering tour problem asks to determine a number of vehicle routes on a subset of V so as to minimize the total distance under the constraint that every vertex in W must be covered by vertices in the routes. We propose a tabu search algorithm that features two procedures: one consists of three operations to remove or insert vertices from or into a route; the other is path reconstruction that replaces a partial path with an optimal one, for which we propose a dynamic programming algorithm. During the search, we evaluate solutions by a penalized cost function, in which penalty weights of uncovered vertices in W are added to the total distance, and we incorporate a mechanism to adaptively control the values of these penalty weights. The computational results on benchmark instances show that our algorithm performs better than existing methods.

ABSTRACT. Consider a graph G = (V, E) with a non negative weight assigned to each vertex v ∈ V and also a threshold t(v) ∈ N, such that a vertex v becomes active if t(v) of its neighbors are active. The Weighted Target Set Selection Problem consists in finding a subset S ⊆ V of vertices such that activating the vertices in S activates all nodes in the graph and the sum of weights of vertices v ∈ S is minimum. This problem has been proven to be NP-hard and has many applications in social network analysis and natural phenomena. This paper proposes the use of the metaheuristic GRASP to solve this problem. Experiments were performed in real networks and the results show the effectiveness of the proposed method.

ABSTRACT. Greedy Randomized Adaptive Search Procedure (GRASP) is one of the best-known metaheuristics to solve hard combinatorial optimization problems. Its construction phase relies on the well known Restricted Candidate List (RCL) approach. This paper proposes an alternative construction method, using a biased randomization technique. A set of experimental results is presented to show the effectiveness of the proposed algorithm.

ABSTRACT. One of the classical problem in combinatorial optimization is the Max Clique, which finds different applications in a very heterogeneous context. Max cut-clique is a recently proposed variant of the best-known max clique. Given its computational intractability nature, in this paper we propose a very competitive hybrid meta-heuristic based on a GRASP and a Phased Local Search and compared it with state-of-the-art scientific literature. The initial computational experience indicates that our proposal finds efficiently near-optimal solutions.

ABSTRACT. Given a set of nodes and the distances between them, the traveling salesman problem (TSP) consists in finding the shortest route that visits each node exactly once and returns to the first. The Steiner traveling salesman problem (STSP) is a variant of the TSP that assumes that only a given subset of nodes must be visited by a shortest route, eventually visiting some nodes and edges more than once. In this paper, we extend some classical TSP constructive heuristics and neighborhood structures to the STSP variant. In particular, we propose a reduced 2-opt neighborhood and we show that it leads to better results in smaller computation times. Computational results with an implementation of a GRASP heuristic using path-relinking and restarts are reported. In addition, a set of test instances and best known solutions is made available for benchmarking purposes.

ABSTRACT. This paper presents a method to combine a discrete-event simulation model of a logistics network with a deep reinforcement learning agent. The agent applies different actions to the logistics network in order to learn a strategy to improve the cost structure and the performance of the logistics network. The return for the agent is derived from the costs and the performance of the logistics network which is measured in terms of logistics costs and β service level. Possible actions comprise the relocation of inventory and the adjustment of transport relations. The authors developed a method to represent the state of the simulation model with an image generated from the simulation input data and used a well-known deep Q-learning algorithm with a convolutional neural network to train the agent.

ABSTRACT. We present a simulation-based optimization approach towards the transit network frequencies setting problem (TNFSP). The underlying simulation model utilizes real world data provided by our industrial partner, the Viennese public transportation provider. Vienna, as many other metropolitan areas, has to deal with population growth. Urbanization, efforts to decrease carbon emission, improvement of the residents' quality of life, tourism, etc. call for frequent re-evaluations whether adaptation measures are necessary or not. Economic factors (i.e. capital and operational expenditure) clearly contrast the goal of passenger satisfaction (i.e. service level). In order so solve the headway optimization problem for the Viennese subway system, we apply evolutionary algorithms (genetic algorithms and evolutionary strategies) as well as grid search.

ABSTRACT. Tooling machine simulation enables an iteratively improved verification of NC-programs. The state of the art is understood as follows: The setup position of a workpiece and its impact on the required cut-ting work as well as tool change processes are excluded. We want to consider these impacts and intend to develop a method that reaches an automatic optimal setup position, taking into consideration the initial setup position. In compliance with the methods for design of experiments (DoE) (see [3]) a systematic procedure occurs by approaching the optimum without needing a large number of uncon-trolled simulation runs. The idea arose to combine rapidly-converging metaheuristics with virtual tooling simulation mod-els. Initial implementation experiments lead to an excessive number of simulation jobs caused by the 1:1-validation of each solution candidate for the metaheuristic. Thus, the metaheuristic was combined with a pre-processing element in order to calculate the best cycle time for the workpiece setup using an assigned NC-program configuration. The pre-processing element as fitness component is given by a NC-parser. Consequently, the method is divided into two phases: For each workpiece position a cycle time es-timation depending on the workpiece position and NC-program configuration as well as a collision control are performed. The collision detection is provided by the simulation model and represents the second phase – only the first phase is discussed in this contribution. An automatic NC-program ad-justment is also offered.

Consequently, the method is divided into two phases: For each workpiece position a cycle time es-timation depending on the workpiece position and NC-program configuration as well as a collision control are performed. The collision detection is provided by the simulation model. An automatic NC-program adjustment is also offered.

ABSTRACT. This research addresses the short-term scheduling problem in a Permutation Flow Shop environment, considering stochastic processing times, through a multi-objective approach that generates Pareto Frontiers for Expected and Standard Deviation of Total Tardiness. A simheuristic algorithm is designed by combining the Tabu Search Metaheuristic and the PAES algorithm with a Monte Carlo Simulation process. The effectiveness of the proposed simheuristic is evaluated for two different probability distributions of the stochastic parameter (lognormal and uniform distributions) and three coefficients of variation (0.3, 0.4, and 0.5). The results are compared with the simulated solutions given by the Tabu Search algorithm programed for the deterministic case. An analysis of variance is also carried out, with 180 benchmark instances in which three factors are considered (solution method, probability distribution and coefficient of variation). Results show that, in 176 of the 180 instances, the proposed simheuristic gives a significantly better result than the comparison benchmark for both objectives under analysis.

ABSTRACT. El aprendizaje de redes Bayesianas (RBs) a partir de datos es una tarea que se puede plantear desde el punto de vista de la optimizaci\'on combinatoria. La forma habitual de hacerlo es definir una funci\'on de puntuaci\'on que mide la calidad de una RB candidata con respecto a los datos de partida. El espacio de b\'usqueda habitual es el de los grafos dirigidos con la restricci\'on fuerte de preservar la aciclicidad del grafo (DAGs). Sin embargo, atendiendo a la sem\'antica de independencia condicional entre variables que codifica la estructura de una RB existe la posibilidad de plantear espacios de b\'usqueda alternativos. Uno de ellos es el del espacio de grafos esenciales ("esential graphs") que codifican las clases de equivalencia de todos los grafos que representan el mismo conjunto de independencia condicional. De esta manera evitamos movernos entre grafos que representan soluciones de calidad equivalente y no introducimos algunos sesgos en la b\'usqueda debido a los operadores espec\'{\i}­ficos para el espacio de b\'usqueda en DAGs.

En este articulo vamos a utilizar algunas metaheur\'{\i}­sticas locales para adaptarlas al problema del aprendizaje de RBs en el espacio de b\'usqueda de grafos esenciales y comprobaremos su rendimiento mediante una bater\'{\i}­a de experimentos.

ABSTRACT. La minería de patrones emergentes es una técnica agrupada dentro de los sistemas descriptivos para aprendizaje supervisado cuyo objetivo es la descripción de tendencias emergentes en el tiempo y la caracterización de diferentes clases o grupos de variables. Entre las diferentes metodologías utilizadas para resolver este problema, los sistemas difusos evolutivos han demostrado ser un enfoque muy prometedor para la tarea. No obstante, la representación del conocimiento en estos algoritmos puede ser modificada con el fin de obtener mejores resultados descriptivos. En este trabajo se presenta una comparativa de las diferentes representaciones del conocimiento más utilizadas a lo largo de la literatura, con el objetivo de determinar aquella que obtiene los mejores resultados descriptivos. Los resultados del estudio experimental muestran el poder descriptivo de estas representaciones, resaltando especialmente la capacidad descriptiva de las reglas en forma normal disyuntiva.

ABSTRACT. Durante años se han organizado competiciones de optimización real en el congreso IEEE de Computación Evolutiva. En dichas competiciones los organizadores definen un benchmark y unas condiciones de experimentación que deberán seguir las propuestas enviadas, y se comparan los resultados obtenidos por cada una de ellas. Es una forma excelente de valorar qué algoritmos (y planteamientos) parecen mejorar al resto, pudiendo servir de guía para avanzar en el área. Desafortunadamente, al proponerse cada año un nuevo benchmark, los resultados entre competiciones no son comparables entre sí, por lo que no hay garantía de que los ganadores de unos años sean mejores que los de años anteriores. En este trabajo presentamos una comparación entre ganadores de distintas competiciones usando los diferentes benchmarks, para analizar sus resultados y establecer qué algoritmos parecen los más competitivos en ellos, y averiguar si efectivamente se está produciendo un avance en las propuestas enviadas cada año.

ABSTRACT. This paper analyzes the fleet mixed vehicle routing problem with backhauls (FSMVRPB), a rich and realistic variant of the popular vehicle routing problem in which both delivery and pick-up customers are served from a central depot using a heterogeneous and configurable fleet of vehicles. After a literature review on the issue and a detailed description of the problem, a solving approach based on a multi-start biased-randomized heuristic is proposed. Our algorithm uses an iterative method that relies on solving a series of smaller instances of the homogeneous-fleet version of the problem and then using these sub-solutions as partial solutions for the original heterogeneous instance. In order to better guide the exploration of the solutions space, the algorithm employs several biased-randomized processes: a first one for selecting a vehicle type; a second one for sorting the savings list; and a third one to define the number of routes that must be selected from the homogenous-fleet sub-solution. The computational experiments show that our approach is competitive and able to provide 20 new best-known solutions for a 36-instance benchmark recently proposed in the literature.

ABSTRACT. In this paper, we discuss multi-trip vehicle routing problems (VRPs) with backhauls. Additional constraints such as time windows, release dates for goods transported to linehaul customers, and latest return times for goods associated with backhaul customers are taken into account. To the best of our knowledge, this VRP is not discussed in the literature so far. Since the considered rich VRP is NP-hard, we propose a memetic algorithm to tackle large-sized problem instances in a rea-sonable amount of time. Based on computational experiments using benchmark instances from the literature for special cases of our problem, we show that the proposed memetic algorithm is com-petitive with other metaheuristics from the literature or even outperforms them. Moreover, we present and discuss computational results for new randomly generated problem instances.

ABSTRACT. We address a tactical time slot management problem for attended home delivery services. In this problem, delivery time slots must be assigned to geographical zones over a horizon of several periods (days). The selection of time slots is based on the solution of a tactical vehicle routing problem, in which the estimated demand of a zone, obtained from historical data, can be split between two or more vehicles. We propose an adaptive large neighborhood search heuristic to solve this problem. We report computational results on instances with up to 200 zones.

ABSTRACT. Motivated by a research on collaborative transportation between various parties, the clustered pick up and delivery problem arises from the search for solutions from a completely centralized point of view. It concerns two decision problems, the scheduling of requests to inter-cluster transportation vehicles and the service of their pick ups and deliveries in intra-cluster routes. The pick up and the delivery customers of each request are located in different clusters, so that each request must be transported between the two clusters. A multi depot approach is considered, along with time windows for the customers and a planning period of several days. The objective is to minimize the total costs of the transportation planning. We solve the problem by means of using an Adaptive Large Neighborhood Search (ALNS) scheme. We build two different approaches of the ALNS, which we apply in three different ways to see how it behaves in this two decision setting. Computational experiments are performed for a benchmark of self generated instances.

ABSTRACT. The distributed permutation flowshop problem is an extension of the well studied flowshop setting in which n jobs have to be processed in m machines that are laid out in series in a production floor. Each job has to go through each machine in the same order. The distributed variant adds an interesting situation which appears in larger companies that have several production facilities. Therefore, the problem includes an additional decision dimension so as to which factory each job should be assigned to. As a result, in the distributed permutation flowshop problem there are f factories and we have to decide the assignment of jobs to factories and then to schedule all jobs assigned to each factory. This generalized flowshop was first proposed in 2010 and a myriad of papers have been published since. In this short work-in-progress note we summarize the latest developments and some new ideas around Iterated Greedy (IG) methods with great promise and with the potential of producing new state-of-the-art results for the makespan minimization criterion.

ABSTRACT. In this paper, we propose a multi-objective optimisation model and the predictive-reactive approach that uses Iterated Greedy algorithm for the robust dynamic permutation flow shop scheduling under different types of real-time events including machine breakdown and new job arrival. The multi-objective model considers three important measures, namely; utility, stability and robustness. The results illustrate that the performance of the new model is better than the bi-objective model [1] and the classical makespan model.

ABSTRACT. The majority of the scheduling literature carries a common assumption that machines are the only resources. However, this assumption may not be true in real industry settings, Since, jobs for their processing besides machines may require additional resources such as raw materials, money or energy. We refer to these resources as non-renewable or consumable or financial resources. When the execution of jobs depend on the availability of both renewable (machines) and non-renewable (raw materials) resources and each of which being subject to different constraints (resources availability), the resulting scheduling problems become very difficult and hard to solve relative to its counterpart that is subject to just one type of resource. So, in this paper we investigate a permutation flow shop scheduling problems, where non-renewable resources constraints are considered. Since this problem is proven to be NP-hard, a classical metaheuristics based on genetic algorithm and particle swarm optimization algorithms are developed and compared with the objective of minimizing the makespan. A computational study is conducted to analyze the efficiency of this approaches on different scale problems instances.

ABSTRACT. This short note gathers some promising initial results obtained with Automatic Algorithm Design (AAD) and Configuration (AAC) tools. The idea is to feed a large number of components and operators into a flexible framework able to combine them. The result is a capable metaheuristic, automatically constructed, able to compete, or even surpass, state-of-the-art methods. We show results for different optimization criteria in hybrid flexible flowshop problems.

ABSTRACT. In recent years, a growing interest has been observed in research on RNA (ribonucleic acid), primarily due to the discovery of the role of RNA molecules in biological systems. They not only serve as templates in protein synthesis or as adapters in the translation process, but also influence and are involved in the regulation of gene expression. The RNA degradation process is now heavily studied as a potential source of such riboregulators.

In this paper, we consider the so-called RNA Partial Degradation Problem (RNA PDP). By solving this combinatorial problem, one can reconstruct a given RNA molecule, having as input the results of the biochemical analysis of its degradation, which possibly contain errors (false negatives or false positives). From the computational point of view the RNA PDP is strongly NP-hard. Hence, there is a need for developing algorithms that construct good suboptimal solutions. We propose a heuristic approach, in which two tabu search algorithms cooperate, in order to reconstruct an RNA molecule. Computational tests clearly demonstrate that the proposed approach fits well the biological problem and allows to achieve near-optimal results.

ABSTRACT. To be competitive in the global market, companies must be prudent in the use of their resources. This research considers a parallel scheduling environment where choosing in-house machines and/or subcontractors as resources to perform the orders/jobs is the main objective. Processing time (or cost) of a job to be performed by different machines or subcontractors can be different. Furthermore, if a machine or a subcontractor is chosen to perform a set of orders there is a one-time fixed cost (in the case of subcontractor it can be considered transportation cost) that depends on the machine or subcontractor. The scheduling criteria is to choose a subset of k machines and/or subcontractors to do all orders/jobs while minimizing the sum of the total workload and total fixed costs. The complexity of the problem is discussed and shown to be NP-hard. An efficient tabu-genetic algorithm that solves large-scale problems in fraction of a second of CPU time is presented and an extensive computational experiment is provided.

ABSTRACT. Given a graph G = (V,E), the Vertex Bisection Minimization Problem (VBMP) aims to find a partition of the vertex set V into two disjoint subsets B and B′of equal cardinalities such that the cardinality of subset SB ⊆ B is minimized, where SB consists of all the vertices in B that are adjacent to at least one vertex in B′. Considering the theoretical intractability and a number of important applications of VBMP, this paper presents an effective Variable Neighborhood Tabu Search approach (VNTS), which employs a k-add&reduce move operator for neighborhood exploration to transition between feasible and infeasible search spaces. Experimental studies on a set of 35 VBMP instances reveal that the proposed algorithm is highly competitive with the state-of-the-art algorithms.

ABSTRACT. This article describes a hybrid algorithm (PSO TS) that uses Particle Swarm Optimization (PSO) and Tabu Search (TS) to solve the Maximum Diversity Problem (MDP). The MDP is a problem in the area of combinatorial optimization which aims to select a preset number of elements of a given set such that the sum of the differences between the selected elements is the highest possible. The PSO approach simulates the behavior of a flock of birds in flight with its random movement locally, but also globally determined, to find the local maximum. The use of PSO TS achieves the great majority of the best results for known instances testing according to literature, thus demonstrating to be competitive with the best algorithms in terms of quality of the solutions.

ABSTRACT. The Order Batching Problem is an optimization problem consisting in minimizing the total time needed to collect a group of orders received in a warehouse. The problem itself can be divided into two sub-problems: (i) grouping the orders into batches and (ii) finding a route to collect all the items that compose the orders within the same batch. In this paper, a variant of the problem is approached. Particularly, we tackle the Online Order Batching Problem where the orders arrive to the warehouse while the collecting process has already begun. We consider the special case where there is a single picker and the aisles of the warehouse are placed in a parallel layout. In this work we compare different routing strategies and we explore an algorithm based on the Variable Neighborhood Search methodology to tackle the batching task.

ABSTRACT. Continuous GRASP (C-GRASP) efficiently solves linearly and nonlinearly-constrained continuous global optimization problems. In this paper, we propose a generalized GRASP for its mixed version: the mixed-integer nonlinear programming (MINLP) problems. Experimental results illustrate its effectiveness on some functions from MINLPLib.

ABSTRACT. With limited financial resources, decision-makers in firms and governments face the task of selecting the best portfolio of projects to invest in. Metaheuristics have been employed for solving large NP-hard instances of the project portfolio selection problem (PPSP). However, this work further analyzes a stochastic version of the PPSP: the goal is to minimize the expected net present value of the inversion, while considering random cash flows and discount rates in future periods and a rich set of constraints - including the maximum risk allowed. To solve this stochastic PPSP, our approach integrates a variable neighborhood search metaheuristic with Monte Carlo simulation. A series of computational experiments contribute to validate our approach and illustrate how the solutions vary as some of the user-defined inputs are modified.

ABSTRACT. The Graph Edit Distance (GED) is a well-known problem to compare graphs. Solving the GED problem allows computing a dissimilarity measure between graphs that normally represent objects and patterns. It is known as well to be very flexible and can work on any type of graphs. $ GED^{EnA} $ (Edges no Attributes) is a sub-problem of GED that deals with a special type of graphs where edges do not carry attributes. Both are modeled as minimization problems and proven to be NP-Hard, they are exponential in the number of vertices of graphs. A great effort has been made to provide heuristic approaches with a compromise between the execution time and the solution quality. As well, they are addressed by means of mathematical programming tools to generate Mixed Integer Linear Program (MILP) models. In the present work, an heuristic is proposed to deal with $ GED^{EnA} $ problem, and is called Local Branching. Mainly, it takes a MILP model and modifies it by adding additional constraints, to define neighborhoods in the solution space which will be explored using a black-box solver. Repeating this process leads to exploring different neighborhoods in the solution space in order to find efficient solutions. Lastly, the proposed heuristic is evaluated considering two factors: its computational time and solution quality against literature heuristics, and the solution quality and closeness to the optimal.

ABSTRACT. An appropriate visualization of multiobjective non-dominated solutions is a valuable asset for decision making. Although there are methods for visualizing the solutions in the design space, they do not provide any information about their relationship. In this work, we propose a novel methodology that allows the visualization of the non-dominated solutions in the design space and their relationships by means of a network. The nodes represent the solutions in the objective space while the edges show the relationships among the solutions in the design space. Our proposal (called moGrams) thus provides a joint visualization of both objective and design spaces. It aims at helping the decision maker to get more understanding of the problem so that (s)he can choose the most appropriate and flexible final solution. moGrams can be applied to any multicriteria problem in which the solutions are related by a similarity metric. Besides, the decision maker interaction is facilitated by modifying the network based on the current preferences to obtain a clearer view. To show both the usefulness and versatility of moGrams, our methodology is applied to the Time and Space Assembly Line Balancing Problem. The results exhibit interesting characteristics of our methodology for visualizing and analyzing solutions of multiobjective problems.

ABSTRACT. We aim at minimizing the dispersion of ergonomic risk of workstation and the risk of the critical workstation in a mixed-model assembly line. To achieve this goal, we evaluate two assembly line balancing Mixed Integer Linear Programming Models: MILP-1 that minimizes the maximum ergonomic risk and MILP-2 that minimizes the average absolute deviations of ergonomic risk. Through a case study we compare the results of the two MILP and we confront them with a GRASP procedure. The results given by GRASP are very competitive.

ABSTRACT. La planificación de movimientos es un área de investigación básica en robótica, sobre todo desde que los robots se convirtieron en una parte esencial en muchos campos de aplicación tales como, por ejemplo, las industrias médica y electrónica, e incluso la biología computacional o la animación por ordenador. La importancia de este problema se hace evidente cuando se intenta planificar una trayectoria para un sistema robótico con un gran número de grados de libertad (DOF), como es el caso de las manos mecánicas o los sistemas antropomorfos. Además, a veces no sólo se requiere que la trayectoria esté libre de colisiones, sino también que optimice alguna función de coste (por ejemplo, el tiempo de ejecución o su longitud). El algoritmo Rapidly-Exploring Random Trees (RRT) es ampliamente utilizado debido a su elevada eficacia para planificar movimientos incluso para sistemas con muchos DOF o restricciones. Además, variantes del RRT permiten encontrar trayectorias óptima (o cercanas a la óptima), acorde a una medida de calidad dada. El objetivo de este trabajo es estudiar el estado de la técnica en la planificación de movimientos y evaluar diferentes planificadores basados en el algoritmo RRT para obtener trayectorias \'optimas de sistemas robóticos.

ABSTRACT. Maintenance operations may present a significant impact on the yield of a manufacturing fa-cility. While certain types of manufacturing processes, i.e. preventive and predictive maintenance, can be scheduled in advance and may influence production efficiency on a deterministic way, corrective maintenance presents stochastic behavior. Hence, the management of a manufacturing facility should take into account the influence of equipment downtime due to corrective mainte-nance tasks. An industrial case study is presented, aimed at selecting the optimal production strat-egy for maximizing the yield under different scenarios. In order to assess the impact of corrective maintenance in production operations, a model of both, the manufacturing facility and the sto-chastic behavior of corrective maintenance operations, has been developed. The core of the deci-sion-making tool, developed for the choice of the best manufacturing strategy is based on a sim-heuristics approach, where the statement of an optimization problem is followed by a solution search algorithm guided by a genetic algorithm and complemented by discrete event system (DES) and Montecarlo simulations.

ABSTRACT. In this work, we are developing a hybrid method driving a core ILP solver with an iterative heuristic for the train unit scheduling optimization problem, which is formulated as an integer multi-commodity flow problem. This approach aims at reducing the problem to a minimal size but still retaining all the essential components for an optimal solution. This research is focussed on two aspects, (i) creation of an initial feasible solution, (ii) iterative improvement on a minimal sized problem extracted from incumbent best solution(s).

ABSTRACT. In urban areas, mainly in large urban centers, the diversity of transport modes has increased with the aim of improving the human mobility, and of making it more efficient. The Multimodal Transport Problem proposes strategies to optimize routes benefits from an interconnection of transport modes. Our approach is to implement a solution to this problem based on meta-heuristics techniques which handle the problem with multiples objectives. The algorithm was based on one of the most representative proposals of the state of the art on Evolutionary Multi-Objective Optimization: Non-dominated Sorting Genetic Algorithm II (NSGA-II) [7].

ABSTRACT. This work introduces a logistical problem occurring in and between two clusters (cities), where packages have to be transported between those cities. Within a city they are transported by small short-haul (SH) vehicles, while inter-city transport is handled by long-haul (LH) vehicles (train,plane or truck) that operate either on a fixed or on a flexible schedule. We propose a hybrid solution approach based on the savings algorithm, the pilot method and a commercial MIP solver. Preliminary computational results are presented and future extensions of the problem formulation and the solution method are discussed.

ABSTRACT. The optimal scheduling of the production tasks in a mill for animal feed production can be modeled as a no-wait flow shop problem with setup times. The no-wait condition ensures that animal feed is produced in a sequential manner without waiting times among different processes. Setup times which vary according to the previous feed produced are required to express the fact that some cleaning activities or readjustments in the processing machines may be required depending on the last feed produced. This problem is solved with an Iterated Local Search metaheuristic with special local search procedures devised to guide the search of this rich flow shop problem. Initial results tested on some instances of the Taillard's benchmark show promising results.

ABSTRACT. In this work the unrelated parallel machine scheduling problem with one additional resource to minimise the makespan is studied. Two strategies are proposed: the first one is based on considering the resource constraint during all the solution construction process. The second starts from several assignment rules without considering the resource constraint and repairing the non feasible assignments in order to obtain a feasible solution from the availability of the resource point of view. Several computation experiments are carried out under an extensive benchmark of instances. From these results we can conclude that the second strategy shows a better performance, especially from the efficiency point of view.

ABSTRACT. We consider the problems featured by two agents, A and B. Agent A is associated with the whole set of jobs whilst agent B is associated with a subset of jobs. Each agent aims at minimizing either the maximum or the total completion times of its assigned jobs. Considering parallel machines environment, the goal is to find the best compromises between the requirements of the agents. These problems belong to multi-agent scheduling problems. Such a class has drawn a significant interest to researchers in the area of scheduling and operational research. Given that the studied problems are NP-hard, we propose a genetic algorithm (NSGA-II) to generate approximated Pareto fronts. Using epsilon-constraint approach we propose an integer programing formulation that allow us to obtain the exact Pareto front for each problem. Experiments are conducted to analyze the performance of such methods compared to exact ones. Results indicate that the genetic algorithm provides high quality Pareto fronts and is computationally efficient.

ABSTRACT. In this paper, we present a hybrid memetic algorithm (HMA) for solving the parallel machine scheduling problem with sequence dependent deteriorating effects to minimize the makespan. Based on the framework of evolutionary algorithms, our HMA integrates a powerful compound neighbourhood search procedure, a uniform crossover operator, and a quality and distance based replacement rule for population updating. Assessed on two sets of 1800 benchmark instances, HMA achieves highly competitive results in terms of both solution quality and computational efficiency. Specifically, for the 900 small benchmark instances, it obtains the optimal solution for all of them in 0.051 milliseconds on average with a hit ratio of 100\%. For the 900 large benchmark instances, it improves the previous best known results for 388 instances while matching the best known results for the others. We also analyze some key features of the HMA to identify its success factors.

ABSTRACT. This talk is focused on the probabilistic p-Center Problem. Given a set of sites, each with a known probability of having demand, the probabilistic p-Center Problem aims at finding a subset of $p$ locations that minimizes de expected maximum distance between a site with demand and its closest selected location.

In this work we propose two different heuristics for this problem. On the one hand, we propose a heuristic based on variable neighborhood search inspired on a previous work on the discrete ordered median problem. On the other hand, we formulate this problem as a two stage stochastic program, and, taking advantage of this formulation we propose a sample average algorithm.

We compare the proposed methods on a series of computational experiments.

ABSTRACT. Nowadays, Electric Vehicles (EVs) play an important role in green transportation. However, they have driving-range limitations by the low capacity of electronic batteries, which arises new operational challenges. Mostly, hybrid fleets of gas and EVs are heterogeneous respect to the driving-range capabilities. In this paper, we propose a new Multi-Round Iterated Greedy (MRIG) metaheuristic to solve the Vehicles Routing Problem with Multiple Driving ranges (VRPMD). The MRIG is designed to find a set of alternative fleet configurations, with different distance-based costs and green levels. The extensive numerical experiments show that MRIG is able to outperform existing methods.

ABSTRACT. In this paper, three algorithms based on three metaheuristics and two exact methods: Ants System (AS), Harmonic Search (HS), Genetic Algorithm (GA), Primal Dual Algorithm (PDA) and Dual Simplex Algorithm (DSA) are presented. These methods have been called as AS-GA, AS-HS, DSAS-PDA. The behavior of the techniques presented to solve 12 instances of VRP-TW was analyzed. The results show that our hybrid algorithms have a robust behavior and they are able to generate the best solutions reported in the literature with smaller number of calls to the objective function in large instances.

In this techniques, the master are the AS, and for a more efficient construction of the solutions, took advantage of the structure of the problem that made use of the time windows, the distance between the customers to visit and the load assigned to each vehicle as factors within the update of the pheromone level.

ABSTRACT. Ongoing population growth in cities and increasing waste production has made the optimization of urban waste management a critical task for local governments. Route planning in waste collection can be formulated as an extended version of the well-known Vehicle Routing Problem, for which a wide range of solution methods already exist in the literature. However, despite the fact that real-life applications are characterized by high uncertainty levels, most works on waste collection assume deterministic inputs and do not consider any risk analysis. To partially close this gap in the literature, this paper first proposes a competitive metaheuristic algorithm based on a Variable Neighborhood Search framework for the deterministic version of the Waste Collection Problem. Then, the former metaheuristic is extended to a simheuristic algorithm in order to deal with the stochastic version of the problem. This extension is achieved by integrating simulation into the metaheuristic framework, which also allows to perform a risk analysis of the best-found solutions for the stochastic version. A series of computational experiments are carried out to illustrate the potential of the proposed methodology.

ABSTRACT. In this talk we propose and analyze a hybrid metaheuristic combining a large neighbordhood search with mixed integer programming techniques. We apply the said metaheuristic on the multimode resource investment problem which is a project scheduling problem. Several neighborhoods are proposed and tested on new benchmark instances.

ABSTRACT. Extended abstract of 3 pages

ABSTRACT. Tourists visiting a destination for one or several days, face the problem to decide which points of interest (POIs) would be more interesting to visit and to design a trip for each day, which consists of two main issues: firstly, to determine which POIs to visit and secondly to decide the visiting order among them. Each POI is associated with a score that measure the degree of satisfaction associated with its visit. The basic version of the Tourist Trip Design Problem has been modeled in the literature as a Team Orienteering Problem (TOP), but, in order to better describe real problems, further issues must be addressed, such as opening time windows, visiting time and cost, category to which the site belongs, etc. The aim of this work is to provide a general metaheuristic framework able to reach competitive results on different variants of the TOP.

ABSTRACT. The combination of metaheuristics and exact methods offers an advanced platform for competitive solutions. Implementing such methods has already provided high quality solutions for Vehicle Routing Problems (VRPs). We propose a matheuristic with two phases for a variant of the VRP. In the first phase, a Variable Neighborhood Search (VNS) computes feasible routes and stores them in a pool which is updated throughout the search. Then, in the second phase, the routes in the memory are utilized as columns in a set-partitioning formulation. The implemented matheuristic achieves promising results for benchmark instances of the Swap-body Vehicle Routing Problem (SB-VRP).

ABSTRACT. Time series segmentation is aimed at representing a time series by using a set of segments. Some researchers perform segmentation by approximating each segment with a simple model (e.g. a linear interpolation), while others focus their efforts on obtaining homogeneous groups of segments, so that common patterns or behaviours can be detected. The main hypothesis of this paper is that both objectives are conflicting, so time series segmentation is proposed to be tackled from a multiobjective perspective, where both objectives are simultaneously considered, and the expert can choose the desired solution from a Pareto Front of different segmentations. A specific multiobjective evolutionary algorithm is designed for the purpose of deciding the cut points of the segments, integrating a clustering algorithm for fitness evaluation. The experimental validation of the methodology includes one synthetic time series and four datasets from real-world problems. Nine clustering quality assessment metrics are experimentally compared to decide the most suitable one for the algorithm. The proposed algorithm shows good performance for both clustering quality and reconstruction error, improving the results of other mono-objective alternatives of the state-of-the-art and showing better results than a simple weighted linear combination of both corresponding fitness functions.

ABSTRACT. Presentamos un algoritmo GRASP para resolver un problema de secuenciación de productos mixtos en una línea de montaje. El objeto del problema es obtener una secuencia de fabricación de modelos que genere la mínima sobrecarga con interrupción forzada de las operaciones, que sea regular en producción y que el mix de producción mantenga la propiedad cuota en toda la secuencia. El GRASP implementado se compara con otros procedimientos usando instancias de un caso de estudio de la planta de fabricación de motores de Nissan en Barcelona.

ABSTRACT. Se plantea un problema de programación de un conjunto de piezas en un sistema productivo formado por tres máquinas idénticas en paralelo, con elegibilidad, una vez definidos unos tiempos de pre-proceso, proceso y post-proceso para cada pieza. Este problema no sólo considera como objetivo minimizar el instante de finalización de la última pieza en el sistema, sino que además busca minimizar la penalización asociada al coste de utilizar máquinas con tecnologías menos eficientes para producir las piezas. Los procedimientos desarrollados para obtener el conjunto de soluciones (programaciones de piezas en máquinas) no dominadas se basan en la exploración arborescente a partir de secuencias iniciales. Inicialmente no se tiene en cuenta si el movimiento realizado para encontrar una nueva solución será beneficioso o no para los futuros. Posteriormente, se diseñan variantes más complejas modificando los criterios de exploración donde sí se tiene en cuenta, lo que lleva a obtener soluciones de mayor calidad. Para verificar la eficiencia de los procedimientos de resolución propuestos, en la experiencia computacional se resuelven problemas de hasta 200 piezas.

ABSTRACT. Based on the most recent literature dealing with consistency, security aspects and surveillance tasks with respect to vehicle routing problems, we provide a formulation, a definition and a way to measure inconsistency as well as a suitable meta- and mathheuristic that is able to solve the problem given the restrictions from a real world application. As suitable characteristics for diversification in terms of inconsistency we present two possibilities: time of service and route diversity. Those two were selected since those are suitable for a wide range of problems. Time inconsistency is a necessary in patrol problems while route inconsistency is important in cash in transit problems. For the solution approach one important restriction had to be be taken into account: The companies can not control the actual routing drivers use to visit all stops, only the clustering and the time window realization can be controlled. Taking this information into account the clustering had to be used to ensure the route inconsistency and diversity. A two stage solution process consisting of clustering and routing operations is applied (exact ones as well as heuristic ones). The models and heuristics performance were tested on classic instances for the vehicle routing problem as well as real-world instances from an Austrian security service provider.

ABSTRACT. In this paper we investigate a multi-neighbourhood local search approach based on simulated annealing to solve the rental fleet scheduling problem (RVSP). This problem arises in the context of the rental of recreational vehicles (RVs). The problem consists of scheduling a set of bookings and other collateral activities on a heterogeneous fleet of recreational vehicles, so that the overall operational costs are minimised. The problem has a number of complicating features, including the ability to relocate vehicles between (sometimes distant) locations, the ability to use different vehicle types for a booking, and the necessity for some specific vehicles to be present at a given location and time for maintenance or disposal activities. This investigation is motivated by an increase in the volume of operations of one of our industrial partners, whose existing scheduling solution cannot handle adequately, and which prompts for a more scalable approach to vehicle scheduling.

ABSTRACT. In this paper, we present the Tourist Trip Design Problem with Clustered POIs, in which we consider that the set of Point of Interest (POIs) are clustered. Categories represents different types of visiting sites (museum, amusement park, beach, restaurant, ...). The goal is to define the set of feasible tours, one for each day of staying, that maximize the total score. The tours must start and end at a given starting point (which represents the hotel) and the duration of each tour, (computed considering both travel, visit and waiting times) cannot exceed a maximum value. In addition, for each category, the number of visited POIs of category can be bounded or even fixed. For instance, for the category of restaurants for lunch, the number of visits for each trip must be exactly one, and for other category we can have only one side limits.

To address this problem, we propose a solution approach based on GRASP, in which several strategies to define the Restricted Candidate List (RCL) and several local search moves are tested. Computational results show the effectiveness of the proposed approach.

ABSTRACT. In car rental, maximizing the utilization of the fleet is a major challenge. The competitive market and increasingly demanding customers make it necessary to provide a heterogeneous fleet with the right vehicles in each rental station. The main goal of this research is to build a schedule for each vehicle utilization (i.e., to assign reservations to specific vehicles), maximizing the company’s profit, while complying with the order details to ensure customer satisfaction. Due to customer flexibility in choosing the start and end of reservation at any rental station, the fleet is shared among stations. This planning should be done in an integrated manner, so as to guarantee availability at the time and location desired by the customer. In this context, empty transfers of vehicles, performed either by truck or by driver, become critical. In this work, a biased random-key genetic algorithm (BRKGA) is proposed for this problem. Literature instances are tested, thus validating and evaluating the performance of the proposed method. Comparing with the results already presented in literature, this approach allows the reduction of the processing time by approximately 25 times, while maintaining the quality of the solutions.

ABSTRACT. In this paper the nonpreemptive Multi-mode Resource Constrained Project Scheduling Problem (MRCPSP) is addressed. This problem aims to scheduling all jobs of a project subject to the precedence relations among these jobs, which once started can not be interrupted. The jobs have combinations of execution modes, which consist of different processing times and resource consumption. The goal is to minimize the project makespan and determine start times for each project activity. To solve this NP-Hard problem, in this article an algorithm inspired in Artificial Immunological Systems is presented, hybridized with an Adaptive Large Neighborhood Search strategy and also with other specific heuristic techniques for the MRCPSP. Computational tests were performed to verify the trend of the proposed algorithm parameters, as well as to compare variations of this algorithm. The results obtained for a set on instances from the classes of problems of the PSPLIB public library were shown to be strongly competitive in relation to the best results in the literature for these same instances.

ABSTRACT. Minimizing the costs in a project is highly tied with the way the required resources are provided. The resource investment problem deals with how to employ the renewable resources such that the related costs are minimized. Furthermore, the material ordering problem alludes to outlining a proper plan for supplying the nonrenewable resources (materials) to minimize the associated costs. The present paper studies the integration of the resource investment problem with the quantity discount problem in material ordering to thoroughly investigate the resource costs of projects in a single circumstance. The integrated model is presented and mathematically formulated. Three hybrid procedures are proposed for the model, each of which includes a genetic algorithm combined with a dynamic programming, a simulated annealing or a particle swarm optimization algorithm. The mathematical formulations of some small instances are solved to be the subject of an exact comparison with hybrid procedures. The proposed procedures are tested on a set of 810 benchmarks known in the literature. The computational experiments reported by algorithms validate the efficiency of the hybrid genetic algorithm and dynamic programming for the model more than other hybrid approaches.

ABSTRACT. This work shows the application of the corridor method to the multi-mode resource-constrained project scheduling problem. The objective is to find a feasible schedule with a minimum makespan. Each activity has to be assigned to exactly one mode and one starting time. At the same time, precedence as well as resource constraints must be respected. The corridor method combines iterated local search with mixed integer programming. The presented approach is able to find a feasible solution for every instance of the MMLIB dataset. Furthermore, 65 new best known solutions were obtained.

ABSTRACT. The Resource Constraint Project Scheduling Problem (RCPSP) is one of the most challenged scheduling topics. In a RCPSP, we consider a set of jobs submitting to a set of precedence relationships. The project is completed only if all the jobs are finished. The particularity lying in this problem is to consider a set of renewable resources with limited capacities, which are required by jobs in-process. During the whole scheduling horizon, it is compulsory to guarantee enough resources availabilities. We have earlier compared the Non-dominated Sorting Genetic Algorithm II (NSGAII) and NSGAIII to solve a multi-objective RCPSP, considering the makespan, the total tardiness of jobs and the workload balance. In this study, we search for improvements on previous results with a Mapping Method (MaM). The mapping technique was highlighted in the work of Autuori et al. to solve a Flexible Job-Shop problem. It converts a multi-objective solution space into a uni-dimension axis and categorizes the solutions based on their location on the map. This categorization allows to decide if the neighbourhood of a given solution is interesting for further exploration during the local search. In this paper, we integrate the mapping into our algorithms and compare the enhanced methods to the original NSGAs. Experiments are carried out on 540 instances randomly generated, covering different parameters of jobs and resources. They hypervolume and metric-C are used to evaluate the solutions. The efficiency of hybrid methods is proved by both metrics within all groups of tests.

ABSTRACT. The life cycle costs of solar tower power plants are mainly determined by the investment costs of its construction. Significant parts of these investment costs are used for the heliostat field. Therefore, an optimized placement of the heliostats gaining the maximal annual power production has a direct impact on the life cycle costs revenue ratio. We present a Two Level Local Search Methaheuristic implemented in MATLAB utilizing the Monte Carlo raytracing simulator STRAL [1] for the evaluation of the annual power output for a specific weighted annual time scheme. The Two Level Local Search Methaheuristic scales the accuracy parameters of the simulation model dynamically during the search to balance between computational speed, adequate precision, and optimization progress. The algorithm was applied to a solar tower power plant (PS10) with 624 heliostats. Compared to former work of Buck [2], we were able to improve both runtime of the algorithm and quality of the output solutions significantly. Using the same environment for both algorithms, we were able to reach Buck’s best solution with a speed up factor of about 20.

ABSTRACT. Collaborative supply chain strategies constitute promising concepts in the establishment of sustainable freight transportation systems. One example is the concept of vendor managed inventories, in which inventory management and delivery route planning decisions are centrally taken by the supplier. From an optimization point of view, this results in the complex inventory routing problem (IRP). This work presents a simulation-optimization approach combining a variable neighborhood search metaheuristic with simulation to solve the IRP with stochastic demands. Possible inventory stock-outs and individual replenishment levels are considered in our solution framework, which outperforms previously published benchmarks.

ABSTRACT. Telecommunication network-design problems have gained attention over the last decades. Among them, the problem looking for a network design that minimizes total costs, while satisfying users’ demands is well-known. This is the particular case of the Hub Location Problem (HLP). In data communications, a hub is a place of convergence where data arrives from one or more directions and is forwarded out in one or more other directions. In this work-in-progress we proposed the application of a simheuristic algorithm for solving the stochastic uncapacitated HLP in which uncertainty is associated to transportation costs.

ABSTRACT. The uncapacitated facility location problem (UFLP) is a popular combinatorial optimization problem with practical applications in different areas, from logistics to telecommunication networks. While most of the existing work in the literature focuses on minimizing total cost for the deterministic version of the problem, some degree of uncertainty (e.g., in the customers' demands or in the service costs) should be expected in real-life applications. Accordingly, this paper proposes a simheuristic algorithm for solving the stochastic UFLP (SUFLP), where optimization goals other than the minimum expected cost can be considered. The development of this simheuristic is structured in three stages: (i) first, an extremely fast savings-based heuristic is introduced; (ii) next, the heuristic is integrated into a metaheuristic framework, and the resulting algorithm is tested against the optimal values for the UFLP; (iii) finally, the algorithm is extended by integrating it with simulation techniques, and the resulting simheuristic is employed to solve the SUFLP. Some numerical experiments contribute to illustrate the potential uses of each of these solving methods, depending on the version of the problem (deterministic or stochastic) as well as on whether or not a real-time solution is required.

ABSTRACT. This work investigates the Symmetric Quadratic Traveling Salesman Problem, which is an extension of the classical (linear) Traveling Salesman Problem. The quadratic case aims to minimize the total cost of a tour, where cost values are not associated to single edges, but to every successive pair of edges. We discuss this highly complex problem and introduce heuristic approaches in order to construct and improve solutions. The range of methods comprises pure heuristic procedures, metaheuristics, and introduces matheuristic ideas as well. Computational results are analyzed, including optimal benchmarking and the discussion of algorithmic designs.

ABSTRACT. The chaotic neural network is one of the effective algorithms for solving combinatorial optimization problems, such as the traveling salesman problem (TSP), quadratic assignment problem (QAP), and vehicle routing problem (VRP). In this metaheuristic algorithm, chaotic dynamics was used to search for solutions along the fractal structure with zero Lebesgue measure constructed by its dynam- ical properties to find the optimum solution in the search space. The performance of chaotic neural networks has already been clarified for combinatorial optimization problems such as the TSP, QAP, and VRP. These combinatorial optimization problems are allowed any form of connection between nodes to construct the solutions. However, the evaluation of problems wherein the connections be- tween nodes are determined in advance, such as the Steiner tree problem in graphs, has not yet been clarified. In the Steiner tree problem in graphs, the solution algorithm attempts to combine the con- nections or routes of the nodes to construct the minimum Steiner tree. In order to clarify whether the chaotic neural network is effective for various kinds of combinatorial optimization problems, this study evaluated chaotic neural networks for the Steiner tree problems in graphs. Numerical exper- iments show that the method using the chaotic neural network can effectively decrease the cost of obtaining the Steiner tree compared to other proposed methods.

ABSTRACT. Every year, natural and man-made disasters have devastating effects on millions of people around the world. An estimated 400 000 people lost their lives and more than 4 000 000 were affected in only two recent major natural disasters, the Indian Ocean earthquake and tsunami, and the Haiti earthquake [1]. What is worse, both natural and man-made disasters are expected to increase another five-fold over the next forty years due to environmental degradation, rapid urbanization and the spread of HIV/AIDS in the developing world [9]. This highlights the need for effective and efficient assistance to disaster-affected communities. Fortunately, there is a growing research interest in the field of humanitarian logistics that specializes in rapid provision of relief (such as emergency shelter, food, water or medicine) to affected areas, so as to minimize human suffering and death [4].

Most of the research in humanitarian logistics focuses on the post-event distribution of aid to people in need of assistance, e.g., [5, 6, 12]. Aid distribution can be formulated as an optimization problem that decides how to utilize the available vehicles to transport the relief to the affected cities or villages, with the goal of minimizing, for example, transportation cost or response time. However, disaster response can be further enhanced in the preparedness phase, before the occurrence of an emergency. Improving preparedness for natural and man-made disasters is one of the challenges of the EU Research and Innovation Horizon 2020 program [2]. Some research suggests that every dollar invested into disaster preparedness saves seven dollars in disaster aftermath [3].

One mechanism to increase preparedness is advance procurement and pre-positioning of relief inventory at strategic locations. This allows to additionally speed up emergency assistance and save more lives by reaching areas that could be otherwise inaccessible. In turn, it makes the optimization problem much more complicated as it increases the number of decisions that need to be made, before even knowing the scale and particularities of the disaster. Indeed, next to deciding about the transportation of supplies, one must also determine the location of storage facilities and the amount of relief items to be pre-positioned, all under uncertainty about the impact of the disaster.

In the relatively little research that has been conducted on the problem of pre-positioning emergency supplies, we have identified three areas for improvement. Firstly, many problem formulations fail to account for a number of complex aspects inherent to the problem, such as multiple facility or commodity types, limited vehicle capacity or uncertainties related to some characteristics of an emergency. Secondly, more often than not, the formulations found in the literature aim to minimize costs, e.g. [7, 8, 11], which does not necessarily reflect the priorities of emergency response. The shortage of critical supplies in humanitarian relief chains makes it impossible to deliver the aid to all people in need. To help decide who are the people who will be provided with needed assistance, an economic value of human suffering is commonly introduced and added to the objective. The goal of an emergency plan then becomes to minimize the summation of logistics costs and the costs of human suffering. Not only is this monetary proxy of human suffering controversial due to its ethical implications, but it is also challenging to determine, while the quality of emergency response obtained by the model is extremely sensitive to this value. Finally, many papers only employ commercial solvers to find the best pre-positioning strategy for one small instance. However, for larger instances the problem becomes intractable for exact methods and thus calls for suitable heuristic procedures.

In order to address these issues, we formulate the pre-positioning problem as a two-stage stochastic mixed integer program that decides on the (1) number, location and category of storage facilities to open, represented by binary variables x = [x iq] that indicate whether a facility of category q is open at vertex i, (2) amount y = [y ik] of commodity k to pre-position at a facility open at vertex i, and (3) aid distribution strategy, represented by binary variables z = [z ijs] that indicate whether a facility open at vertex i serves the demands of vertex j in scenario s. A number of scenarios is used to model the uncertainties about the demands, survival of pre-positioned supplies and transportation network availability. This information can be predicted and/or derived from historical data.

Instead of considering logistics costs as an objective, in our formulation, they are treated as constraints: the aim is to directly minimize unmet demand and response time, while simply respecting the budget limitations. In [10], we show that this model is able to achieve the same (if not better) results as the cost-minimizing approach, without forcing the practitioners to put a price on human life. In addition, we illustrate how our formulation also offers practitioners the flexibility to explore a number of diverse emergency plans in a straightforward manner, that provides insights about the problem and helps in many aspects of disaster response planning.

In order to be able to find good pre-positioning strategies for instances of realistic size in a reasonable amount of time, we develop a matheuristic that employs local search techniques to look for good location and inventory configurations (first-stage decision variables x and y), and use CPLEX to find the optimal assignment of cities to the facilities that serve their demands (second-stage decision variables z). Although the matheuristic performs well, designing moves to heuristically optimize continuous inventory decision variables proved to be a significant challenge. This motivated us to, instead, use heuristics to decide on binary facility and assignment decision variables x and z, and resort to CPLEX in order to look for a feasible inventory scheme y. We investigate how the two different approaches compare and, in particular, if employing CPLEX to solve a few small linear programs instead of a large integer program for each disaster scenario guarantees a more successful matheuristic. We use a number of case studies from the literature to evaluate the performance of the two proposed methods. Using different case studies, combined with the flexibility offered by our mathematical model, can help to derive some general recommendations to guide comprehensive emergency response planning. The model, the devised matheuristics and the results of our study will be presented in detail at the conference.

ABSTRACT. This paper considers a variant of the multiple depot Vehicle Routing Problem with Time Windows where competence constraints define the places that vehicles can visit. A difficulty faced here is that the special set of instances are highly constrained, due to tight competence and time window constraints. This induced a matheuristic approach, combining advantages of MIP exact approaches with constructive and local search heuristics. A first work furnishes matheuristics based on compact MIP formulation works. Then, a column generation scheme is developed, using previous work to solve subproblems generating aggressively multiple columns. The resulting column generation heuristic outperforms significantly the previous matheuristics.

ABSTRACT. Multitud de estudios han demostrado que hay una relación directa entre los Polimorfismos de Nucleótido Simple o SNPs y la aparición de enfermedades complejas, como el Alzheimer, el Parkinson, la diabetes, etc. Sin embargo, recientes avances en el Estudio de la Asociación del Genoma Completo indican que la relación entre SNPs y dichas enfermedades va más allá de una simple relación uno a uno, por lo que se están realizando investigaciones que relacionan múltiples SNPs (epistasia) con la aparición de estas dolencias. En este sentido, este trabajo propone la aplicación del algoritmo multiobjetivo NSGA-II para la detección de epistasia de dos loci haciendo uso de una regresión logística y una red Bayesiana como funciones objetivo. Para comprobar la validez de los resultados se han realizado pruebas con 5200 conjuntos de datos generados a partir de 52 tablas de penetrancia de los modelos DME y DNME con 1600 individuos y 100 SNPs cada una. Además, se ha ampliado la comparativa añadiendo un conjunto de datos de mayor tamaño con 4000 individuos y 1000 SNPs para verificar los resultados cuando ampliamos el número de individuos y SNPs. Los resultados obtenidos se han comparado con el algoritmo MACOED propuesto por otros autores usando las mismas funciones objetivo. Dichas comparativas demuestran que la implementación NSGA-II aquí presentada obtiene mejores resultados que MACOED en todas las pruebas realizadas, ya sea usando los conjuntos de datos de tamaño reducido como con el de mayor tamaño, tanto desde el punto de vista cualitativo como del tiempo de ejecución.

ABSTRACT. En bioinformática, es vital encontrar alineamientos precisos entre múltiples secuencias biológicas que tienen algún tipo de relación evolutiva. De los alineamientos, se puede inferir la homología, y puede llevarse a cabo un análisis filogenético, el cual nos indicará los orígenes evolutivos compartidos por las secuencias. Este problema es conocido como Alineamiento Múltiple de Secuencias (MSA, Multiple Sequence Alignment). Diferentes heurísticas han sido publicadas para resolver el problema MSA, tales como métodos basados en alineamientos progresivos, basados en consistencia, iterativos o algoritmos genéticos. En este trabajo, se propone el uso de optimización multiobjetivo e inteligencia colectiva de abejas para el alineamiento múltiple de secuencias. La metaheurística propuesta optimiza simultáneamente dos funciones objetivo con el fin de preservar la calidad (suma ponderada de pares, WSP) y la consistencia (número de columnas iguales, TC) de los alineamientos resultantes. En nuestro estudio hemos utilizado el conjunto de datos BAliBASE 3.0 (uno de los más utilizados a la hora de evaluar el rendimiento de nuevos alineadores) para realizar comparativas entre la metaheurística propuesta y más de 15 alineadores publicados en la literatura.

ABSTRACT. La introducción de técnicas de computación paralela en las metaheurísticas ha representado tradicionalmente una aproximación prometedora para resolver problemas de optimización de elevados costes temporales. No obstante, los avances en el estudio de metaheurísticas han dado lugar a diseños cada vez más complejos cuya paralelización da lugar a problemas de rendimiento bajo esquemas paralelos clásicos. Este trabajo tiene por objeto abordar la paralelización del algoritmo Indicator-Based Multiobjective Bat Algorithm en entornos de memoria compartida, aplicando el diseño resultante para resolver un problema real de bioinformática: la reconstrucción de historias filogenéticas. La idea fundamental radica en aplicar estrategias adecuadas que permitan lidiar con las diferentes fuentes de sobrecarga y desbalanceo de carga presentes en el algoritmo secuencial. Los experimentos efectuados sobre una infraestructura hardware de 64 cores dan cuenta de la bondad del diseño paralelo propuesto, mejorando otras implementaciones y métodos en términos de rendimiento paralelo y obteniendo a su vez soluciones de calidad significativa en tiempos reducidos.