Scheduling and assignment are relevant decisions widespread in complex organizations that produce goods or deliver services. Industrial companies and service providers periodically make these ...decisions that take into account their specific context in terms of objectives and constraints. As a consequence, a multitude of mathematical models for solving specific scheduling and assignment problems have been investigated in the literature. This paper tackles the problem differently by proposing a general two-phase decomposition framework in which the first phase grasps the key elements of the problem, while the second phase customizes the solution to the specific application addressed. Both phases are based on a mathematical model. The first model considers a set of kernel constraints and generates a set of patterns that link scheduling to assignment decisions. This model is flexible in the criteria used to generate the patterns and considers the finite and heterogeneous capacity of the critical resources to schedule and assign. The second model benefits from the patterns identified by the first phase, that reduce the solution space; this reduction is fundamental because the second model considers all the problem features. To show the generality of the approach, the methodology was applied in diverse application contexts by formulating the augmented pattern generation model with objective functions and constraints custom to the application context. Computational results, obtained from a pool of small to large instances generated from a case study in the Home Care sector, are also presented.
•We study optimization problems characterized by scheduling and assignment decisions.•We introduce augmented patterns, a new modeling tool to manage such decisions.•We propose effective decomposition approaches and study their properties.•The augmented pattern is instantiated in different applications to show generality.•A case study shows the advantages in terms of computation time and solution quality.
•This paper surveys the recent attempts, both from the machine learning and operations research communities, at leveraging machine learning to solve combinatorial optimization problems.•Given the ...hard nature of these problems, state-of-the-art algorithms rely on handcrafted heuristics for making decisions which are otherwise too expensive to compute or mathematically not well-defined. Thus, machine learning looks like a natural candidate to make such decisions in a more principled and optimized way. We advocate for pushing further the integration of machine learning and combinatorial optimization and detail a methodology to do so. A main point of the paper is seeing generic optimization problems as data points and inquiring what is the relevant distribution of problems to use for learning on a given task.
This paper surveys the recent attempts, both from the machine learning and operations research communities, at leveraging machine learning to solve combinatorial optimization problems. Given the hard nature of these problems, state-of-the-art algorithms rely on handcrafted heuristics for making decisions that are otherwise too expensive to compute or mathematically not well defined. Thus, machine learning looks like a natural candidate to make such decisions in a more principled and optimized way. We advocate for pushing further the integration of machine learning and combinatorial optimization and detail a methodology to do so. A main point of the paper is seeing generic optimization problems as data points and inquiring what is the relevant distribution of problems to use for learning on a given task.
•Survey of author’s research from 1972 to 2022.•Ten applications are presented.•Conclusions and avenues for future research are drawn.
In July 2022, I received the EURO Gold medal at the 32nd EURO ...Conference held in Espoo, Finland. This paper is based on the presentation I made at the medal award ceremony. It covers 10 topics on which I have worked throughout my career. These are the seriation problem, rotating work schedules, deterministic vehicle routing, stochastic vehicle routing, examination timetabling, districting, waste management, metro network design, green transportation, and humanitarian logistics.
High-value payment systems (HVPSs) are typically liquidity intensive because payments are settled on a gross basis. State-of-the-art solutions to this problem include algorithms that seek netting ...sets and allow for ad hoc reordering of submitted payments. This paper introduces a new algorithm that explores the entire space of payments reordering to improve the liquidity efficiency of these systems without significantly increasing payment delays. Finding the optimal payment order among the entire space of reorderings is, however, an NP-hard combinatorial optimization problem. We solve this problem using a hybrid quantum annealing algorithm. Despite the limitations in size and speed of today’s quantum computers, our algorithm provides quantifiable liquidity savings when applied to the Canadian HVPS using a 30-day sample of transaction data. By reordering batches of 70 payments, we achieve an average of Canadian (C) $240 million in daily liquidity savings, with a settlement delay of approximately 90 seconds. For a few days in the sample, the liquidity savings exceed C$1 billion. Compared with classical computing and with current algorithms in HVPS, our quantum algorithm offers larger liquidity savings, and it offers more reliable and consistent solutions, particularly under time constraints. This paper was accepted by Chung Piaw Teo, optimization. Supplemental Material: The data files are available at https://doi.org/10.1287/mnsc.2023.00314 .
In this paper, we study the Generalized Traveling Salesman Problem with Neighborhoods (GTSPN), a variant of the Traveling Salesman Problem (TSP), where the goal is to find the shortest path visiting ...each of the given neighborhood sets represented as a set of convex regions. The GTSPN is motivated by the sequencing problem of robotic manipulators, where an operation can be achieved from multiple locations, such as the visual inspection that can be performed from several possible views. The GTSPN formulation allows for exploiting continuous optimization to find the most suitable locations for the inspection, yielding possible solution cost reduction. Moreover, instances with overlapping high-dimensional convex regions further allow modeling neighborhood sets with complex shapes. We propose a novel approach to determine the first lower bounds to the studied GTSPN by employing the Branch-and-Bound (BB) method and the Mixed-Integer Second-Order Cone Programming (MISOCP) model for particular BB subproblems. In addition, the proposed method allows for solving the GTSPN to optima. The developed lower bound determination is further exploited in the empirical evaluation of existing heuristic approaches to the GTSPN and assesses the solution quality using the relative optimality gap. Regarding the presented results, the proposed BB-based approach provides tight lower bounds and solutions with up to 20% optimality gap for the GTSPN instances with less than 15 neighborhood sets for the given limited computational time. Furthermore, the presented results support that the proposed approach is suitable for solving high-dimensional instances of the GTSPN that can be found in inspection tasks with robotic manipulators.
•Novel Branch-and-Bound-based method providing the first lower bounds for the GTSPN.•GTSPN instances with high-dimensional regions are motivated by tasks with robotic manipulators.•Optimal solutions of the GTSPN instances with up to 12 sets.•Novel formulation of the GTSPN as the Mixed-Integer Second-Order Cone Programming.
We present a unifying framework for Selective Routing Problems (SRPs) through a systematic analysis. The common goal in SRPs is to determine an optimal vehicle route to serve a subset of vertices ...while covering another subset. They arise in diverse fields such as logistics, public health, disaster response, and urban development. To establish a unifying framework for different but related problems, we associate the notion of service with coverage and argue that routing is a tool of service. We classify SRPs according to their selectiveness degree and emphasize the breadth and depth of this problem in terms of its characteristics. This SRP framework helps us identify research gaps as well as potential future research areas. We present a generic mathematical model, use it to describe the connections among these problems and identify some identical problems presented under different names.
•We present a unifying framework and a generic model for Selective Routing Problems.•Problems in logistics, public health, disaster response, and urban development.•We classify SRPs according to their selectiveness degree.•We identify some identical problems presented under different names.•We identify research gaps as well as potential future research areas.
Many traditional algorithms for solving combinatorial optimization problems involve using hand-crafted heuristics that sequentially construct a solution. Such heuristics are designed by domain ...experts and may often be suboptimal due to the hard nature of the problems. Reinforcement learning (RL) proposes a good alternative to automate the search of these heuristics by training an agent in a supervised or self-supervised manner. In this survey, we explore the recent advancements of applying RL frameworks to hard combinatorial problems. Our survey provides the necessary background for operations research and machine learning communities and showcases the works that are moving the field forward. We juxtapose recently proposed RL methods, laying out the timeline of the improvements for each problem, as well as we make a comparison with traditional algorithms, indicating that RL models can become a promising direction for solving combinatorial problems.
•Survey explores synergy of combinatorial optimization and reinforcement learning.•It covers recent papers showing how RL can be applied to solve canonical CO problems.•Graph neural networks are used as a method for graph representation in RL for CO.•Policy-based and value-based RL methods are used to learn the solutions to CO tasks.•Most of the reported experiments do not overlap.•This makes it hard to fairly compare the surveyed methods.
Nature-inspired optimization algorithms can solve different engineering and scientific problems owing to their easiness and flexibility. There is no need for structural modifications of optimization ...problems to apply meta-heuristic algorithms on them. Recently, meta-heuristic algorithms are becoming powerful methods for solving NP problems. In this paper, the authors propose a novel meta-heuristic algorithm suitable for continuous nonlinear optimization problems. The proposed method, Black Widow Optimization Algorithm (BWO), is inspired by the unique mating behavior of black widow spiders. This method includes an exclusive stage, namely, cannibalism. Due to this stage, species with inappropriate fitness are omitted from the circle, thus leading to early convergence. BWO algorithm is evaluated on 51 various benchmark functions to verify its efficiency in obtaining the optimal solutions for the problems. The obtained results indicate that the proposed algorithm has numerous advantages in different aspects such as early convergence and achieving optimized fitness value compared to other algorithms. Also, it has the capability of providing competitive and promising results. The research also solves three different challenging engineering design problems adopting BWO algorithm. The outcomes of the real case study problems prove the effectiveness of the proposed algorithm in solving real-world issues with unknown and challenging spaces.
•A novel bio-inspired Black Widow Optimization (BWO) Algorithm is proposed.•BWO is inspired by the bizarre mating behavior of black widow spiders.•BWO is compared with GA, PSO, ABC and BBO using 51 different benchmark functions.•BWO converges to the optimal value as quickly as possible.•BWO outperforms the other experimental algorithms in majority of test functions.
PDF
