Local search for a multi-drop multi-container loading problem

We consider a complex variant of the Container Loading Problem arising from a real-world industrial application. It includes several features such as multiple containers, box rotation, and bearable weight, which are of importance in many practical situations. In addition, it also considers the situation in which boxes have to be delivered to different destinations (multi-drop). Our solution technique is based on local search metaheuristics. Local search works on the space of sequences of boxes to be loaded, while the actual load is obtained by invoking, at each iteration, a specialized procedure called loader. The loader inserts the boxes in the container using a deterministic heuristic which produces a load that is feasible according to the constraints. We test our solver on real-world instances provided by our industrial partner, showing a clear improvement on the previous heuristic solution. In addition, we compare our solver on benchmarks from the literature on the basic container loading problems. The outcome is that the results are in some cases in-line with the best ones in the literature and for other cases they also improve upon the best known ones. All instances and solutions are made available on the web for future comparisons.     

Simulated annealing for order spread minimization in sequencing cutting patterns

The Order Spread Minimization Problem (OSMP) is a sequencing problem that arises in the process of planning industrial cutting operations. As it can be looked upon as a generalization of the Travelling-Salesman Problem (TSP), it has to be classified as NP-complete. Thus heuristic algorithms are required in order to solve large problem instances. In this paper the authors suggest to apply Simulated Annealing (SA) to the OSMP. A specific version of SA is developed and compared to both an approach previously introduced into the literature by Madsen and a traditional 3-opt-procedure. The performance of these methods is compared on a set of 2400 randomly generated problem instances. SA appears to provide solutions which - in terms of solution quality - are equivalent to those generated by the 3-opt-procedure. However, computing times of the latter for solving large instances are prohibitive. In relation to Madsen's approach SA provides significantly improved solutions at the expense of a moderate increase in computing times.     

An exact solution framework for the minimum cost dominating tree problem

The minimum cost dominating tree problem is a recently introduced NP-hard problem, which consists of finding a tree of minimal cost in a given graph, such that for every node of the graph, the node or one of its neighbours is in the tree. We present an exact solution framework combining a primal–dual heuristic with a branch-and-cut approach based on a transformation of the problem into a Steiner arborescence problem with an additional constraint. The effectiveness of our approach is evaluated on testbeds proposed in literature containing instances with up to 500 nodes. Our framework manages to solve all but four instances from literature to proven optimality within 3 h (most of them in a few seconds). We provide optimal solution values for 69 instances from literature for which the optimal solution was previously unknown.     

Evolutionary search for difficult problem instances to support the design of job shop dispatching rules

Dispatching rules are simple scheduling heuristics that are widely applied in industrial practice. Their popularity can be attributed to their ability to flexibly react to shop floor disruptions that are prevalent in many real-world manufacturing environments. However, it is a challenging and time-consuming task to design local, decentralised dispatching rules that result in a good global performance of a complex shop.An evolutionary algorithm is developed to generate job shop problem instances for which an examined dispatching rule fails to achieve a good solution due to a single suboptimal decision. These instances can be easily analysed to reveal limitations of that rule which helps with the design of better rules. The method is applied to a job shop problem from the literature, resulting in new best dispatching rules for the mean flow time measure.     

Packing non-identical circles within a rectangle with open length

Packing non-identical circles inside a rectangle witnesses a wide range of industrial applications. However, the non-convex constraints in this problem make it intractable using exact analytical approaches. Even via heuristic methods, the solution time for industrial-scale instances sometimes is too long to be acceptable. This article aims to challenge the existing methods for the benchmark instances. The most significant contributions of this work are: firstly, we proposed three types of packing positions for selection and used human intelligence to convert an arbitrary circle sequence into a feasible compact layout; secondly, diverse position selection criteria have been tested, and it is found that the criterion commonly used in the literature is not the best; thirdly, the traditional genetic algorithm is adapted with lower crossover rate but higher mutation rate particularly, and a minor-adjustment operator with the purpose of exploring the neighborhood of the current best solutions is introduced.     

General variable neighborhood search for the uncapacitated single allocation <Emphasis Type="Italic">p</Emphasis>-hub center problem

In this paper we propose a general variable neighborhood search heuristic for solving the uncapacitated single allocation p-hub center problem (USApHCP). For the local search step we develop a nested variable neighborhood descent strategy. The proposed approach is tested on benchmark instances from the literature and found to outperform the state-of-the-art heuristic based on ant colony optimization. We also test our heuristic on large scale instances that were not previously considered as test instances for the USApHCP. Moreover, exact solutions were reached by our GVNS for all instances where optimal solutions are known.     

Diversification-driven tabu search for unconstrained binary quadratic problems

This paper describes a Diversification-Driven Tabu Search (D²TS) algorithm for solving unconstrained binary quadratic problems. D²TS is distinguished by the introduction of a perturbation-based diversification strategy guided by long-term memory. The performance of the proposed algorithm is assessed on the largest instances from the ORLIB library (up to 2500 variables) as well as still larger instances from the literature (up to 7000 variables). The computational results show that D²TS is highly competitive in terms of both solution quality and computational efficiency relative to some of the best performing heuristics in the literature.     

A GRASP based on DE to solve single machine scheduling problem with SDST

When handling combinatorial optimization problems, we try to get the optimal arrangement of discrete entities so that the requirements and the constraints are satisfied. These problems become more and more important in various industrial and academic fields. So, over the past years, several techniques have been proposed to solve them. In this paper, we are interested in the single machine scheduling problem with Sequence-Dependent Setup Times, which can be solved through different approaches. We present a hybrid algorithm which combines Greedy Randomized Adaptive Search Procedure and Differential Evolution for tackling this problem. Our algorithm is tested on benchmark instances from the literature. The computational experiments prove the efficiency of this algorithm.     

A note on exact and heuristic algorithms for the identical parallel machine scheduling problem

A recent paper (Davidovi? et al., J. Heuristics, 18:549?C569, 2012) presented a bee colony metaheuristic for scheduling independent tasks to identical processors, evaluating its performance on a benchmark set of instances from the literature. We examine two exact algorithms from the literature, the former published in 1995, the latter in 2008 (and not cited by the authors). We show that both such algorithms solve to proven optimality all the considered instances in a computing time that is several orders of magnitude smaller than the time taken by the new algorithm to produce an approximate solution.     

The two-echelon production-routing problem

This paper introduces the Two-Echelon Production-Routing Problem. This problem is motivated from the petrochemical industry, enlarging the supply chain integration by taking into account production, inventory, and routing decisions in a two-echelon vendor-managed inventory system. We describe, model, and design a branch-and-cut (B&C) to solve the problem under different inventory policies. We also propose a novel exact algorithm, by employing parallel computing techniques, in order to combine local search procedures within a traditional B&C scheme. We evaluate the performance of our methods through extensive computational experiments, both by comparing the algorithms, the effectiveness of the different inventory policies, and the impact of these policies on the partial costs. We derive many managerial insights based on the results. We also validate our new exact algorithm by solving similar problems from the literature, such as the two-echelon multi-depot inventory-routing (2E-MDIRP) and the classical multi-vehicle production-routing problem (MV-PRP). Computational experiments show that our method is very competitive. Based on 512 experiments for the 2E-MDIRP, our algorithm was able to find 111 new best known solutions (BKS), besides proving 412 optimal solutions, against 298 from the literature. For 336 experiments over small and medium size MV-PRP instances, we proved 242 optimal solutions, 11 more than the exact methods from the literature, besides providing 95 new BKS. Moreover, we were the first to tackle large MV-PRP instances exactly, and in this case, our algorithm provides all BKS for instances up to 50 customers, 20 periods and 5 vehicles, outperforming all meta/matheuristics procedures from the literature.     

A caving degree approach for the single container loading problem

Inspired by an old adage “Gold corner, silver side and strawy void”, and improved by a new observation “Maximum value in diamond cave”, a new heuristic approach is proposed for solving the three-dimensional single container loading problem. Differing from several previous approaches, its key issue is to pack the outside item into a corner or even a cave in the container such that the item is as compactly and closely as possible with other packed items. Experiments are on two groups of public and difficult benchmarks. For the 47 without-orientation-constraint instances from the OR-Library, experiments indicate an average packing utilization of 94.9%, which improves current best result reported in the literature by 3.9%. For the 800 strongly heterogeneous instances among 1500 representative benchmarks proposed by Bischoff et al., (100 instances in a set), experiments show an average packing utilization of 87.97%, which improves current best record reported in the literature by 0.28%. Besides, new best records are achieved on the latter five sets among the eight sets of strongly heterogeneous benchmarks.     

A mathematical formulation and complexity considerations for the blocks relocation problem

The blocks relocation problem (BRP) may be defined as follows: given a set of homogeneous blocks stored in a two-dimensional stock, which relocations are necessary to retrieve the blocks from the stock in a predefined order while minimizing the number of those relocations? In this paper, we first prove NP-hardness of the BRP as well as a special case, closing open research questions. Moreover, we propose different solution approaches. First, a mathematical model is presented that provides optimal solutions to the general BRP in cases where instances are small. To overcome such limitation, some realistic assumption taken from the literature is introduced, leading to the definition of a binary linear programming model. In terms of computational time, this approach is reasonably fast to be used to solve medium-sized instances. In addition, we propose a simple heuristic based upon a set of relocation rules. This heuristic is used to generate “good” quality solutions for larger instances in very short computational time, and, consequently, is proposed for tackling problem instances where solutions are required (almost) immediately. Solution quality of the heuristic is measured against optimal solutions obtained using a state-of-the-art commercial solver and both of them are compared with reference results from literature.     

A hybrid multistart heuristic for the uncapacitated facility location problem

We present a multistart heuristic for the uncapacitated facility location problem, based on a very successful method we originally developed for the p-median problem. We show extensive empirical evidence to the effectiveness of our algorithm in practice. For most benchmarks instances in the literature, we obtain solutions that are either optimal or a fraction of a percentage point away from it. Even for pathological instances (created with the sole purpose of being hard to tackle), our algorithm can get very close to optimality if given enough time. It consistently outperforms other heuristics in the literature.     

A new model for the asymmetric vehicle routing problem with simultaneous pickup and deliveries

The asymmetric vehicle routing problem with simultaneous pickup and deliveries is considered. This paper develops four new classes of valid inequalities for the problem. We generalize the idea of a no-good cut. Together, these help us solve 45-node randomly generated problem instances more efficiently. We report results on a set of benchmark instances in literature. In this set, we are able to show an order of magnitude improvement in computational times over currently published results in literature.     

A goal-driven prototype column generation strategy for the multiple container loading cost minimization problem

In the multiple container loading cost minimization problem (MCLCMP), rectangular boxes of various dimensions are loaded into rectangular containers of various sizes so as to minimize the total shipping cost. The MCLCMP can be naturally modeled as a set cover problem. We generalize the set cover formulation by introducing a new parameter to model the gross volume utilization of containers in a solution. The state-of-the-art algorithm tackles the MCLCMP using the prototype column generation (PCG) technique. PCG is an effective technique for speeding up the column generation technique for extremely hard optimization problems where their corresponding pricing subproblems are NP-hard. We propose a new approach to the MCLCMP that combines the PCG technique with a goal-driven search. Our goal-driven prototype column generation (GD-PCG) algorithm improves the original PCG approach in three respects. Computational experiments suggest that all three enhancements are effective. Our GD-PCG algorithm produces significantly better solutions for the 350 existing benchmark instances than all other approaches in the literature using less computation time. We also generate two new set instances based on industrial data and the classical single container loading instances.     

Clustering of search trajectory and its application to parameter tuning

This paper is concerned with automated classification of Combinatorial Optimization Problem instances for instance-specific parameter tuning purpose. We propose the CluPaTra Framework, a generic approach to CLUster instances based on similar PAtterns according to search TRAjectories and apply it on parameter tuning. The key idea is to use the search trajectory as a generic feature for clustering problem instances. The advantage of using search trajectory is that it can be obtained from any local-search based algorithm with small additional computation time. We explore and compare two different search trajectory representations, two sequence alignment techniques (to calculate similarities) as well as two well-known clustering methods. We report experiment results on two classical problems: Travelling Salesman Problem and Quadratic Assignment Problem and industrial case study.     

An exact algorithm for the node weighted Steiner tree problem

The Node Weighted Steiner Tree Problem (NW-STP) is a generalization of the Steiner Tree Problem. A lagrangean heuristic presented in EngevallS: StrLBN: 98, and based on the work in Lucena: 92, solves the problem by relaxing an exponential family of generalized subtour elimination constraints and taking into account only the violated ones as the computation proceeds. In EngevallS: StrLBN: 98 the computational results refer to complete graphs up to one hundred vertices. In this paper, we present a branch-and-bound algorithm based on this formulation. Its performance on the instances from the literature confirms the effectiveness of the approach. The experimentation on a newly generated set of benchmark problems, more similar to the real-world applications, shows that the approach is still valid, provided that suitable refinements on the bounding procedures and a preprocessing phase are introduced. The algorithm solves to optimality all of the considered instances up to one thousand vertices, with the exception of 11 hard instances, derived from the literature of a similar problem, the Prize Collecting Steiner Tree Problem. Received: March 2005, Revised: September 2005 AMS classification: 68M10, 90C10, 90C57 This work has been partially supported by the Ministero dell'Istruzione, Universitá e Ricerca (MIUR), Italy     

A metaheuristic approach to the dominating tree problem

This paper considers a recently introduced NP-hard problem on graphs, called the dominating tree problem. In order to solve this problem, we develop a variable neighborhood search (VNS) based heuristic. Feasible solutions are obtained by using the set of vertex permutations that allow us to implement standard neighborhood structures and the appropriate local search procedure. Computational experiments include two classes of randomly generated test instances and benchmark test instances from the literature. Optimality of VNS solutions on small size instances is verified with CPLEX.     

Order sequencing on a unidirectional cyclical picking line

A real life order-picking configuration that requires multiple pickers to cyclically move around fixed locations in a single direction is considered. This configuration is not the same, but shows similarities to, unidirectional carousel systems described in literature. The problem of minimising the pickers’ travel distance to pick all orders on this system is a variant of the clustered travelling salesman problem. An integer programming (IP) formulation of this problem cannot be solved in a realistic time frame for real life instances of the problem. A relaxation of this IP formulation is proposed that can be used to determine a lower bound on an optimal solution. It is shown that the solution obtained from this relaxation can always be transformed to a feasible solution for the IP formulation that is, at most, within one pick cycle of the lower bound. The computational results and performance of the proposed methods as well as adapted order sequencing approaches for bidirectional carousel systems from literature are compared to one another by means of real life historical data instances obtained from a retail distribution centre.     

Multiobjective scatter search for a commercial territory design problem

In this paper, a multiobjective scatter search procedure for a bi-objective territory design problem is proposed. A?territory design problem consists of partitioning a set of basic units into larger groups that are suitable with respect to some specific planning criteria. These groups must be compact, connected, and balanced with respect to the number of customers and sales volume. The bi-objective commercial territory design problem belongs to the class of NP-hard problems. Previous work showed that large instances of the problem addressed in this work are practically intractable even for the single-objective version. Therefore, the use of heuristic methods is the best alternative for obtaining approximate efficient solutions for relatively large instances. The proposed scatter search-based framework contains a diversification generation module based on a greedy randomized adaptive search procedure, an improvement module based on a relinked local search strategy, and a combination module based on a solution to an assignment problem. The proposed metaheuristic is evaluated over a variety of instances taken from literature. This includes a comparison with two of the most successful multiobjective heuristics from literature such as the Scatter Tabu Search Procedure for Multiobjective Optimization (SSPMO) by Molina et al. (INFORMS J. Comput. 19(1):91?C100, 2007), and the Non-dominated Sorting Genetic Algorithm (NSGA-II) by Deb et?al. (Parallel problem solving from nature ?C PPSN VI, Lecture notes in computer science, vol. 1917, Springer, Berlin, pp.?849?C858, 2000). Experimental work reveals that the proposed procedure consistently outperforms both heuristics, SSPMO and NSGA-II, on all instances tested.