Pasar al contenido principal

Resultados relacionados

Resultados totales (Incluyendo duplicados): 24
Encontrada(s) 1 página(s)

Dipòsit Digital de Documents de la UAB
Publicación Artículo de revisión (ReviewArticle)

Learnheuristics, Hybridizing metaheuristics with machine learning for optimization with dynamic inputs

  • Calvet, Laura|||0000-0001-8425-1381
  • Armas, Jésica De
  • Masip, David
  • Juan, Ángel A.|||0000-0003-1392-1776
This paper reviews the existing literature on the combination of metaheuristics with machine learning methods and then introduces the concept of learnheuristics, a novel type of hybrid algorithms. Learnheuristics can be used to solve combinatorial optimization problems with dynamic inputs (COPDIs). In these COPDIs, the problem inputs (elements either located in the objective function or in the constraints set) are not fixed in advance as usual. On the contrary, they might vary in a predictable (non-random) way as the solution is partially built according to some heuristic-based iterative process. For instance, a consumer's willingness to spend on a specific product might change as the availability of this product decreases and its price rises. Thus, these inputs might take different values depending on the current solution configuration. These variations in the inputs might require from a coordination between the learning mechanism and the metaheuristic algorithm: at each iteration, the learning method updates the inputs model used by the metaheuristic.
Repositorio Digital de la UPF
Publicación Artículo científico (JournalArticle)

Multi criteria biased randomized method for resource allocation in distributed systems: Application in a volunteer computing system

  • Panadero, Javier
  • De Armas, Jésica
  • Serra, Xavier
  • Marquès, Joan Manuel
Volunteer computing is a type of distributed computing in which a part or all the resources (processing power and storage) necessary to run the system are donated by users. In other words, participants contribute their idle computing resources to help running the system. Due to the fact that the nodes which compose the system are provided by a large number of users instead of a single (or a few) institution, a main drawback of volunteer computing is the unreliability of these nodes. For this reason, the selection of nodes to be involved in each task becomes a key issue. In this paper, we propose the Multi Criteria Biased Randomized (MCBR) method, a novel selection method for large-scale systems that use unreliable nodes. MCBR method is based on a multicriteria optimization strategy. We evaluated the method in a microblogging social network formed by a large number of microservices hosted in nodes voluntarily contributed by their participants. Simulation results show that our proposal is able to select nodes in a fast and efficient manner while requiring low computational power., This work has been partially supported by the Spanish Ministry of Economy and Competitiveness (TRA2013-48180-C3-P, TRA2015-71883-REDT), FEDER and the Erasmus+ programme (20161ES01KA108023465).
Repositorio Digital de la UPF
Publicación Artículo científico (JournalArticle)

Biased randomization of heuristics using skewed probability distributions: a survey and some applications

  • Grasas, Àlex
  • Juan, Angel A.
  • Faulin, Javier
  • De Armas, Jésica
  • Ramalhinho-Lourenço, Helena
Randomized heuristics are widely used to solve large scale combinatorial optimization problems. Among the plethora of randomized heuristics, this paper reviews those that contain biased-randomized procedures (BRPs). A BRP is a procedure to select the next constructive ‘movement’ from a list of candidates in which their elements have different probabilities based on some criteria (e.g., ranking, priority rule, heuristic value, etc.). The main idea behind biased randomization is the introduction of a slight modification in the greedy constructive behavior that provides a certain degree of randomness while maintaining the logic behind the heuristic. BRPs can be categorized into two main groups according to how choice probabilities are computed: (i) BRPs using an empirical bias function; and (ii) BRPs using a skewed theoretical probability distribution. This paper analyzes the second group and illustrates, throughout a series of numerical experiments, how these BRPs can benefit from parallel computing in order to significantly outperform heuristics and even simple metaheuristic approaches, thus providing reasonably good solutions in ‘real time’ to different problems in the areas of transportation, logistics, and scheduling., This work has been partially supported by the Spanish Ministry of Economy and Competitiveness and FEDER (TRA2013-48180-C3-P, TRA2015-71883-REDT), the Ibero-American Program for Science and Technology for Development (CYTED2014-515RT0489), and the Erasmus+ Program (2016-1-ES01-KA108-023465).
Repositorio Digital de la UPF
Publicación Artículo científico (JournalArticle)

Designing e‐commerce supply chains: a stochastic facility–location approach

  • Pagès Bernaus, Adela
  • Ramalhinho-Lourenço, Helena
  • Juan, Angel A.
  • Calvet Mir, Laura
E‐Commerce activity has been increasing during recent years, and this trend is expected to continue in the near future. e‐Commerce practices are subject to uncertainty conditions and high variability in customers’ demands. Considering these characteristics, we propose two facility–location models that represent alternative distribution policies in e‐commerce (one based on outsourcing and another based on in‐house distribution). These models take into account stochastic demands as well as more than one regular supplier per customer. Two methodologies are then introduced to solve these stochastic versions of the well‐known capacitated facility–location problem. The first is a two‐stage stochastic‐programming approach that uses an exact solver. However, we show that this approach is not appropriate for tackle large‐scale instances due to the computational effort required. Accordingly, we also introduce a “simheuristic” approach that is able to deal with large‐scale instances in short computing times. An extensive set of benchmark instances contribute to illustrate the efficiency of our approach, as well as its potential utility in modern e‐commerce practices., This work has been partially supported by the Spanish Ministry of Economy and Competitiveness and FEDER (TRA2013-48180-C3-P, TRA2015-71883-REDT) and the Erasmus+ programme (2016-1-ES01-KA108-023465). We also thank the support of the UOC doctoral programme.
Repositorio Digital de la UPF
Publicación Capítulo o parte de un libro (BookPart)

Iterated local search: framework and applications

  • Ramalhinho-Lourenço, Helena
  • Martin, Olivier C.
  • Stützle, Thomas
The key idea underlying iterated local search is to focus the search not on the full space of all candidate solutions but on the solutions that are returned by some underlying algorithm, typically a local search heuristic. The resulting search behavior can be characterized as iteratively building a chain of solutions of this embedded algorithm. The result is also a conceptually simple metaheuristic that nevertheless has led to state-of-the-art algorithms for many computationally hard problems. In fact, very good performance is often already obtained by rather straightforward implementations of the metaheuristic. In addition, the modular architecture of iterated local search makes it very suitable for an algorithm engineering approach where, progressively, the algorithm’s performance can be further optimized. Our purpose here is to give an accessible description of the underlying principles of iterated local search and a discussion of the main aspects that need to be taken into account for a successful application of it. In addition, we review the most important applications of this method and discuss its relationship with other metaheuristics., Helena Ramalhinho Lourenço acknowledges support from the Spanish Ministry of Economy and Competitiveness (TRA2013-48180-C3-P, TRA2015-71883-REDT), and Thomas Stützle acknowledges support from the F.R.S.-FNRS, of which he is a research director. This work received support from the COMEX project P7/36 within the Interuniversity Attraction Poles Programme of the Belgian Science Policy Office.
Repositorio Digital de la UPF
Publicación Artículo científico (JournalArticle)

Generic Pareto local search metaheuristic for optimization of targeted offers in a bi-objective direct marketing campaign

  • Coelho, Vitor Nazário
  • Oliveira, Thays Aparecida de
  • Coelho, Igor Machado
  • Coelho, Bruno N.
  • Fleming, Peter J.
  • Guimarães, Frederico G.
  • Ramalhinho-Lourenço, Helena
  • Souza, Marcone Jamilson Freitas
  • Talbi, El-Ghazali
  • Lust, Thibaut
Cross-selling campaigns seek to offer the right products to the set of customers with the goal of maximizing expected profit, while, at the same time, respecting the purchasing constraints set by investors. In this context, a bi-objective version of this NP-Hard problem is approached in this paper, aiming at maximizing both the promotion campaign total profit and the risk-adjusted return, which is estimated with the reward-to-variability ratio known as Sharpe ratio. Given the combinatorial nature of the problem and the large volume of data, heuristic methods are the most common used techniques. A Greedy Randomized Neighborhood Structure is also designed, including the characteristics of a neighborhood exploration strategy together with a Greedy Randomized Constructive technique, which is embedded in a multi-objective local search metaheuristic. The latter combines the power of neighborhood exploration by using a Pareto Local Search with Variable Neighborhood Search. Sets of non-dominated solutions obtained by the proposed method are described and analyzed for a number of problem instances., The authors would like to thank Brazilian agency CAPES, CNPq (grants 305506/2010-2, 552289/2011-6, 306694/2013-1 and 312276/2013-3), FAPEMIG (grants APQ-04611-10, PPM CEX497-13) and FP7 CORDIS, “New Horizons for Multi Criteria Decision Making”, for supporting the development of this work. Helena Ramalhinho was also partially supported by the Spanish Ministry of Economy and Competitiveness (TRA2013- 48180-C3-P, TRA2015-71883-REDT).
Repositorio Digital de la UPF
Publicación Artículo científico (JournalArticle)

An ILS-based algorithm to solve a large-scale real heterogeneous fleet VRP with multi-trips and docking constraints

  • Coelho, Vitor Nazário
  • Grasas, Àlex
  • Ramalhinho-Lourenço, Helena
  • Coelho, Igor Machado
  • Souza, Marcone Jamilson Freitas
  • Cruz, R. C.
Distribution planning is crucial for most companies since goods are rarely produced and consumed at the same place. Distribution costs, in addition, can be an important component of the final cost of the products. In this paper, we study a VRP variant inspired on a real case of a large distribution company. In particular, we consider a VRP with a heterogeneous fleet of vehicles that are allowed to perform multiple trips. The problem also includes docking constraints in which some vehicles are unable to serve some particular customers, and a realistic objective function with vehicles’ fixed and distance-based costs and a cost per customer visited. We design a trajectory search heuristic called GILS-VND that combines Iterated Local Search (ILS), Greedy Randomized Adaptive Search Procedure (GRASP) and Variable Neighborhood Descent (VND) procedures. This method obtains competitive solutions and improves the company solutions leading to significant savings in transportation costs., This work has been partially supported by CNPq (grants 552289/2011-6 and 306458/2010-1), FAPEMIG (grants PPM CEX 497-13, APQ-04611-10), CAPES and Science Without Borders (grant 202380/2012-2 and 202381/2012-9), the Spanish Ministry of Economy and Competitiveness (TRA2013-48180-C3-P) and the Ibero-American Programme for Science, Technology and Development (CYTED2010-511RT0419).
Repositorio Digital de la UPF
Publicación Artículo científico (JournalArticle)

Modeling and solving the non-smooth arc routing problem with realistic soft constraints

  • De Armas, Jésica
  • Ferrer, Albert
  • Juan, Angel A.
  • Lalla-Ruiz, Eduardo
This paper considers the non-smooth arc routing problem (NS-ARP) with soft constraints in order to capture in more perceptive way realistic constraints violations arising in transportation and logistics. To appropriately solve this problem, a biased-randomized procedure with iterated local search (BRILS) and a mathematical model for this ARP variant is proposed. An extensive computational study is conducted on rich and diverse problem instances. The results highlight the competitiveness of BRILS in terms of quality and time, where it provides high-quality solutions within reasonable computational times. In the context of real-world environments, the performance exhibited by BRILS motivates its incorporation in intelligent and integrative systems where frequent and fast solutions are required., Supported by the Spanish Ministry of Economy and Competitiveness & FEDER (TRA2015-71883-REDT, TRA2013-48180-C3-P, SEV-2015-0563).
Repositorio Digital de la UPF
Publicación Artículo científico (JournalArticle)

SimILS: a simulation-based extension of the iterated local search metaheuristic for stochastic combinatorial optimization

  • Grasas, Àlex
  • Juan, Angel A.
  • Ramalhinho-Lourenço, Helena
Iterated Local Search (ILS) is one of the most popular single-solution-based metaheuristics. ILS is recognized by many authors as a relatively simple yet efficient framework able to deal with complex combinatorial optimization problems (COPs). ILS-based algorithms have been successfully applied to provide near-optimal solutions to different COPs in logistics, transportation, production, etc. However, ILS is designed to solve COPs under deterministic scenarios. In some real-life applications where uncertainty is present, the deterministic assumption makes the model less accurate since it does not reflect the real stochastic nature of the system. This paper presents the SimILS framework that extends ILS by integrating simulation to be able to cope with Stochastic COPs in a natural way. The paper also describes several tested applications that illustrate the main concepts behind SimILS and give rise to a new brand of ILS-based algorithms., This work has been partially supported by the Spanish Ministry of Economy and Competitiveness (TRA2013-48180-C3-P) and by the Ibero-American Programme for Science, Technology and Development (CYTED2010-511RT0419).
Repositorio Digital de la UPF
Publicación Artículo científico (JournalArticle)

A BRILS metaheuristic for non-smooth flow-shop problems with failure-risk costs

  • Ferrer, Alberto
  • Guimarans, Daniel
  • Ramalhinho-Lourenço, Helena
  • Juan, Angel A.
This paper analyzes a realistic variant of the Permutation Flow-Shop Problem (PFSP) by considering a non-smooth objective function that takes into account not only the traditional makespan cost but also failure-risk costs due to uninterrupted operation of machines. After completing a literature review on the issue, the paper formulates an original mathematical model to describe this new PFSP variant. Then, a Biased-Randomized Iterated Local Search (BRILS) algorithm is proposed as an efficient solving approach. An oriented (biased) random behavior is introduced in the well-known NEH heuristic to generate an initial solution. From this initial solution, the algorithm is able to generate a large number of alternative good solutions without requiring a complex setting of parameters. The relative simplicity of our approach is particularly useful in the presence of non-smooth objective functions, for which exact optimization methods may fail to reach their full potential. The gains of considering failure-risk costs during the exploration of the solution space are analyzed throughout a series of computational experiments. To promote reproducibility, these experiments are based on a set of traditional benchmark instances. Moreover, the performance of the proposed algorithm is compared against other state-of-the-art metaheuristic approaches, which have been conveniently adapted to consider failure-risk costs during the solving process. The proposed BRILS approach can be easily extended to other combinatorial optimization problems with similar non-smooth objective functions., This research has been partially supported by the Spanish Ministry of Economy and Competitiveness, projects MTM2011-29064-C03-02, MTM2014-59179-C2-01 & TRA2013-48180-C3-P, and FEDER. NICTA is funded by the Australian Government through the Department of Communications and the Australian Research Council through the ICT Centre of Excellence Program.
Repositorio Digital de la UPF
Publicación Artículo científico (JournalArticle)

A VNS approach for book marketing campaigns generated with quasi-bicliques probabilities

  • Oliveira, Thays Aparecida de
  • Coelho, Vitor Nazário
  • Ramalhinho-Lourenço, Helena
  • Souza, Marcone Jamilson Freitas
  • Coelho, Bruno N.
  • Rezende, Daniel C.
  • Coelho, Igor Machado
This paper focuses on Book Marketing Campaigns, where the benefit of offering each book is calculated based on a bipartite graph (biclique). A quasi Biclique problem is assessed for obtaining the probabilities of success of a given client buy a given book, considering it had received another book as free offer. The remaining optimization decision problem can be solved following the Targeted Offers Problem in Direct Marketing Campaigns. The main objective is to maximize the feedback of customers purchases, offering books to the set of customers with the highest probability of buying others ones from its biclique and, at the same time, minimizing campaign operational costs. Given the combinatorial nature of the problem and the large volume of data, which can involve real cases with up to one million customers, metaheuristics procedures have been used as an efficient way for solving it. Here, a hybrid trajectory search based algorithm, namely GGVNS, which combines the Greedy Randomized Adaptive Search Procedures and General Variable Neighborhood Search, is used. The strategy for generating the quasi Biclique problem is described and a new instance generator for the TOPDMC is introduced. Computational results regarding the GGVNS algorithm shows it is able to find useful and profitable sets of clients., The authors thank the Brazilian agencies CNPq (grants 306694/2013-1, 552289/2011-6 and 202380/2012-2) and FAPEMIG (grants PPM CEX 772/15 and APQ-04611-10) for supporting the development of this work. Helena Ramalhinho was also partially supported by the Spanish Ministry of Economy and Competitiveness (TRA2013-48180-C3-P, TRA2015-71883-REDT).
O2, repositorio institucional de la UOC
Publicación Artículo científico (JournalArticle)

A simheuristic algorithm for solving the arc routing problem with stochastic demands

  • González Martín, Sergio
  • Juan, Angel A.
  • Riera Terrén, Daniel
  • Elizondo, Monica G.
  • Ramos, Juan Jose
This paper proposes a simheuristic algorithm for solving the Arc Routing Problem with Stochastic Demands (ARPSD). Our approach combines Monte Carlo Simulation (MCS) with the RandSHARP metaheuristic, which was originally designed for solving the Capacitated Arc Routing Problem with deterministic demands (CARP). The RandSHARP metaheuristic is a biased-randomized version of a savings-based heuristic for the CARP, which allows it to obtain competitive results for this problem in low computational times. The RandSHARP is then combined with MCS to cope with the stochastic variant of the problem in a natural and efficient way. Our work is based on the use of a safety stock during the route-design stage. This safety stock can then be used during the delivery stage to satisfy unexpected demands. A reliability index is also defined to evaluate the robustness of each solution with respect to possible route failures caused by random demands. Some numerical experiments contribute to validate our approach and to illustrate its potential benefits.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Modeling and solving the non-smooth arc routing problem with realistic soft constraints

  • De Armas, Jésica
  • Ferrer, Albert
  • Juan, Angel A.
  • Lalla-Ruiz, Eduardo
This paper considers the non-smooth arc routing problem (NS-ARP) with soft constraints in order to capture in more perceptive way realistic constraints violations arising in transportation and logistics. To appropriately solve this problem, a biased-randomized procedure with iterated local search (BRILS) and a mathematical model for this ARP variant is proposed. An extensive computational study is conducted on rich and diverse problem instances. The results highlight the competitiveness of BRILS in terms of quality and time, where it provides high-quality solutions within reasonable computational times. In the context of real-world environments, the performance exhibited by BRILS motivates its incorporation in intelligent and integrative systems where frequent and fast solutions are required., Supported by the Spanish Ministry of Economy and Competitiveness & FEDER (TRA2015-71883-REDT, TRA2013-48180-C3-P, SEV-2015-0563).
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

SimILS: a simulation-based extension of the iterated local search metaheuristic for stochastic combinatorial optimization

  • Grasas, Àlex
  • Juan, Angel A.
  • Ramalhinho-Lourenço, Helena
Iterated Local Search (ILS) is one of the most popular single-solution-based metaheuristics. ILS is recognized by many authors as a relatively simple yet efficient framework able to deal with complex combinatorial optimization problems (COPs). ILS-based algorithms have been successfully applied to provide near-optimal solutions to different COPs in logistics, transportation, production, etc. However, ILS is designed to solve COPs under deterministic scenarios. In some real-life applications where uncertainty is present, the deterministic assumption makes the model less accurate since it does not reflect the real stochastic nature of the system. This paper presents the SimILS framework that extends ILS by integrating simulation to be able to cope with Stochastic COPs in a natural way. The paper also describes several tested applications that illustrate the main concepts behind SimILS and give rise to a new brand of ILS-based algorithms., This work has been partially supported by the Spanish Ministry of Economy and Competitiveness (TRA2013-48180-C3-P) and by the Ibero-American Programme for Science, Technology and Development (CYTED2010-511RT0419).
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Multi criteria biased randomized method for resource allocation in distributed systems: Application in a volunteer computing system

  • Panadero, Javier
  • De Armas, Jésica
  • Serra, Xavier
  • Marquès, Joan Manuel
Volunteer computing is a type of distributed computing in which a part or all the resources (processing power and storage) necessary to run the system are donated by users. In other words, participants contribute their idle computing resources to help running the system. Due to the fact that the nodes which compose the system are provided by a large number of users instead of a single (or a few) institution, a main drawback of volunteer computing is the unreliability of these nodes. For this reason, the selection of nodes to be involved in each task becomes a key issue. In this paper, we propose the Multi Criteria Biased Randomized (MCBR) method, a novel selection method for large-scale systems that use unreliable nodes. MCBR method is based on a multicriteria optimization strategy. We evaluated the method in a microblogging social network formed by a large number of microservices hosted in nodes voluntarily contributed by their participants. Simulation results show that our proposal is able to select nodes in a fast and efficient manner while requiring low computational power., This work has been partially supported by the Spanish Ministry of Economy and Competitiveness (TRA2013-48180-C3-P, TRA2015-71883-REDT), FEDER and the Erasmus+ programme (20161ES01KA108023465).
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Generic Pareto local search metaheuristic for optimization of targeted offers in a bi-objective direct marketing campaign

  • Coelho, Vitor Nazário
  • Oliveira, Thays Aparecida de
  • Coelho, Igor Machado
  • Coelho, Bruno N.
  • Fleming, Peter J.
  • Guimarães, Frederico G.
  • Ramalhinho-Lourenço, Helena
  • Souza, Marcone Jamilson Freitas
  • Talbi, El-Ghazali
  • Lust, Thibaut
Cross-selling campaigns seek to offer the right products to the set of customers with the goal of maximizing expected profit, while, at the same time, respecting the purchasing constraints set by investors. In this context, a bi-objective version of this NP-Hard problem is approached in this paper, aiming at maximizing both the promotion campaign total profit and the risk-adjusted return, which is estimated with the reward-to-variability ratio known as Sharpe ratio. Given the combinatorial nature of the problem and the large volume of data, heuristic methods are the most common used techniques. A Greedy Randomized Neighborhood Structure is also designed, including the characteristics of a neighborhood exploration strategy together with a Greedy Randomized Constructive technique, which is embedded in a multi-objective local search metaheuristic. The latter combines the power of neighborhood exploration by using a Pareto Local Search with Variable Neighborhood Search. Sets of non-dominated solutions obtained by the proposed method are described and analyzed for a number of problem instances., The authors would like to thank Brazilian agency CAPES, CNPq (grants 305506/2010-2, 552289/2011-6, 306694/2013-1 and 312276/2013-3), FAPEMIG (grants APQ-04611-10, PPM CEX497-13) and FP7 CORDIS, “New Horizons for Multi Criteria Decision Making”, for supporting the development of this work. Helena Ramalhinho was also partially supported by the Spanish Ministry of Economy and Competitiveness (TRA2013- 48180-C3-P, TRA2015-71883-REDT).
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Designing e‐commerce supply chains: a stochastic facility–location approach

  • Pagès Bernaus, Adela
  • Ramalhinho-Lourenço, Helena
  • Juan, Angel A.
  • Calvet Mir, Laura
E‐Commerce activity has been increasing during recent years, and this trend is expected to continue in the near future. e‐Commerce practices are subject to uncertainty conditions and high variability in customers’ demands. Considering these characteristics, we propose two facility–location models that represent alternative distribution policies in e‐commerce (one based on outsourcing and another based on in‐house distribution). These models take into account stochastic demands as well as more than one regular supplier per customer. Two methodologies are then introduced to solve these stochastic versions of the well‐known capacitated facility–location problem. The first is a two‐stage stochastic‐programming approach that uses an exact solver. However, we show that this approach is not appropriate for tackle large‐scale instances due to the computational effort required. Accordingly, we also introduce a “simheuristic” approach that is able to deal with large‐scale instances in short computing times. An extensive set of benchmark instances contribute to illustrate the efficiency of our approach, as well as its potential utility in modern e‐commerce practices., This work has been partially supported by the Spanish Ministry of Economy and Competitiveness and FEDER (TRA2013-48180-C3-P, TRA2015-71883-REDT) and the Erasmus+ programme (2016-1-ES01-KA108-023465). We also thank the support of the UOC doctoral programme.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

A VNS approach for book marketing campaigns generated with quasi-bicliques probabilities

  • Oliveira, Thays Aparecida de
  • Coelho, Vitor Nazário
  • Ramalhinho-Lourenço, Helena
  • Souza, Marcone Jamilson Freitas
  • Coelho, Bruno N.
  • Rezende, Daniel C.
  • Coelho, Igor Machado
This paper focuses on Book Marketing Campaigns, where the benefit of offering each book is calculated based on a bipartite graph (biclique). A quasi Biclique problem is assessed for obtaining the probabilities of success of a given client buy a given book, considering it had received another book as free offer. The remaining optimization decision problem can be solved following the Targeted Offers Problem in Direct Marketing Campaigns. The main objective is to maximize the feedback of customers purchases, offering books to the set of customers with the highest probability of buying others ones from its biclique and, at the same time, minimizing campaign operational costs. Given the combinatorial nature of the problem and the large volume of data, which can involve real cases with up to one million customers, metaheuristics procedures have been used as an efficient way for solving it. Here, a hybrid trajectory search based algorithm, namely GGVNS, which combines the Greedy Randomized Adaptive Search Procedures and General Variable Neighborhood Search, is used. The strategy for generating the quasi Biclique problem is described and a new instance generator for the TOPDMC is introduced. Computational results regarding the GGVNS algorithm shows it is able to find useful and profitable sets of clients., The authors thank the Brazilian agencies CNPq (grants 306694/2013-1, 552289/2011-6 and 202380/2012-2) and FAPEMIG (grants PPM CEX 772/15 and APQ-04611-10) for supporting the development of this work. Helena Ramalhinho was also partially supported by the Spanish Ministry of Economy and Competitiveness (TRA2013-48180-C3-P, TRA2015-71883-REDT).
Recercat. Dipósit de la Recerca de Catalunya
Publicación Capítulo o parte de un libro (BookPart)

Iterated local search: framework and applications

  • Ramalhinho-Lourenço, Helena
  • Martin, Olivier C.
  • Stützle, Thomas
The key idea underlying iterated local search is to focus the search not on the full space of all candidate solutions but on the solutions that are returned by some underlying algorithm, typically a local search heuristic. The resulting search behavior can be characterized as iteratively building a chain of solutions of this embedded algorithm. The result is also a conceptually simple metaheuristic that nevertheless has led to state-of-the-art algorithms for many computationally hard problems. In fact, very good performance is often already obtained by rather straightforward implementations of the metaheuristic. In addition, the modular architecture of iterated local search makes it very suitable for an algorithm engineering approach where, progressively, the algorithm’s performance can be further optimized. Our purpose here is to give an accessible description of the underlying principles of iterated local search and a discussion of the main aspects that need to be taken into account for a successful application of it. In addition, we review the most important applications of this method and discuss its relationship with other metaheuristics., Helena Ramalhinho Lourenço acknowledges support from the Spanish Ministry of Economy and Competitiveness (TRA2013-48180-C3-P, TRA2015-71883-REDT), and Thomas Stützle acknowledges support from the F.R.S.-FNRS, of which he is a research director. This work received support from the COMEX project P7/36 within the Interuniversity Attraction Poles Programme of the Belgian Science Policy Office.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Biased randomization of heuristics using skewed probability distributions: a survey and some applications

  • Grasas, Àlex
  • Juan, Angel A.
  • Faulin, Javier
  • De Armas, Jésica
  • Ramalhinho-Lourenço, Helena
Randomized heuristics are widely used to solve large scale combinatorial optimization problems. Among the plethora of randomized heuristics, this paper reviews those that contain biased-randomized procedures (BRPs). A BRP is a procedure to select the next constructive ‘movement’ from a list of candidates in which their elements have different probabilities based on some criteria (e.g., ranking, priority rule, heuristic value, etc.). The main idea behind biased randomization is the introduction of a slight modification in the greedy constructive behavior that provides a certain degree of randomness while maintaining the logic behind the heuristic. BRPs can be categorized into two main groups according to how choice probabilities are computed: (i) BRPs using an empirical bias function; and (ii) BRPs using a skewed theoretical probability distribution. This paper analyzes the second group and illustrates, throughout a series of numerical experiments, how these BRPs can benefit from parallel computing in order to significantly outperform heuristics and even simple metaheuristic approaches, thus providing reasonably good solutions in ‘real time’ to different problems in the areas of transportation, logistics, and scheduling., This work has been partially supported by the Spanish Ministry of Economy and Competitiveness and FEDER (TRA2013-48180-C3-P, TRA2015-71883-REDT), the Ibero-American Program for Science and Technology for Development (CYTED2014-515RT0489), and the Erasmus+ Program (2016-1-ES01-KA108-023465).
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

An ILS-based algorithm to solve a large-scale real heterogeneous fleet VRP with multi-trips and docking constraints

  • Coelho, Vitor Nazário
  • Grasas, Àlex
  • Ramalhinho-Lourenço, Helena
  • Coelho, Igor Machado
  • Souza, Marcone Jamilson Freitas
  • Cruz, R. C.
Distribution planning is crucial for most companies since goods are rarely produced and consumed at the same place. Distribution costs, in addition, can be an important component of the final cost of the products. In this paper, we study a VRP variant inspired on a real case of a large distribution company. In particular, we consider a VRP with a heterogeneous fleet of vehicles that are allowed to perform multiple trips. The problem also includes docking constraints in which some vehicles are unable to serve some particular customers, and a realistic objective function with vehicles’ fixed and distance-based costs and a cost per customer visited. We design a trajectory search heuristic called GILS-VND that combines Iterated Local Search (ILS), Greedy Randomized Adaptive Search Procedure (GRASP) and Variable Neighborhood Descent (VND) procedures. This method obtains competitive solutions and improves the company solutions leading to significant savings in transportation costs., This work has been partially supported by CNPq (grants 552289/2011-6 and 306458/2010-1), FAPEMIG (grants PPM CEX 497-13, APQ-04611-10), CAPES and Science Without Borders (grant 202380/2012-2 and 202381/2012-9), the Spanish Ministry of Economy and Competitiveness (TRA2013-48180-C3-P) and the Ibero-American Programme for Science, Technology and Development (CYTED2010-511RT0419).
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

A BRILS metaheuristic for non-smooth flow-shop problems with failure-risk costs

  • Ferrer, Alberto
  • Guimarans, Daniel
  • Ramalhinho-Lourenço, Helena
  • Juan, Angel A.
This paper analyzes a realistic variant of the Permutation Flow-Shop Problem (PFSP) by considering a non-smooth objective function that takes into account not only the traditional makespan cost but also failure-risk costs due to uninterrupted operation of machines. After completing a literature review on the issue, the paper formulates an original mathematical model to describe this new PFSP variant. Then, a Biased-Randomized Iterated Local Search (BRILS) algorithm is proposed as an efficient solving approach. An oriented (biased) random behavior is introduced in the well-known NEH heuristic to generate an initial solution. From this initial solution, the algorithm is able to generate a large number of alternative good solutions without requiring a complex setting of parameters. The relative simplicity of our approach is particularly useful in the presence of non-smooth objective functions, for which exact optimization methods may fail to reach their full potential. The gains of considering failure-risk costs during the exploration of the solution space are analyzed throughout a series of computational experiments. To promote reproducibility, these experiments are based on a set of traditional benchmark instances. Moreover, the performance of the proposed algorithm is compared against other state-of-the-art metaheuristic approaches, which have been conveniently adapted to consider failure-risk costs during the solving process. The proposed BRILS approach can be easily extended to other combinatorial optimization problems with similar non-smooth objective functions., This research has been partially supported by the Spanish Ministry of Economy and Competitiveness, projects MTM2011-29064-C03-02, MTM2014-59179-C2-01 & TRA2013-48180-C3-P, and FEDER. NICTA is funded by the Australian Government through the Department of Communications and the Australian Research Council through the ICT Centre of Excellence Program.
Dipòsit Digital de Documents de la UAB
Publicación Artículo científico (JournalArticle)

Combining variable neighborhood search with simulation for the inventory routing problem with stochastic demands and stock-outs

  • Gruler, Aljoscha|||0000-0003-0510-117X
  • Panadero, Javier|||0000-0002-3793-3328
  • Armas Adrián, Jésica de|||0000-0002-7619-7407
  • Moreno Pérez, José Andrés|||0000-0001-9506-5197
  • Juan, Ángel A|||0000-0003-1392-1776
Vendor managed inventory aims at reducing supply chain costs by centralizing inventory management and vehicle routing decisions. This integrated supply chain approach results in a complex combinatorial optimization problem known as the inventory routing problem (IRP). This paper presents a variable neighborhood search metaheuristic hybridized with simulation to solve the IRP under demand uncertainty. Our simheuristic approach is able to solve large sized instances for the single period IRP with stochastic demands and stock-outs in very short computing times. A range of experiments underline the algorithm's competitiveness compared to previously used heuristic approaches. The results are analyzed in order to provide closer managerial insights.
Dipòsit Digital de Documents de la UAB
Publicación Artículo científico (JournalArticle)

Multi criteria biased randomized method for resource allocation in distributed systems, application in a volunteer computing system

  • Panadero, Javier|||0000-0002-3793-3328
  • Armas Adrián, Jésica de|||0000-0002-7619-7407
  • Serra, Xavier
  • Marquès Puig, Joan Manuel
Volunteer computing is a type of distributed computing in which a part or all the resources (processing power and storage) necessary to run the system are donated by users. In other words, participants contribute their idle computing resources to help running the system. Due to the fact that the nodes which compose the system are provided by a large number of users instead of a single (or a few) institution, a main drawback of volunteer computing is the unreliability of these nodes. For this reason, the selection of nodes to be involved in each task becomes a key issue. In this paper, we propose the Multi Criteria Biased Randomized (MCBR) method, a novel selection method for large-scale systems that use unreliable nodes. MCBR method is based on a multicriteria optimization strategy. We evaluated the method in a microblogging social network formed by a large number of microservices hosted in nodes voluntarily contributed by their participants. Simulation results show that our proposal is able to select nodes in a fast and efficient manner while requiring low computational power.