Meta Heuristics

Metaheuristic, Models and Software for the Heterogeneous Fleet Pickup and Delivery Problem with Split Loads

  • Diogenes Gasque
  • Pedro Munari
    • Categories Meta Heuristics, Optimization Software and Modeling Systems, Transportation Tags , , , ,

    This paper addresses a rich variant of the vehicle routing problem (VRP) that involves pickup and delivery activities, customer time windows, heterogeneous fleet, multiple products and the possibility of splitting a customer demand among several routes. This variant generalizes traditional VRP variants by incorporating features that are commonly found in practice. We present two mixed-integer … Read more

    Decomposition strategies for vehicle routing heuristics

  • Alberto Santini
  • Michael Schneider
  • Thibaut Vidal
  • Daniele Vigo
    • Categories Meta Heuristics, Transportation Tags , ,

    Decomposition techniques are an important component of modern heuristics for large instances of vehicle routing problems. The current literature lacks a characterisation of decomposition strategies and a systematic investigation of their impact when integrated into state-of-the-art heuristics. This paper fills this gap: we discuss the main characteristics of decomposition techniques in vehicle routing heuristics, highlight … Read more

    An Adaptive and Near Parameter-free BRKGA Using Q-Learning Method

  • Antonio Chaves
  • Luiz Henrique Lorena
    • Categories Meta Heuristics Tags , , ,

    The Biased Random-Key Genetic Algorithm (BRKGA) is an efficient metaheuristic to solve combinatorial optimization problems but requires parameter tuning so the intensification and diversification of the algorithm work in a balanced way. There is, however, not only one optimal parameter configuration, and the best configuration may differ according to the stages of the evolutionary process. … Read more

    Local search and swapping strategies.Challenging the greedy maximization of a polymatroid subject to a cardinality constraint

  • Mirco Soffritti
    • Categories Approximation Algorithms, Combinatorial Optimization, Meta Heuristics Tags , , , , , ,

    This paper studies the maximization of a polymatroid subject to a cardinality constraint. In particular, we consider the problem of improving the value of the greedy set by swapping one of its members with an element that does not belong to it. To achieve this goal, we first define a (set-based) post-greedy measure of curvature … Read more

    Scheduling the Brazilian OR Conference

  • Teobaldo Bulhões
  • Puca Huachi V. Penna
  • Anand Subramanian
  • Rubens Correia
    • Categories Meta Heuristics, Scheduling Tags , ,

    In this paper, we show how to efficiently schedule the Brazilian OR conference using a matheuristic approach. The event has traditionally around 300 presentations across a period of 3 to 4 days, and building a schedule for the technical sessions is an arduous task. The proposed algorithm integrates the concepts of iterated local search and … Read more

    A modern POPMUSIC matheuristic for the capacitated vehicle routing problem

  • Eduardo Queiroga
  • Ruslan Sadykov
  • Eduardo Uchoa
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Meta Heuristics

    This work proposes a partial optimization metaheuristic under special intensification conditions (POPMUSIC) for the classical capacitated vehicle routing problem (CVRP). The proposed approach uses a branch-cut-and-price algorithm as a powerful heuristic to solve subproblems whose dimensions are typically between 25 and 200 customers. The whole algorithm can be seen as the application of local search … Read more

    Modular-topology optimization with Wang tilings: An application to truss structures

  • Martin Doskar
  • Martin Kružík
  • Matej Lepš
  • Marek Tyburec
  • Jan Zeman
    • Categories Civil and Environmental Engineering, Convex Optimization, Meta Heuristics Tags , , , ,

    Modularity is appealing for solving many problems in optimization. It brings the benefits of manufacturability and reconfigurability to structural optimization, and enables a trade-off between the computational performance of a Periodic Unit Cell (PUC) and the efficacy of non-uniform designs in multi-scale material optimization. Here, we introduce a novel strategy for concurrent minimum-compliance design of … Read more

    Some heuristic methods for the p-median problem with maximum distance constraints. Application to a bi-objective problem.

  • Adrián Esteban-Pérez
  • Jesús Sáez-Aguado
  • Luis A. San-José
    • Categories Facility Planning and Design, Meta Heuristics Tags , , , , ,

    In this work we study the p-median problem with maximum distance constraints (PMPDC) which is a variant of the classical p-median problem (PMP). First of all, we provide some different formulations for (PMPDC) because the heuristics procedures for the (PMPDC) with a formulation based on the approach that modifies the distance matrix that leads to … Read more

    On Modeling Local Search with Special-Purpose Combinatorial Optimization Hardware

  • Xiaoyuan Liu
  • Avradip Mandal
  • Arnab Roy
  • Ilya Safro
  • Sarvagya Upadhyay
  • Hayato Ushijima-Mwesigwa
    • Categories Combinatorial Optimization, Meta Heuristics Tags , , ,

    As we approach the physical limits predicted by Moore’s law, a variety of specialized hardware is emerging to tackle specialized tasks in different domains. Within combinatorial optimization, adiabatic quantum computers, CMOS annealers, and optical parametric oscillators are few of the emerging specialized hardware technology aimed at solving optimization problems. In terms of mathematical framework, the … Read more

    Exact and Heuristic Approaches for a New Circular Layout Problem

  • Truden Christian
  • Philipp Hungerländer
  • Kerstin Maier
  • Veronika Pachatz
    • Categories (Mixed) Integer Linear Programming, Meta Heuristics, Production and Logistics Tags , , , ,

    We discuss a new facility layout problem, the so-called Directed Circular Facility Layout Problem (DCFLP). The DCFLP aims to find an optimal arrangement of machines on a circular material handling system such that the total weighted sum of the center-to-center distances between all pairs of machines measured in clockwise direction is minimized. Several real-world applications, … Read more