Meta Heuristics

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

    Flexible Job Shop Scheduling Problems with Arbitrary Precedence Graphs

  • Gregory A. Kasapidis
  • Dimitris C. Paraskevopoulos
  • Panagiotis P. Repoussis
  • Christos D. Tarantilis
    • Categories Meta Heuristics, Scheduling Tags , , , ,

    A common assumption in the shop scheduling literature is that the processing order of the operations of each job is sequential; however, in practice there can be multiple connections and finish-to-start dependencies among the operations of each job. This paper studies flexible job shop scheduling problems with arbitrary precedence graphs. Rigorous mixed integer and constraint … Read more

    Anomalous Behaviour of Dual-Based Heuristics

  • Trivikram Dokka
  • Adam N. Letchford
  • M. Hasan Mansoor
    • Categories 0-1 Programming, Combinatorial Optimization, Meta Heuristics Tags , , ,

    Some popular heuristics for combinatorial optimisation start by constructing a feasible solution to a dual of the problem. We show that such dual-based heuristics can exhibit highly counter-intuitive behaviour. In particular, for some problem classes, solving the dual exactly invariably leads to much worse primal solutions than solving the dual with a simple greedy heuristic. … Read more

    A Scenario-Based Approach for the Vehicle Routing Problem with Roaming Delivery Locations under Stochastic Travel Times

  • Joris Kinable
  • Afonso Sampaio
  • Lucas Veelenturf
  • Tom Van Woensel
    • Categories Meta Heuristics, Stochastic Programming, Transportation Tags , ,

    We address a stochastic variant of the Vehicle Routing Problem with Roaming Delivery Locations. In this model, direct-to-consumer deliveries can be made in the trunk of the customer’s car, while the vehicle is parked at a location along the customer’s itinerary. The stochasticity arises from the uncertainty in travel times and the problem is formulated … Read more

    The Benefits of Transfers in Crowdsourced Pickup-and-Delivery Systems

  • Afonso Sampaio
  • Martin Savelsbergh
  • Lucas Veelenturf
  • Tom Van Woensel
    • Categories Applications - OR and Management Sciences, Meta Heuristics, Transportation Tags , , ,

    Rapid urban growth, the increasing importance of e-commerce and high consumer service expectations have given rise to new and innovative models for freight delivery within urban environments. Crowdsourced solutions – where drivers are not employed by a carrier but occasionally offer their services through on-line platforms and are contracted as required by carriers – are … Read more

    A Tutorial on Formulating QUBO Models

  • Fred Glover
  • Gary Kochenberger
    • Categories 0-1 Programming, Combinatorial Optimization, Meta Heuristics Tags ,

    The field of Combinatorial Optimization (CO) is one of the most important areas in the general field of optimization, with important applications found in every industry, including both the private and public sectors. It is also one of the most active research areas pursued by the research communities of Operations Research, Computer Science, and Analytics … Read more

    A Decision Tool based on a Multi-Objective Methodology for designing High-Pressure Thermal Treatments in Food Industry

  • Miriam R. Ferrández
  • Benjamin Ivorra
  • Pilar M. Ortigosa
  • Ángel M. Ramos
  • Juana L. Redondo
    • Categories Meta Heuristics, Optimization of Systems modeled by PDEs, Systems governed by Differential Equations Optimization Tags , , , ,

    In this work, we propose a methodology for designing High-Pressure Thermal processes for food treatment. This approach is based on a multi-objective preference-based evolutionary optimization algorithm, called WASF-GA, combined with a decision strategy which provides the food engineer with the best treatment in accordance with some quality requirements. The resulting method is compared to a … Read more

    The job shop scheduling problem with convex costs

  • Kerem Bülbül
  • Reinhard Bürgy
    • Categories Applications - OR and Management Sciences, Meta Heuristics, Scheduling

    The job shop scheduling literature has been dominated by a focus on regular objective functions — in particular the makespan — in its half a century long history. The last twenty years have encountered a spike of interest in other objectives, such as the total weighted tardiness, but research on non-regular objective functions has always … Read more

    Recent Progress Using Matheuristics for Strategic Maritime Inventory Routing

  • Myun-Seok Cheon
  • George L. Nemhauser
  • Dimitri J. Papageorgiou
  • Stuart Harwood
  • Francisco Trespalacios
    • Categories (Mixed) Integer Linear Programming, Meta Heuristics, Transportation Tags , , , ,

    This paper presents an extensive computational study of simple, but prominent matheuristics (i.e., heuristics that rely on mathematical programming models) to fi nd high quality ship schedules and inventory policies for a class of maritime inventory routing problems. Our computational experiments are performed on a set of the publicly available MIRPLib instances. This class of inventory … Read more