Search

Selecting or adjusting attribute-levels (e.g. components, equipments, flavors, ingredients, prices, tastes) for multiple new and/or status quo products is an important task for a focal firm in a dynamic market. Usually, the goal is to maximize expected overall buyers' welfare based on consumers' partworths or expected revenue, market share, and profit under given assumptions. However, in general, these so-called product-line design problems cannot be solved exactly in acceptable computing time. Therefore, heuristics have been proposed: Two-stage heuristics select promising candidates for single products and evaluate sets of them as product-lines. One-stage heuristics directly search for multiple attribute-level combinations. In this paper, Ant Colony Optimization, Genetic Algorithms, Particle Swarm Optimization, Simulated Annealing and, firstly, Cluster-based Genetic Algorithm and Max-Min Ant Systems are applied to 78 small- to large-size product-line design problem instances. In contrast to former comparisons, data is generated according to a large sample of commercial conjoint analysis applications (n = 2,089). The results are promising: The firstly applied heuristics outperform the established ones. [ABSTRACT FROM AUTHOR]

We consider the block relocation problem (BRP), a combinatorial optimization problem that may arise in storage systems where items are organized in stacks. The objective is to retrieve all items in a predefined order with a minimal number of relocations. It can be distinguished between a restricted and an unrestricted version of the BRP. While in the restricted BRP (R-BRP) only relocations of items located above the item to be retrieved next are permitted, in the unrestricted BRP (U-BRP) all possible relocations are allowed. Existing exact methods concerning the BRP are frequently search-based methods which appear to be very effective. Nevertheless, recent literature concerning the R-BRP has shown that model-based methods can be competitive and therefore should also be taken into consideration. In this paper, we propose a new model-based approach for the U-BRP. It eliminates the fact that the number of variables is increasing with the number of necessary relocations; a disadvantage most mathematical models for the U-BRP have in common. [ABSTRACT FROM AUTHOR]

Since the 1960s, automated approaches to examination timetabling have been explored and a wide variety of approaches have been investigated and developed. In this paper we build upon a recently presented, sequential solution improvement technique which searches efficiently over a very large set of “adjacent” (neighbourhood) solutions. This solution search methodology, originally developed by Ahuja and Orlin, has been applied successfully in the past to a number of difficult combinatorial optimisation problems. It is based on an improvement graph representation of solution adjacency and identifies improvement moves by finding cycle exchange operations using a modified shortest path label-correcting algorithm. We have drawn upon Ahuja–Orlin’s basic methodology to develop an effective automated exam timetabling technique. We have evaluated our approach against the latest methodologies in the literature on standard benchmark problems. We demonstrate that our approach produces some of the best known results on these problems. [ABSTRACT FROM AUTHOR]

Combinatorial optimization plays an important role in real-world problem solving. In the big data era, the dimensionality of a combinatorial optimization problem is usually very large, which poses a significant challenge to existing solution methods. In this paper, we examine the generalization capability of a machine learning model for problem reduction on the classic travelling salesman problems (TSP). We demonstrate that our method can greedily remove decision variables from an optimization problem that are predicted not to be part of an optimal solution. More specifically, we investigate our model's capability to generalize on test instances that have not been seen during the training phase. We consider three scenarios where training and test instances are different in terms of: (1) problem characteristics; (2) problem sizes; and (3) problem types. Our experiments show that this machine learning-based technique can generalize reasonably well over a wide range of TSP test instances with different characteristics or sizes. Since the accuracy of predicting unused variables naturally deteriorates as a test instance is further away from the training set, we observe that, even when tested on a different TSP problem variant, the machine learning model still makes useful predictions about which variables can be eliminated without significantly impacting solution quality. [ABSTRACT FROM AUTHOR]

Copyright of OR Spectrum is the property of Springer Nature and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

We consider the Distribution problem for multiline palletizing systems, which arises in centralized distribution centres, where boxes have to be stacked up from conveyor belts onto pallets with respect to customer orders. The problem asks how to distribute boxes to k buffer queues such that an optimal subsequent stacking process requires only p stack-up places. The boxes reach the palletizer on the main conveyor of an order-picking system. A distribution conveyor pushes the boxes out to several buffer conveyors. Robotic arms are placed at the end of these buffer conveyors, where each arm picks up the first box of one of the buffer conveyors and moves it onto a pallet located at one of p stack-up places. In this paper, we seek for an assignment of the boxes from the main conveyor to the buffer conveyors such that only p stack-up places are used during the subsequent stacking process. We present online algorithms and analyse their worst-case behaviour. For restricted problems, an optimal online algorithm is given, which also performs very well for general instances. The average-case behaviour is determined by experiments. For benchmarking the general case, we present two binary integer programs. The Distribution problem for stacking systems has not been investigated up to now, although it is a natural problem to consider. [ABSTRACT FROM AUTHOR]

Packing problems (sometimes also called cutting problems) are combinatorial optimization problems concerned with placement of objects (items) in one or several containers. Some packing problems are special cases of several other problems such as resource-constrained scheduling, capacitated vehicle routing, etc. In this paper we consider a bounding technique for one- and higher-dimensional orthogonal packing problems, called conservative scales ( CS) (in the scheduling terminology, redundant resources). CS are related to the possible structure of resource consumption: filling of a bin, distribution of the resource to the jobs, etc. In terms of packing, CS are modified item sizes such that the set of feasible packings is not reduced. In fact, every CS represents a valid inequality for a certain binary knapsack polyhedron. CS correspond to dual variables of the set-partitioning model of a special 1D cutting-stock problem. Some CS can be constructed by (data-dependent) dual-feasible functions (( D) DFFs). We discuss the relation of CS to DFFs: CS assume that at most one copy of each object can appear in a combination, whereas DFFs allow several copies. The literature has investigated the so-called extremal maximal DFFs ( EMDFFs) which should provide very strong CS. Analogously, we introduce the notions of maximal CS ( MCS) and extremal maximal CS ( EMCS) and show that EMDFFs do not necessarily produce (E)MCS. We propose fast greedy methods to 'maximize' a given CS. Using the fact that EMCS define facets of the binary knapsack polyhedron, we use lifted cover inequalities as EMCS. For higher-dimensional orthogonal packing, we propose a Sequential LP ( SLP) method over the set of CS and investigate its convergence. Numerical results are presented. [ABSTRACT FROM AUTHOR]

In this paper, we present a corridor method inspired algorithm for a blocks relocation problem in block stacking systems. Typical applications of such problem are found in the stacking of container terminals in a yard, of pallets and boxes in a warehouse, etc. The proposed algorithm applies a recently proposed metaheuristic. In a method-based neighborhood we define a two-dimensional 'corridor' around the incumbent blocks configuration by imposing exogenous constraints on the solution space of the problem and apply a dynamic programming algorithm capturing the state of the system after each block movement for exploring the neighborhoods. Computational results on medium- and large-size problem instances allow to draw conclusions about the effectiveness of the proposed scheme. [ABSTRACT FROM AUTHOR]

Combinatorial optimization problems are often too complex to be solved within reasonable time limits by exact methods, in spite of the theoretical guarantee that such methods will ultimately obtain an optimal solution. instead, heuristic methods, which do not offer a convergence guarantee, but which have greater flexibility to take advantage of special properties of the search space, are commonly a preferred alternative. The standard procedure is to craft a heuristic method to suit the particular characteristics of the problem at hand, exploiting to the extent possible the structure available. Such tailored methods, however, typically have limited usefulness in other problems domains. An alternative to this problem specific solution approach is a more general methodology that recasts a given problem into a common modeling format, permitting solutions to be derived by a common, rather than tailor-made, heuristic method. Because such general purpose heuristic approaches forego the opportunity to capitalize on domain-specific knowledge, they are characteristically unable to provide the effectiveness or efficiency of special purpose approaches. indeed, they are typically regarded to have little value except for dealing with small or simple problems. This paper reports on recent work that calls this commonly held view into question. We describe how a particular unified modeling framework, coupled with latest advances in heuristic search methods, makes it possible to solve problems from a wide range of important model classes. [ABSTRACT FROM AUTHOR]

This paper extends Markov chain bootstrapping to the case of multivariate continuous-valued stochastic processes. To this purpose, we follow the approach of searching an optimal partition of the state space of an observed (multivariate) time series. The optimization problem is based on a distance indicator calculated on the transition probabilities of the Markov chain. Such criterion aims at grouping those states exhibiting similar transition probabilities. A second methodological contribution is represented by the addition of a contiguity constraint, which is introduced to force the states to group only if they have 'near' values (in the state space). This requirement meets two important aspects: first, it allows a more intuitive interpretation of the results; second, it contributes to control the complexity of the problem, which explodes with the cardinality of the states. The computational complexity of the optimization problem is also addressed through the introduction of a novel Tabu Search algorithm, which improves both the quality of the solution found and the computing times with respect to a similar heuristic previously advanced in the literature. The bootstrap method is applied to two empirical cases: the bivariate process of prices and volumes of electricity in the Spanish market; the trivariate process composed of prices and volumes of a US company stock (McDonald's) and prices of the Dow Jones Industrial Average index. In addition, the method is compared with two other well-established bootstrap methods. The results show the good distributional properties of the present proposal, as well as a clear superiority in reproducing the dependence among the data. [ABSTRACT FROM AUTHOR]

Distributors are faced with loading constraints in their route planning, e.g.,multi-dimensional packing constraints, unloading sequence constraints, stability constraints and axle weight limits. Ignoring these constraints impairs planning and induces last-minute changes resulting in additional costs. Developing vehicle routing models incorporating loading constraints is critical to more efficient route planning. The last couple of years has seen a huge increase of contributions to this field of research with almost 60 % of these being published after 2009. Our contribution is twofold. First, we overview the recent developments in the literature on all vehicle types in which loading constraints play a key role (trucks, airplanes, ships, and automated guided vehicles), using a state-of-the-art classification scheme to identify the loading constraints considered in each article. Second, we identify research gaps and opportunities for future research. [ABSTRACT FROM AUTHOR]

A new optimization approach is introduced for designing a public transit network. The main innovation of this paper is that the demand for public transit is endogenous. We maximize the total number of expected public transit passengers subject to a budget constraint. The demand depends on the established routes and their frequencies. A binary logit model is applied to simulate the behavior of the potential customers where the expected utility for public transit depends on in-vehicle time, waiting time, and access time. The expected waiting time depends on the frequency of the transit routes. The approach has been tested for the City of Dresden in Germany. The computational experiments show that the approach is applicable to real-world situations. [ABSTRACT FROM AUTHOR]

Assembly line balancing problems (ALBP) consist of distributing the total workload for manufacturing any unit of the products to be assembled among the work stations along a manufacturing line as used in the automotive or the electronics industries. Usually, theory assumes that, within each station, tasks can be executed in an arbitrary precedence-feasible sequence without changing station times. In practice, however, the task sequence may influence the station time considerably as sequence-dependent setups (e.g., walking distances, tool changes) have to be considered. Including this aspect leads to a joint balancing and scheduling problem, which we call SUALBSP ( set up assembly line balancing and scheduling problem). In this paper, we modify the problem by modeling setups more realistically, give a new, more compact mathematical model formulation and develop effective heuristic solution procedures. Computational experiments based on existing and new data sets indicate that the new procedures outperform formerly proposed heuristics. They are able to solve problem instances of real-world size with small deviations from optimality in computation times short enough to be accepted in real-world decision support systems. [ABSTRACT FROM AUTHOR]

In this paper, we describe an implementation of the iterated tabu search (ITS) algorithm for the quadratic assignment problem (QAP), which is one of the well-known problems in combinatorial optimization. The medium- and large-scale QAPs are not, to this date, practically solvable to optimality, therefore heuristic algorithms are widely used. In the proposed ITS approach, intensification and diversification mechanisms are combined in a proper way. The goal of intensification is to search for good solutions in the neighbourhood of a given solution, while diversification is responsible for escaping from local optima and moving towards new regions of the search space. In particular, the following enhancements were implemented: new formula for fast evaluation of the objective function and efficient data structure; extended intensification mechanisms (including randomized tabu criterion, combination of tabu search and local search, dynamic tabu list maintaining); enhanced diversification strategy using periodic tabu tenure and special mutation procedure. The ITS algorithm is tested on the different instances taken from the QAP library QAPLIB. The results from the experiments demonstrate promising efficiency of the proposed algorithm, especially for the random QAP instances. [ABSTRACT FROM AUTHOR]

Assembly line balancing problems (ALBP) arise whenever an assembly line is configured, redesigned or adjusted. An ALBP consists of distributing the total workload for manufacturing any unit of the products to be assembled among the work stations along the line. The sequence-dependent assembly line balancing problem (SDALBP) is an extension of the standard simple assembly line balancing problem (SALBP) which has significant relevance in real-world assembly line settings. SDALBP extends the basic problem by considering sequence-dependent task times. In this paper, we define this new problem, formulate several versions of a mixed-integer program, adapt solution approaches for SALBP to SDALBP, generate test data and perform some preliminary computational experiments. As a main result, we find that applying SALBP-based search procedures is very effective, whereas modelling and solving the problem with MIP standard software is not recommendable. [ABSTRACT FROM AUTHOR]

Electronics manufacturing systems employ increasingly multi-head gantry machines, where several vacuum nozzles are used simultaneously in pick-and-place operations to insert components on bare PCBs. Their use includes several options that have an impact on the overall manufacturing speed of the machine. In the present paper we address the problem of selecting the nozzles for this kind of a gantry machine, which is an important subproblem of the larger scheduling problem of multi-head gantry machines. Nozzles come in different types, and different types of components may require different types of nozzles in their placing. We address first a case where a single PCB type is manufactured and the only limitation on the number of nozzles is given by the capacity of the placement head. Then we discuss the case where there is a budget limitation on the total cost of the nozzles we can buy. We show that both of these problems can be solved optimally by the means of efficient greedy algorithms. We also discuss the case of selecting nozzles when manufacturing multiple different PCB types. [ABSTRACT FROM AUTHOR]

The vehicle routing problem with pickup and delivery and time windows (VRPPDTW) is one of the prominent members studied in the class of rich vehicle routing problems and it has become one of the challenges for developing heuristics which are accurate and fast at the same time. Indirect local search heuristics are ideally suited to flexibly handle complex constraints as those occurring in rich combinatorial optimization problems by separating the problem of securing feasibility of solutions from the objective-driven metaheuristic search process using simple encodings and appropriate decoders. In this paper we show that the approach of indirect local search with greedy decoding (GIST) is not only flexible and simple but when applied to the VRPPDTW it also gives results which are competitive with state-of-the-art VRPPDTW-methods by Li and Lim, as well as Pankratz. [ABSTRACT FROM AUTHOR]

In this paper we have proposed two heuristics for the one-dimensional bin-packing problem. One is a hybrid steady-state grouping genetic algorithm, whereas the other is an improved version of Perturbation MBS’ heuristic (Fleszar and Hindi in Comput Oper Res 29:821–839, 2002). A combined approach using these two heuristics gives results which are comparable with the best methods known so far. [ABSTRACT FROM AUTHOR]

One of the main advantages of portfolios over single assets is that risk can be diversified without necessarily reducing the expected return - provided "proper" assets are selected and they are assigned the "proper" weights. Since in practice investors tend to restrict themselves to a rather small number of different assets, the decision which securities to include is a crucial one that turns out to he NP-hard. In this paper we suggest a hybrid local search algorithm which combines principles of Simulated Annealing and evolutionary strategies and which proved to highly efficiently approach this problem. [ABSTRACT FROM AUTHOR]

In this study, we propose a reinforcement learning (RL) approach for minimizing the number of work overload situations in the mixed model sequencing (MMS) problem with stochastic processing times. The learning environment simulates stochastic processing times and penalizes work overloads with negative rewards. To account for the stochastic component of the problem, we implement a state representation that specifies whether work overloads will occur if the processing times are equal to their respective 25%, 50%, and 75% probability quantiles. Thereby, the RL agent is guided toward minimizing the number of overload situations while being provided with statistical information about how fluctuations in processing times affect the solution quality. To the best of our knowledge, this study is the first to consider the stochastic problem variation with a minimization of overload situations. [ABSTRACT FROM AUTHOR]

Most approaches to multi-project scheduling are based on the assumption that resources can be transferred between projects without any expense in time and cost. As this assumption often is not realistic, we generalise the multi-project scheduling problem (RCMPSP) by additionally including transfer times and cost. To integrate this aspect, in a first step, we develop a framework for considering resource transfers in single- and multi-project environments. It includes managerial approaches to handle resource transfers, a classification of resource transfer types and new roles that resources can take in these transfers. Afterwards, we define the multi-project scheduling problem with transfer times (RCMPPTT) and formulate it in a basic and an extended version as integer linear programmes. Eventually, it is supplemented for the first time by cost considerations and introduced as resource constrained multi-project scheduling problem with transfer times and cost (RCMPSPTTC). Computational experiments compare the presented managerial approaches and prove the necessity of explicitly considering transfer times in project scheduling already during the planning phase. Moreover, the experiments evaluate the presented MIP models and show that specialised solution procedures are vital. [ABSTRACT FROM AUTHOR]

This work deals with the proposal of some models for the schedule optimization problem for public transit networks. In particular, we consider the case of a transit terminal where passengers are supposed to split among different lines of a service, or even change mode of transportation in case of intermodal systems. Starting from a given schedule for the transit lines arriving at the terminal, the aim is to decide the optimal schedule for the output lines, in such a way to balance the operative costs of the service and the passenger waiting time at the transit terminal. We propose two different models for this problem, which present strong similarities with some well known combinatorial optimization models. Computational results are also presented, showing the suitability of the models to solve real case studies. [ABSTRACT FROM AUTHOR]