MIC'2017: 12TH METAHEURISTICS INTERNATIONAL CONFERENCE
PROGRAM FOR THURSDAY, JULY 6TH
Days:
previous day
next day
all days

View: session overviewtalk overview

09:00-10:30 Session T1.1: Transportation
Location: 40.004
09:00
A Heuristic for the Period Vehicle Routing Problem with Inventory

ABSTRACT. We consider a period vehicle routing problem with inventory motivated by lean manufacturing principles. We present a mixed-integer-programming-based local search algorithm for this problem. At each iteration, a neighbor solution is generated by solving a commodity flow formulation over a carefully-selected subset of binary variables. Preliminary findings on six real-world data sets show that the matheuristic obtains solutions 0.785 percent better on average than a traditional local search heuristic.

09:20
An Adaptive Large Neighborhood Search for the Consistent Inventory Routing Problem

ABSTRACT. Every year, the consumption of beer is around 400 million hectoliters in Europe. Although the consumption per capita and year is quite stable, the demands and characteristics of the customers (bars, restaurants, stands...) are really diverse. Each establishment has different and independent opening hours, time windows and different inventory characteristics. Customers can also demand consistency in delivery times. Special events, such as sports events or music festivals, create, due to temporary high demands, the need of delivering commodity with more than one vehicle. Hence, the creation of efficient inventory routing plans is highly demanding. We present a model which includes time windows, inventory and consistency management as well as split deliveries to create delivery routes. We also propose a metaheuristic to obtain efficient solutions in large real world instances which consist in a constructive phase with some local searches followed by an adaptive large neighborhood search applied to the obtained solution.

09:40
A Large Neighborhood Search for a Rich Vehicle Routing Problem arising in the Steel Industry

ABSTRACT. We study a variant of the vehicle routing problem inspired by a real world problem setting that occurs in steel producing factories. Steel slabs are heterogeneous items that appear at locations at certain release times and, according to their handling instructions, need to be transported to another location within the factory before a certain due time. They are transported by fleets that include standard vehicles as well as truck-and-trailer type vehicles. In our model, practitioners impose high processing rates such that not all steel slabs can be delivered in time during the considered optimization period. Therefore, the objective function is organized in a lexicographic fashion: first, maximize the throughput-related profit; second, minimize travel times. Exact solutions can only be obtained for small problem settings. In order to solve large real world instances, we propose an algorithm based on Large Neighborhood Search. The results of our approach show that the solutions obtained are competitive compared to the solutions provided by our industrial partner.

10:00
A Hybrid Heuristic for a Balanced Vehicle Routing Problem with Time Windows and Loading Constraints

ABSTRACT. The Vehicle Routing Problem with Loading Constraints (VRPLC) has strong connections with real life transportation problems. In a VRPLC the simultaneous loading and routing of vehicles is addressed simultaneously, thus interest in the development of applications for VRPLCs has risen in recent years. The VRPLC literature provides a large number of available heuristics approaches, but several of these have considered only a limited group of practical characteristics that arise in real cases. This study proposes a hybrid heuristic method based on the GRASP metaheuristic and the Clarke and Wright Savings algorithm, to solve a VRPLC with several loading and routing constraints that have not been considered simultaneously before, such as time windows, balanced vehicle fleet and weight distribution inside the transporting vehicles. We provide experimental results to show that the proposed heuristic approach is capable of obtaining feasible solutions in a short amount of time.

09:00-10:30 Session T1.2: Scheduling
Location: 40.006
09:00
An ILS heuristic for a real-life ship scheduling problem

ABSTRACT. This work proposes an Iterated Local Search (ILS) heuristic for solving a ship scheduling prob-lem in the context of a Brazilian offshore oil company. This problem consists in scheduling activi-ties of oil wells interconnection for a fleet of Pipe Laying Support Vessels (PLSV). Due to its prop-erties, we have modeled it as an identical parallel machines scheduling problem. Extensive exper-iments were carried out on real data. Results showed that this approach was able to improve the current solution in more than 91%.

09:20
Predictive baseline schedule for electrical vehicles charging in dedicated residential zone parking

ABSTRACT. Uncertainties challenge the electrical vehicles (EV) charging in the residential zones (EVCR). In this paper, we take into account the uncertainty caused by random arrival times and demands of EV customers. A simulating protocol is presented to get the schedule baseline of EVCR problem. This baseline can decide the total power subscription and the charging time-horizon of EVCR. A more-than-necessary power subscription would be a costly waste. A less-than-necessary one could not assure a good service level. Our contributions are two-folds. First, we introduce a constructive heuristic to solve the deterministic scheduling problem. Then, we present a predictive framework working on the historical data. Finally, we present a case study, input data of which are taken from our actual industrial project. With the statistical results from the case study, we can draw conclusions and propose perspectives for future works.

09:40
Algoritmos Constructivos Mateheurísticos para Solucionar el Problema de Programación de Vehículos de Transporte Público de Pasajeros con Múltiples Depósitos

ABSTRACT. En este trabajo se presentan 3 algoritmos constructivos híbridos, que combinan métodos heurísticos y exactos para solucionar el problema de programación de vehículos de transporte público de pasajeros con múltiples depósitos MDVSP. El primer constructivo asigna cada uno de los viajes programados a los depósitos teniendo en cuenta el orden cronológico de los viajes y el mejor costo de salida desde el depósito y seguidamente se construyen los itinerarios de manera heurística (Concurrent Scheduler). El segundo método construye una secuencia general de atención, la cual combina criterios de orden cronológico y una adaptación de la heurística para solucionar el Problema del Agente Viajero TSP, Vecino más Cercano (Nearest Neighbor); para determinar el depósito desde donde se atenderá cada itinerario, se resuelve el modelo matemático del Problema de Asignación Generalizada (Generalized Assigment Problem). Finalmente, se propone una metodología que combina la teoría de grafos para determinar itinerarios de mínimo costo con los modelos de Asignación generalizada y Flujo Mínimo en una red. Para validar cada uno de los algoritmos se utilizan 90 instancias de la literatura especializada, las cuales tienen entre 2 y 5 depósitos, y entre 100 y 500 viajes. Los algoritmos presentan tiempos de respuesta cercanos a cero. El enfoque de este trabajo es proporcionar métodos eficientes en tiempos de cómputo para la reprogramación en tiempo real de los itinerarios de vehículos, especialmente para aliviar la operación cuando se presentan contingencias en el caso real del Sistema de Transporte Masivo del Área Metropolitana Centro Occidente de Colombia AMCO, cuya operación consta de alrededor de 5000 viajes diarios.

10:00
Strategic planning of maintenance work of a large-scale tramway network

ABSTRACT. This article studies the strategic planning of maintenance work for the infrastructure of a large-scale urban transportation network. A mixed integer programming model has been developed to represent this planning problem. When solved via a commercial solver (CPLEX) the model is able to generate good solutions with a small optimality gap only for small instances but it lacks the ability of generating maintenance plans for large scale networks. For solving large instances an algorithm based on large neighborhood search was implemented. This algorithm is compared to CPLEX on small instances and is applied to the Viennese tramway network in a numerical test.

09:00-10:30 Session T1.3: Metaheuristics in Retail Operations
Location: 40.008
09:00

ABSTRACT. This article presents a heuristic to solve the integrated problem of building pallets and loading them into trucks. The heuristic is used to solve a real application involving particular constraints and considerations. The validation of the proposal is based on comparison of performance of the computed solutions. As a reference of comparison we have selected a commercial packing tool of high acceptance that employs two different algorithms. A four-step methodology is used: (i) design of the optimization algorithm, (ii) selection of test data, (iii) calculation of the solution using the Cape Pack® and GrasPacking optimization tools, (iv) performance validation by comparison, minimizing the total wasted space. The performance of the proposed algorithm is evaluated using real instances associated with delivery orders of a logistic company. The results allow us to con-clude that the proposed algorithm has a good performance which overcomes the commercial tool.

09:20
A Biased-randomized algorithm for non-smooth arc routing problems with realistic soft constraints
SPEAKER: Albert Ferrer

ABSTRACT. In this paper we discuss arc routing problems with non-smooth objective functions, and propose a biased-randomized algorithm for solving it. Our approach employs a skewed probability distribution to transform a savings-based deterministic heuristic into a randomized algorithm, which is then integrated into an iterated local search framework. By doing so, a large set of alternative good solutions can be quickly obtained in a natural way and without complex configuration processes. Since the solution generation process is based on the criterion of maximizing the savings at each step, it does not need to assume any particular property of the objective function. The procedure can be especially useful in problems where properties such as non-smoothness or non-convexity lead to a highly irregular solution space, for which the traditional optimization methods may fail to reach their full potential. In our numerical experiments we show how the solutions vary when realistic soft constraints are allowed instead of hard ones.

09:40

ABSTRACT. The research on multi-compartment vehicle routing problems (MCVRP) is still young and therefore the available literature is limited, especially when flexible compartments are considered. Besides fuel distribution, grocery distribution is one main applications and the focus of our research. By using multi-compartment vehicles (MCV), the MCVRP offers new possibilities for distribution but also imposes new challenges for the planning problem. An important aspect is the occurrence of loading issues when MCV are used. If the loading of an MCV is not taken into account within the routing, loading issues will impact the deliveries and lead to infeasible unloading situations at stores.

In our work we addresses this problem by considering an extended MCVRP that takes into account loading constraints. We develop efficient solution approaches to solve the arising problem. First, a branch-and-cut algorithm is presented to solve the problem exactly for smaller problem sizes. Second, a Large Neighborhood Search (LNS) is introduced to solve larger, practical relevant problems. Within our solution approaches we solve a specialized packing problem to account for loading constraints. The packing problem is formulated as integer program (IP). The tailored LNS iteratively solves the routing and packing problem while the branch-and-cut algorithm is guided by adding cuts for infeasible solutions. In numerical studies we analyze the performance of the proposed solution approaches. Additionally, we perform tests on larger instances to derive general rules for the influence of loading constraints in practice. To conclude the numerical experiments, a case study was analyzed with an European retailer.

10:00
An ALNS for solving the MCVRP with Product-Specific Time-Windows Assignment
SPEAKER: Sara Martins

ABSTRACT. The research on multi-compartment vehicle routing problems (MCVRP) is still a young area as these trucks types has only be applied in transportation during the last years. Besides the distribution of fuel, one main application is the grocery distribution. Multi-compartment vehicles (MCV) can be used by grocery retailers to jointly transport products that require different temperatures, making it possible to reduce the number of stops at a store by delivering all products together. This paper extends the work on MCVRP by considering a multi-period setting, where a time-window has to be selected for each customer-product pair and used consistently throughout the planning horizon. An adaptive large neighborhood search (ALNS) is proposed to solve the problem with daily operators, focusing on the improvement of routing aspects of the problem on each day, and weekly operators, called to align the time-windows consistency throughout the periods.

09:00-10:30 Session T1.4: Ph.D Colloquim
Location: 40.010
09:00
Cyclic Cutwidth Minimization Problem
SPEAKER: J.D. Quintana

ABSTRACT. The Cyclic Cutwidth Minimization Problem (CCMP) consist in labelling the vertices of a graph in order to map it into a circular layout, in such a way that the maximum cutwidth in the region, defined between consecutive vertices in the layout is minimized. This is a combinatorial optimization problem that was proposed as theoretical model for circuit layout design and it has been shown to be N P–hard. Exact solutions are known for some particular classes of graphs, however, for other classes and general graphs optimal solutions are not known. In this work-in-progress paper we review previous literature for the problem and we introduce several promising heuristics to tackle the CCMP.

09:20
Scheduling of a line manager using Iterated Local Search

ABSTRACT. In this document we will describe the the problem of the scheduling of a packaging system for perishable products. The problem was first introduced by Ferrari et al. in [1] where an optimal control solution is presented. The solution proposed however relies on being able to optimally solve a scheduling problem for the current line status in a very fast manner in order to be usable. For this scheduling problem we will propose a metaheuristic based solution using the Iterated Local Search Framework and present some experimental results comparing the metaheuristic to an exact method developed for the problem.

[1]: G Ferrari, L Ferrarini, A Petretti, and E Pizzi. Modeling and design of an optimal line manager of a packaging system with milp. In Industrial Electronics Society, IECON 2015-41st Annual Conference of the IEEE, pages 005050–005056. IEEE, 2015.

09:40
Routes design from warehouses towards the delivery points
SPEAKER: Marcelus Lima

ABSTRACT. In such a competitive and complex market, the warehouse managing procedures have a substantial importance into the final companies’ outcome. Therefore, we propose an optimization method to improve a warehouse’s throughput. We expect to identify the design of the routes, which is optimal for a determining set of parameters. Also, we plan to solve the mathematical model through Iterated-Local-Search. Finally, we plan to compare our solution and the current solution provided by the company, regarding some key performance indicators.

10:00
A neighborhood for the blocking job-shop problem embedded in a simulated annealing
SPEAKER: Julia Lange

ABSTRACT. The classical job-shop scheduling problem is one of the well-studied models in scheduling research. Including a real-world aspect, the consideration of blocking constraints refers to the absence of buffers in a production system. The resulting blocking job-shop problem is complex due to additional interdependencies of different jobs on different machines. Mathematical programming results give evidence to the necessity of efficient heuristic methods to obtain near-optimal solutions. There are two major challenges in the application of a heuristic approach to this problem. First, a permutation of operations satisfying the technological orders, which does always define a feasible schedule for the classical job-shop problem, does not necessarily give a feasible schedule with regard to blocking constraints. Second, it is not clear how to complete and repair a partial solution to determine feasible neighbors of a solution. For the blocking job-shop problem a procedure is presented, which generates a feasible schedule from any given permutation of operations. Additionally, a neighborhood is derived applying adjacent pairwise interchanges together with a technique to complete partial solutions and construct feasible neighbors. Both mechanisms are implemented in a simulated annealing metaheuristic and tested with regard to the minimization of total tardiness.

09:00-10:30 Session T1.5: Metaheuristics in Port Logistics and Related Problems (MAEB)
Location: 40.012
09:00
Artificial Intelligence System for supporting the management of berthing operations

ABSTRACT. The increasing volume of maritime freight is presented as a challenge to those skilled terminal managers seeking to maintain or increase their market share. In this context, an efficient management of scarce resources arises as a reasonable option for reducing costs while enhancing the productivity of the overall terminal. In this work, we address the management of berthing scheduling operations at Bulk Ports. Namely, for a given yard layout and location of the cargo facilities, we aim to coordinate the berthing and yard activities for giving service to those vessels arriving to the terminal. To do so, we propose an artificial intelligence system that allows to determine the best solution algorithm depending on the scenario at hand.

09:20
Multi-agent based Model for the Simulation of Yard Crane Operations at Maritime Container Terminals

ABSTRACT. This paper introduces a combined solution approach of optimization and simulation procedures for the Yard Crane Scheduling Problem. This optimization problem seeks to obtain a sequence of retrieval and storage operations of containers around the yard of a maritime container terminal. The solution approach combines an efficient hybrid Greedy Randomized Adaptive Search Procedure and Variable Neighborhood Search to obtain solution for the deterministic problem and a multiagent based model is used to deal with the stochastic nature of the environment. The proposed approach considers that high-quality solutions for the deterministic version of the problem will also be high-quality solutions for the stochastic version. In addition, the paper proposes a test battery for solution resilience analysis in order to evaluate the behaviour of deterministic solutions in dynamic environments.

09:40
A GRASP algorithm for the container stowage slot planning problem

ABSTRACT. This work presents a generalization of the Slot Planning Problem which raises when the liner shipping industry needs to plan the placement of containers within a vessel (stowage planning). State-of-the-art stowage planning relies on a heuristic decomposition where containers are first distributed in clusters along the vessel. For each of those clusters a specific position for each container must be found. Compared to previous studies, we have introduced two new features: the explicit handling of rolled out containers and the inclusion of separations rules for dangerous cargo. We present a novel integer programming formulation and a Greedy Randomized Adaptive Search Procedure (GRASP) to solve the problem. The approach is able to find high-quality solution within 1 second. We also provide comparison with the state-of-the-art on an existing and a new set of benchmark instances.

10:00
Heuristic and metaheuristic algorithms for a multi-port container ship stowage problem

ABSTRACT. The multi-port container ship stowage problem consists in developing a plan for the position of the containers in a ship taking into account its whole route and the different sets of containers which must be loaded at each port. The objective of the problem is to minimize the number of unproductive moves necessary to unload the containers at their port of discharge. In this work, we present a preprocessing phase for fixing the position of some containers before solving the problem with one of the existing heuristic algorithms. Moreover, we propose a local search technique that goes from one solution to another seeking an improvement of the objective function. Finally, a GRASP has been developed and computational results corroborate its good performance. The computational study carried out show that GRASP generates stowage plans with a minimal number of reshuffles in a high percentage of instances.

10:30-11:00 Session : Coffee Break
Location: 30.S02 S. Exposition
11:00-12:00 Session Plenary: "Black-Box Solvers In Combinatorial Optimization" Rafael Martí and Manuel Laguna

Rafael Marti, University of Valencia, Spain

Manuel Laguna, Leeds School of Business of the University of Colorado Boulder. USA

Black box optimizers have a long tradition in the field of operations research. These procedures treat the objective function evaluation as a black box and therefore do not take advantage of its specific structure. Black-box optimization refers to the process in which there is a complete separation between the evaluation of the objective function —and perhaps other functions used to enforce constraints— and the solution procedure. The challenge of optimizing black boxes is to develop methods that can produce outcomes of reasonable quality without taking advantage of problem structure and employing a computational effort that is adequate for the context. Holland’s (1975) genetic algorithms proposal was in fact a black-box optimizer that used an array of bits as the generic representation. The proposed procedure did not include local search and the standard genetic operators (such as single-point crossover) were not linked to the problem context. As GAs became more popular and researchers and practitioner applied them to many hard optimization problems, the context-independent nature of the original proposal began to vanish when improved outcomes were obtained by the addition of problem structure. During the last years we worked on the adaptation of metaheuristic methodologies to deal with black-box combinatorial optimization. We classified the problems according to their solution representation: permutation, binary, and integer to create solvers in each family. In this talk we will review commercial black-box solvers, such as Opttek’s OptQuest, Palisade’s Evolver and Frontline’s Premium Solver, and compare their performance with our metaheuristic implementations based on the Scatter Search methodology on many different optimization problems.

Location: 30.S01 Auditorium
12:00-13:30 Session T2.1: Variable Neirgborhood Search
Location: 40.004
12:00
A Parallel Variable Neighborhood Search Approach for the Obnoxious p-Median Problem

ABSTRACT. In this work we investigate the application of a Variable Neighborhood Search (VNS) procedure for a max-min-location problem, known as the Obnoxious p-Median Problem. We develop new and fast local search procedures to be integrated into the Basic VNS methodology. Besides, after tuning some parameters of the algorithm, the best VNS variant is parallelized and compared with the best previous methods. Experimental results show that the proposed VNS outperforms previous methods in the state of the art over a wide set of instances generated from the OR-Library.

12:20
A variable neighborhood search for single machine scheduling problem with time restrictions
SPEAKER: unknown

ABSTRACT. In this paper we analyze a single machine scheduling problem with time restrictions. The objective considered is the minimization of the makespan. In this problem several jobs, available at the begging of the schedule, have to be processed on a single machine. The machine can handle only one job at a time, and during any time period of length alpha the number of jobs being executed is less than or equal to a given integer value B. The problem is known to be NP-hard for any value of B > 2. We propose a variable neighborhood search metaheuristic to solve the problem and we conduct computational experiments on randomly generated instances. The results indicate that our algorithm is effective and efficient regarding the quality of the solutions and the computational times required to find them.

12:40
Solving the Steiner Tree Problem in graphs with Variable Neighborhood Descent

ABSTRACT. The Steiner Tree Problem (STP) in graphs is an important problem with various applications in many areas such as design of integrated circuits, evolution theory, networking, etc. In this paper, we propose an algorithm to solve the STP. The algorithm includes a Reducer and a Solver using Variable Neighborhood Descent (VND), interacting with each other during the search. New constructive heuristics and a vertex score system for intensification purpose are proposed. The algorithm is tested on a set of benchmarks which shows encouraging results.

13:00
A hybrid VNS matheuristic for a bin packing problem with a color constraint

ABSTRACT. We study a new variant of the bin packing problem with a color constraint. Given a finite set of items, each item has a set of colors. Each bin has a color capacity, the total number of colors for a bin is the union of colors for its items and cannot exceed the bin capacity. We need to pack all items into the minimal number of bins. For this NP-hard problem we present approximability results and design a hybrid matheuristic based on the column generation technique. The VNS heuristic is applied for the pricing problem. The column generation method provides a lower bound and a core subset of the most promising bin patterns. Fast heuristics and exact solution for this core produce upper bounds. Computational experiments for test instances with number of items up to 500 illustrate the efficiency of the approach.

13:20
Solving the maximum min-sum dispersion by alternating formulations of two different problems

ABSTRACT. The maximum min-sum dispersion problem aims to maximize the minimum accumulative dispersion among the chosen elements. It is known to be strongly NP-hard problem. In this paper we present heuristic where the objective functions of two different problems are shifted within variable neighbor- hood search framework. Though this heuristic can be seen as an extended variant of variable formulation search approach that takes into account alternative formulations of one problem, the important differ- ence is that it allows using alternative formulations of more than one optimization problem. Here we use one alternative formulation that is of max-sum type of the originally max–min type maximum diversity problem. Computational experiments on the benchmark instances used in the literature show that the suggested approach improves the best known results for most instances in a shorter computing time.

12:00-13:30 Session T2.2: Scheduling
Location: 40.006
12:00
Scheduling for the Growing of Crops to Meet Demand
SPEAKER: Chris Potts

ABSTRACT. A problem of scheduling the growing of crops to meet customer demand as closely as possible is considered. The plants are to be assigned to growing locations of a given capacity, where all plant types in the same location at any time must have identical requirements for irrigation and lighting. Movement of plants between locations is allowed, although such movements should be minimized as far as is possible. A hierarchical decomposition heuristic is proposed, where the first phase minimizes the total weighted quantity of unsatisfied demand, and the second phase takes the satisfied demands from the first phase as input and aims to minimize plant movements. A computational evaluation of the heuristic using data from an industrial partner is reported.

12:20
A biased random-key genetic algorithm for the Multi-period, Multi-rate and Multi-channels with variable bandwidth Scheduling Problem

ABSTRACT. This paper introduces a new combinatorial optimization problem that arises from a new technology described in the IEEE 802.11ac standard. The latter enables a higher transmission speed than the previous IEEE standards, because it allows a higher flexibility on how the network frequency spectrum is divided into communication channels. The problem consists in assigning the time slot, channel and bandwidth for a given set of communications links. We propose a biased random-key genetic algorithm for this problem. Computational experiments showed that this heuristic can significantly improve the network throughput by exploiting the flexibility in the channel bandwidth.

12:40
Referee Assignment for a Basketball League with Multiple Divisions using Local Search

ABSTRACT. We consider a referee assignment problem arising from an amateur basketball league with many divisions. The problem consists in assigning a variable number of referees to each game of the season according to a set of constraints and objectives.

We propose a simulated annealing search method that turned out to provide feasible solutions in short time, ensuring fairness between referees, balancing the referee/team assignments, and minimizing the travel time of referees.

13:00
A Metaheuristic Approach for Scheduling Steelmaking and Casting Plants

ABSTRACT. We apply local search metaheuristics to a production scheduling problem in real-world steelmaking and casting plants. This is an ongoing research and we are working on the infrastructure for integrating with the actual control monitor of the plan in order to test and tune our solver.

12:00-13:30 Session T2.3: Metaheuristics - General
Location: 40.008
12:00
Minimum Labelling bi-Connectivity

ABSTRACT. We consider the problem of finding the minimum set of labels that provide bi-connectivity among all the vertices of a labelled, undirected graph given as input. A graph is bi-connected if there are at least two disjoint paths joining every pair of vertices. We consider both bi-connectivity concepts: the edge bi-connectivity where these paths cannot have a common edge and the vertex bi-connectivity where the paths cannot have a common vertex. We describe our preliminary investigation on the problem and provide the details on an exact solution approach under current development.

12:20
TSP Neighbourhood Reduction with POPMUSIC

ABSTRACT. A key point for implementing a fast and efficient local search is to use a neighbourhood of limited size containing all the pertinent moves. For the travelling salesman problem, the most efficient neighbourhoods are based on Lin-Kernighan moves or extensions. In order to speed-up the computation, only a subset of moves are evaluated. This article propose a method with low algorithmic complexity for generating a limited subset of pertinent edges that must be used in the solution tours. Combined with state-of-the art local searches, this technique is able to produce solutions of very high quality to very large problem instances.

12:40
A metaheuristic algorithm using chaotic neurodynamics with degree information for the dynamic combinatorial optimization problem: a packet routing problem
SPEAKER: Yuuki Morita

ABSTRACT. Combinatorial optimization problems are categorized into two groups: static combinatorial op- timization problems and dynamic combinatorial optimization problems. In static combination op- timization problems, the search space for solutions is stationary. The optimum solution, therefore, does not change with time. On the other hand, the search space changes with time in dynamic com- binatorial optimization problems. Thus, there is no guarantee that the current optimum solution will also be the optimum solution the next time. On of the typical dynamic combinatorial optimization problms is a packet routing problem, whose primary objective is to transmit packets from sources to as many destinations as possible, is one of the typical dynamic combinatorial optimization prob- lems. In addition, the shortest hop method, which is commonly employed as the routing method in real computer networks, cannot transmit the packets to destinations if packet flows increase. In this study, we propose a heuristic algorithm using chaotic neurodynamics with degree information for the packet routing problem. The numerical experiments show that proposed method improves the packet arrival rate by approximately 130% compared to the conventional sp-hop method.

13:00
Proper balance between search towards and along Pareto front: biobjective TSP case study

ABSTRACT. In this paper we propose simple yet efficient version of the Two-Phase Pareto Local Search (2PPLS) for solving the biobjective traveling salesman problem (bTSP). In the first phase the powerful Lin-Kernighan heuristic is used to generate some high quality solutions being very close to the Pareto front. Then Pareto Local Search is used to generate more potentially Pareto efficient solutions along the Pareto front. Instead of previously used method of Aneja and Nair we use uniformly distributed weight vectors in the first phase. We show experimentally that properly balancing the computational effort in the first and second phase we can obtain results better than previous versions of 2PPLS for bTSP and at least comparable to the state-of-the art results of more complex MOMAD method. Furthermore, we propose a simple extension of 2PPLS where some additional solutions are generated by Lin-Kernighan heuristic during the run of PLS. In this way we obtain a method that is more robust with respect to the number of initial solutions generated in the first phase.

12:00-13:30 Session T2.4: Smart Cities
Location: 40.010
12:00
Beacon-based solution for dynamic traffic light management

ABSTRACT. Nowadays, the large number of vehicles in cities causes serious problems, such as serious pollution increase, difficulty for emergency services to move through the streets, or long waiting time due to traffic congestion. In this paper, a dynamic traffic lights management system is proposed in order to optimize the movement of both pedestrians and vehicles taking into account the number of individuals at the same crossing. The proposal is based on Bluetooth Low Energy (BLE) small devices as identifier of each traffic light together with a mobile phone application that allows to identify pedestrians and vehicles, among other operations. To develop the proposal the GPS location of the vehicles and the pedestrians, together with the identification of the detected traffic light beacon is used. has been endowed with the necessary security mechanisms to preserve anonymity of users, and confidentiality, integrity and authenticity of data.

12:20
Hybrid Metaheuristics for Multiobjective Thermal and Electrical Energy Management in a Smart Home

ABSTRACT. In recent years, energy demand has increased strongly due to industrial development, rapid urbanization, and the world's population growth, which leads to operational, economic, and environmental issues. According to the International Energy Agency report (IEA), the energy consumption will increase further with an average annual rate of 1.5\% by 2030. The growing energy needs often make current power grids under stress, and occasionally causes power supply imbalance. To meet the growing energy needs and maintain the reliability of energy supply, investments in new power plants and transporting electricity lines are needed, which negatively affect energy costs causing dramatic power losses in high scale energy distribution network. On the other hand, the energy demand was mainly covered by the use of fossil fuels such as oil, natural gas or coal. The over-consumption of these fuels results to their depletion and serious environmental issues such as greenhouse gas emissions.To meet the growing demand for energy while fighting against climate change, several policies have been adopted. In this context, energy consumers are expected to play a pivotal role in energy management through so called demand side management (DSM). Demand side management refers to the policies that are intended to either curtail or shift energy consumption with the aim to achieve financial, societal and environmental benefits. Indeed, the demand side management provides a multitude of asset's for the future power grid by improving the load factor, reducing costs, maintaining the energy system reliability, giving a new era to the paradigm "consumption follows production" by managing energy demand-supply balance with the local energy generation and storage system. Our work is intended to present a model for the DSM in a smart home in order to coordinate the local energy sources (micro combined heating cooling and power and photovoltaic panel), the local storage (thermal and electrical energy storages), different electrical and thermal appliances, and the ability to inject the surplus of electricity from the local energy sources to the grid for revenue.

12:40
Travel Assistance Application for Seniors

ABSTRACT. In smart cities, and in particular within smart mobility, improving the mobility of older people increases their independence and their active participation in society. Within the mobility of this group, we find that public transport is possibly the only tool they have to be able to move from one place to another. The problem with this type of transportation is that it can become very confusing, and even more for these types of people because their cognitive and sensory abilities tend to be smaller. This is why this work describes the idea and operation of a mobile application that will guide the elderly through the means of transport. To do this, the application has been designed with a simple interface that works with both keyboard and voice commands, and uses BLE beacons to detect events that may occur during the journey. In addition, the application has been enriched with a implementation based on fuzzy logic that will allow to show a series of recommendations to the passenger, facilitating the use of the application.

12:00-13:30 Session T2.5: Metaheuristics General (MAEB)
Location: 40.012
12:00
Scatter search para el problema multi-objetivo p-median y p-dispersion.

ABSTRACT. En este artículo se propone la utilización de la metodología Scatter Search en el problema multi-objetivo de la p-median y p-dispersion. Para realizar una ordenación de las soluciones por calidad, se propone una métrica de la distancia de cada solución a una referencia ideal, de modo que se puedan combinar soluciones según este criterio de calidad. Además, se han estudiado tres métodos de mejora dentro de Scatter Search y se han comparado con el estado del arte, obteniendo buenos resultados en hipervolumen para un conjunto de instancias de tamaño medio.

12:20
An Alternative ILP Model and Algorithmic Ideas for the Maximum Edge-Disjoint Paths Problem

ABSTRACT. This document describes an alternative integer linear programming (ILP) model for the so-called edge-disjoint paths (EDP) problem in undirected graphs. EDP is an $\mathcal{NP}$-hard problem where exact methods are not able to produce high quality solutions. Therefore, we propose two different algorithms for combining exact and heuristic methods. On the one hand, we consider a restricted model that limits the number of paths between two given nodes in the graphs (which reduces the search space exploration). On the other hand, the application of a mat-heuristic algorithm known as Construct, Merge, Solve and Adapt (CMSA) is considered. In this document we show some preliminary results concerning the restricted model. These results indicate the potential usefulness of the presented ideas.

12:40
Multi-Start Methods for the Capacitated Clustering Problem

ABSTRACT. The Capacitated Clustering Problem (CCP) consists of forming a given number of clusters or groups from a set of elements in such a way that the sum of the weights of the elements in each cluster is within some capacity limits, and the sum of the benefits between the pairs of elements in the same cluster is maximized. In this work, we investigate the adaptation of the Greedy Randomized Adaptive Search Procedure (GRASP) and Iterated Greedy methodologies to the Capacitated Clustering Problem (CCP). In particular, we focus on the effect of the balance between randomization and greediness on the performance of these multi-start heuristic search methods when solving this NP-hard problem. The former is a memory-less approach that constructs independent solutions, while the latter is a memory-based method that constructs linked solutions, obtained by partially rebuilding previous ones. Both are based on the combination of greediness and randomization in the constructive process, and coupled with a subsequent local search phase. We propose these two multi-start methods and their hybridization and compare their performance on the CCP. Additionally, we propose a heuristic based on the mathematical programming formulation of this problem, which constitutes a so-called matheuristic. We also implement a classical randomized method based on simulated annealing to complete the picture of randomized heuristics. Our extensive experimentation reveals that Iterated Greedy performs better than GRASP in this problem, and improved outcomes are obtained when both methods are hybridized and coupled with the matheuristic. This study shows that memory-based construction is an effective mechanism within multi-start heuristic search techniques.

13:00

13:30-15:00 Session : Lunch
Location: Cafeteria (Roger de Lluria building)
15:00-16:00 Session Plenary (MAEB): "VNS para Planificación Logística" José Andrés Moreno Pérez

José Andrés Moreno Pérez, Universidad de La Laguna, España

Location: 30.S01 Auditorium
16:00-16:30 Session : Coffee Break
Location: 30.S02 S. Exposition
16:30-18:00 Session T4.1: Automated Algorithm Design
Location: 40.004
16:30
ADVISER+: Toward a Usable Web-based Algorithm Portfolio Deviser

ABSTRACT. The present study offers a more user-friendly and parallelized version of a web-based algorithm portfolio generator, called ADVISER. ADVISER is a portfolio generation tool to deliver a group of configurations for a given set of algorithms targeting a particular problem. The resulting configurations are expected to be diverse such that each can perform well on a certain type of problem instances. One issue with ADVISER is that it performs portfolio generation on a single-core which results in long waiting times for the users. Besides that, it lacks of a reporting system with visualizations to tell more about the generated portfolios. ADVISER is extended as ADVISER+ to overcome both of these issues while introducing new tuning based portfolio generation capabilities.

16:50
The irace Package: Iterated Racing for Automatic Algorithm Configuration

ABSTRACT. Modern optimization algorithms typically require the setting of a large number of parameters to optimize their performance. The immediate goal of automatic algorithm configuration is to find, automatically, the best parameter settings of an optimizer. Ultimately, automatic algorithm configuration has the potential to lead to new design paradigms for optimization software. The irace package is a software package that implements a number of automatic configuration procedures. In particular, it offers iterated racing procedures, which have been used successfully to automatically configure various state-of-the-art algorithms. The iterated racing procedures implemented in irace include the iterated F-race algorithm and several extensions and improvements over it. In this paper, we describe the rationale underlying the iterated racing procedures and introduce a number of recent extensions. Among these, we introduce a restart mechanism to avoid premature convergence, the use of truncated sampling distributions to handle correctly parameter bounds, and an elitist racing procedure for ensuring that the best configurations returned are also those evaluated in the highest number of training instances. We experimentally evaluate the most recent version of irace and demonstrate with a number of example applications the use and potential of irace, in particular, and automatic algorithm configuration, in general.

17:10
Revisiting Simulated Annealing: From a Component-Based Analysis to an Automated Design of Simulated Annealing Algorithms

ABSTRACT. In this paper we show how the combination of flexible algorithm frameworks with automatic algorithm configuration techniques can be useful for the analysis and the automated design of new algorithms. Algorithm frameworks can be used to capture the wide variety of algorithmic components for heuristic algorithms and serve as basic experimental frameworks. We exemplify this approach considering Simulated Annealing (SA). In fact, a wide variety of design choices of SA algorithms has been proposed in the literature and by collecting the available ideas into algorithm frameworks we can analyze specific algorithms and component choices, and allow the generation of new algorithm variants by combining existing components in new ways. In our experiments we show how the tuning improves the existing algorithms, and how it can be used to automatically design new SA implementations starting from the options available in the framework.

17:30
AMH: a new Framework to Design Adaptive Metaheuristics
SPEAKER: Aymeric Blot

ABSTRACT. Metaheuristics should be configured to well perform on a given problem. Their configuration is either made off-line by automatic algorithm configuration tools or on-line with control mechanisms to adapt the behaviour. This former mean requires a flexible structure that may be modified during the execution. Therefore, the implementation of such a structure is not straightforward to enable modifications of optimisation strategies and not of parameter values only. In this work, we present AMH, a framework dedicated to the design of configurable metaheuristics. This framework is based on the execution flow of an algorithm that enables the flexibility of the implementation.

16:30-18:00 Session T4.2: Metaheuristics in Cloud Computing
Location: 40.006
16:30
A Brokering Approach for Multi-Objective Resource Allocation in Cloud Computing
SPEAKER: Stefan Voß

ABSTRACT. In multi-clouds, on-demand infrastructure as a service solutions are used from multiple cloud providers. To benefit from this novel technology-delivery model, those services need to be selected and configured in a way that individual cost and performance goals of consumers can be achieved. This often involves to consider, depending on the given consumer and scenario, different objectives such as costs, latencies, and execution times. In this work, we propose a multi-objective cloud brokering approach in which different objectives are considered with the aim, from a broker perspective, to facilitate allocation and scheduling decision processes for IaaS services under several rich constraints. The underlying problem is solved by means of the NSGA-II and AMOSA algorithms. Using a large set of problem instances, we evaluate and compare their performances using the well-known hypervolume measure.

16:50
Evaluating a Two-Phase Virtual Machine Placement Optimization Scheme for Cloud Computing Datacenters

ABSTRACT. Infrastructure as a Service (IaaS) providers must support requests for virtual resources in complex dynamic cloud computing environments, taking into account service elasticity and overbooking of physical resources. Due to the randomness of customer requests, Virtual Machine Placement (VMP) problems should be formulated under uncertainty. This work proposes an experimental evaluation of a two-phase optimization scheme for VMP problems, studying different (i) online heuristics, (ii) overbooking protection factors and (iii) objective function scalarization methods. The proposed experimental evaluation considers an uncertain VMP formulation for the optimization of the following three objective functions: (i) power consumption, (ii) economical revenue, and (3) resource utilization. Experiments were performed considering 96 different scenarios, representing complex cloud computing environments. Experimental results shows that Best-Fit and Best-Fit Decreasing heuristics are recommended in the incremental VMP (iVMP) phase working with the considered Memetic Algorithm in the VMP reconfiguration (VMPr) phase, adjusting protection factors to 0.00 and 0.75 in low and high CPU load scenarios respectively, while scalarazing the proposed three objective functions considering an Euclidean distance to the origin.

17:10
Optil.io Platform: Evaluation as a Service for Metaheuristics
SPEAKER: Szymon Wasik

ABSTRACT. Evaluation as a Service, in brief, is defined as a paradigm of keeping the evaluation data in the cloud and allowing to access them via dedicated interfaces. Here, we present Optil.io, an online platform that allows users to reliably evaluate metaheuristic-based algorithms, designed to solve complex optimization problems, in a secure cloud-based infrastructure. The proposed platform supports a continuous evaluation of all solutions submitted by the participants for science- or industry-inspired challenges.

17:30
Evolutionary planning for IaaS virtual brokering in the cloud

ABSTRACT. This article presents an evolutionary approach for virtual machine planning under the model of virtual brokering for IaaS services in cloud computing. The proposed evolutionary algorithm provides an accurate technique for managing the cloud user requests and planning the effective utilization of virtual machines owned by the virtual broker. The main results indicate that the planning method is able to guarantee significant profit values for the broker, while fulfilling the service level agreements required by users. The proposed evolutionary approach outperforms several planning heuristics previously proposed in the literature.

16:30-18:00 Session T4.3: Metaheuristics - General
Location: 40.008
16:30
Hybridizing Particle Swarm Optimization Variants on Continuous Optimization Functions

ABSTRACT. This paper presents a comparison between four new hybridizations using two Particle Swarm Optimization (PSO) variants: the Barebones PSO (BPSO) and the Comprehensive Learning PSO (CLPSO). The goal of these hybridizations is to improve the exploration and the exploitation of the search space from these two variants. The performance of these four new hybrids, named CLBPSO-Demi, CLPSO+CL, BPSO+CL, and CLBPSO-NewVel, are compared with the original CLPSO and BPSO on classical continuous optimization functions. The results are compared using stochastic dominance and convergence analysis.

16:50
An evolutionary algorithm for harmonic music composition
SPEAKER: unknown

ABSTRACT. This article presents an evolutionary approach for harmonic music composition using information from a database of existing songs from a given musician. The fitness function of the proposed evolutionary algorithm uses score comparison to find harmonies which are similar---but no equal---to those songs in the database. A voice-based version of the composition problem is solved, where each voice contains a melody composed by notes and rests. The generic problem is reduced to compose the musical notes implied in each voice and to compare them to a set of entry sounds, stored in a reference database. Promising results are reported for five sample database instances.

17:10
Grid-Based Parameter Adaptation in Particle Swarm Optimization

ABSTRACT. Metaheuristics have been established as essential tools for solving complex optimization problems. Although they have proved to be useful in problems where other algorithms fail, their performance is heavily dependent on their proper parametrization. The latter is typically addressed through a laborious preprocessing phase of parameter tuning, which consumes significant amount of computational resources and time. For this purpose various techniques, also called tuners, have been proposed in the literature. Tuners are distinguished into offline and online, depending on whether they tune the parameters prior to the algorithm's application or during its run. Recently a grid-based parameter adaptation approach was proposed and successfully applied on the Differential Evolution algorithm. The present work extends the application field of this technique by incorporating it in the Particle Swarm Optimization algorithm for the adaptation of its scalar parameters as well as the neighborhood radius. Proper modifications in the technique are made and a first empirical evaluation is conducted on a large-scale test suite where plain PSO has questionable performance. The results show that PSO equipped with this approach becomes more efficient while, at the same time, the user is relieved from the burden of parameter tuning.

17:30
A differential evolution algorithm for single model U-type assembly line balancing problem

ABSTRACT. U-type layouts have been utilized in many production lines in place of the traditional straightline configuration due to the use of just-in-time principles. Since any type of an assembly line balancing problem is known to be NP-hard, there has been a growing tendency toward using evolutionary algorithms to solve such a hard problem. This paper proposes a differential evolution algorithm to address the multi-objective U-type assembly line balancing problem. We considered preemptive goal programming, which minimizes the smoothing index as the primary objective, and maximizes the line efficiency as a secondary objective. The proposed approach is tested on well-known test problems from the literature with up to 111 tasks, and the results are compared with the previously best known solutions. The computational results show that the proposed approach performs quite effectively.

16:30-18:00 Session T4.4: Logistics and Supply Chain Management
Location: 40.010
16:30
An iterated local search precedure for the green vehicle routing problem with heterogeneous fleet and time windows

ABSTRACT. In this work, we investigate a specific version of the Green Vehicle Routing Problem with time windows. We propose a sequential insertion heuristic combined with a local search to optimize the routing of a mixed vehicle fleet, composed by electric and classical (internal combustion engine) vehicles. Since the electric vehicles have a limited autonomy of the battery, the possibility of recharging partially at any of the available stations is taken into consideration. In addition, we also consider a limitation on the pollution emissions for the classical vehicles.

16:50
A hybrid metaheuristic approach for the two-dimensional loading vehicle routing problem with heterogeneous fleet (2L-HFVRP)

ABSTRACT. In this work, we present a hybrid metaheuristic approach for the 2L-HFVRP with sequential loading constraints. This problem combines two well-known NP-hard problems: the heterogeneous fleet vehicle routing problem (HFVRP) and the two-dimensional sequential loading problem (2D-LP). The proposed approach for the considered problem uses a set of initial solutions generated by a specialized constructive algorithm; trying to get an initial population based on a set of good so-lution for a TSP problem. A Genetic Algorithm (GA) was developed to manage all the search pro-cess. To encoding each chromosome is used the Prins’ auxiliary graph. Meanwhile, the feasibility of the solutions respect to the loading constraints is checked by a reactive GRASP algorithm. The GRASP verifies if the demand of the customers belonging to a route must be placed in the fleet by considering sequential loading constraints (multi-drop constraints). Five different crossover meth-ods SJX, PMX, OX, CX, and OBX were implemented. In this case, after applied the crossover methods the algorithm checks the packing feasibility of the new offspring. The best individuals could be mutated with a randomized shaking procedure. Therefore, the population is updated if better solutions are found. Finally, the proposed approach shows good quality results on bench-marking instances, improving some of the best-known previous solutions.

17:10
Solving a supply chain design problem by the krill herd algorithm

ABSTRACT. This paper proposes a krill herd algorithm to solve a supply chain design problem for a family of products forming hierarchies of sub-assemblies and components. There may be multiple suppliers that can supply a component or many manufacturers and assemble the sub-assemblies. Therefore, there are several resource options for each activity, and there is a lead time and a cost associated with each one. The problem is to choose the best option in terms of the total cost and lead times. This is done using a krill herd algorithm, whose results are compared with the results obtained by a genetic algorithm and differential evolution in terms of the solution quality. Parameter setting is done for the krill herd and differential evolution algorithms in a full-factorial setting with some of the values driven from the literature.

17:30
Combining DES with metaheuristics to improve scheduling and workloads in parcel transshipment terminals

ABSTRACT. In this paper, we investigate an extended local search algorithm with discrete-event simulation (DES) to solve problems at the operational level of parcel transshipment terminals. This level concerns the scheduling of incoming trucks as well as the assignment of outbound relations to the sorters. The best allocated heuristics by Schumacher outperform the existing exact optimization methods for transshipment terminals of Clausen, by requiring much less computation time and with a higher amount of detail. Our approach makes it possible to assess optimization results in a more realistic DES-environment, where stochastic impacts are included. The approach demonstrates that also in a stochastic environment, local search can provide solutions that reduce the makespan by approximately 7 % (more than 40 minutes) compared to common "first come, first serve" (FCFS) practice.