Extended local search algorithm based on nonlinear programming for two-dimensional irregular strip packing problem

This paper presents an extended local search algorithm (ELS) for the irregular strip packing problem. It adopts two neighborhoods, swapping two given polygons in a placement and placing one polygon into a new position. The local search algorithm is used to minimize the overlap on the basis of the neighborhoods mentioned above and the unconstrained nonlinear programming model is adopted to further minimize the overlap during the search process. Moreover, the tabu search algorithm is used to avoid local minima, and a compact algorithm is presented to improve the result. The results of standard test instances indicate that when compared with other existing algorithms, the presented algorithm does not only show some signs of competitive power but also updates several best known results.     

Extended guided tabu search and a new packing algorithm for the two-dimensional loading vehicle routing problem

In this paper, we develop an extended guided tabu search (EGTS) and a new heuristic packing algorithm for the two-dimensional loading vehicle routing problem (2L-CVRP). The 2L-CVRP is a combination of two well-known NP-hard problems, the capacitated vehicle routing problem, and the two-dimensional bin packing problem. It is very difficult to get a good performance solution in practice for these problems. We propose a meta-heuristic methodology EGTS which incorporates theories of tabu search and extended guided local search (EGLS). It has been proved that tabu search is a very good approach for the CVRP, and the guiding mechanism of the EGLS can help tabu search to escape effectively from local optimum. Furthermore, we have modified a collection of packing heuristics by adding a new packing heuristic to solve the loading constraints in 2L-CVRP, in order to improve the cost function significantly. The effectiveness of the proposed algorithm is tested, and proven by extensive computational experiments on benchmark instances.     

A parallel hybrid local search algorithm for the container loading problem

In this contribution, a parallel hybrid local search algorithm for the three‐dimensional container loading problem (CLP) is proposed. First a simulated annealing method for the CLP is developed, which is then combined with an existing tabu search algorithm to form a hybrid metaheuristic. Finally, parallel versions are introduced for these algorithms. The emphasis is on CLP instances with a weakly heterogeneous load. Numerical tests based on the well‐known 700 test instances from Bischoff and Ratcliff are performed, and the outcome is compared with methods from other authors. The results show a high solution quality obtained with reasonable computing time.     

An iterated local search heuristic for multi-capacity bin packing and machine reassignment problems

This paper proposes an efficient Multi-Start Iterated Local Search for Packing Problems (MS-ILS-PPs) metaheuristic for Multi-Capacity Bin Packing Problems (MCBPP) and Machine Reassignment Problems (MRP). The MCBPP is a generalization of the classical bin-packing problem in which the machine (bin) capacity and task (item) sizes are given by multiple (resource) dimensions. The MRP is a challenging and novel optimization problem, aimed at maximizing the usage of available machines by reallocating tasks/processes among those machines in a cost-efficient manner, while fulfilling several capacity, conflict, and dependency-related constraints. The proposed MS-ILS-PP approach relies on simple neighborhoods as well as problem-tailored shaking procedures. We perform computational experiments on MRP benchmark instances containing between 100 and 50,000 processes. Near-optimum multi-resource allocation and scheduling solutions are obtained while meeting specified processing-time requirements (on the order of minutes). In particular, for 9/28 instances with more than 1000 processes, the gap between the solution value and a lower bound measure is smaller than 0.1%. Our optimization method is also applied to solve classical benchmark instances for the MCBPP, yielding the best known solutions and optimum ones in most cases. In addition, several upper bounds for non-solved problems were improved.     

Algorithms for the circular two‐dimensional open dimension problem

In this paper, we propose three heuristics for the circular two‐dimensional open dimension problem, also known as the circular strip cutting/packing problem. We first propose an open strip generation solution procedure that uses the best local position rule into the open strip. Second, we propose a simple augmented version of the first heuristic by introducing an exchange‐order strategy. Third, we propose a hybrid heuristic that combines beam search and a series of target values belonging to a predetermined interval search. We evaluate the performance of these heuristics on several instances varying from small to large ones. Encouraging results have been obtained.     

Variable neighbourhood search for the variable sized bin packing problem

The variable sized bin packing problem is a generalisation of the one-dimensional bin packing problem. Given is a set of weighted items, which must be packed into a minimum-cost set of bins of variable sizes and costs. This problem has practical applications, for example, in packing, transportation planning, and cutting. In this work we propose a variable neighbourhood search metaheuristic for tackling the variable sized bin packing problem. The presented algorithm can be seen as a hybrid metaheuristic, because it makes use of lower bounding techniques and dynamic programming in various algorithmic components. An extensive experimentation on a diverse set of problem instances shows that the proposed algorithm is very competitive with current state-of-the-art approaches.     

A greedy search for the three-dimensional bin packing problem: the packing static stability case

We suggest a greedy search heuristic for solving the three-dimensional bin packing problem (3D-BPP) where in addition to the usual requirement of minimum amount of bins being used, the resulting packing of items into the bins must be physically stable. The problem is NP-hard in the strong sense and imposes severe computational strain for solving it in practice. Computational experiments are also presented and the results are compared with those obtained by the Martello, Pisinger and Vigo (2000) heuristic.     

Superior solution guided particle swarm optimization combined with local search techniques

Particle swarm optimization (PSO) is an evolutionary algorithm known for its simplicity and effectiveness in solving various optimization problems. PSO should have strong yet balanced exploration and exploitation capabilities to enhance its performance. A superior solution guided PSO (SSG-PSO) framework integrated with an individual level based mutation operator and different local search techniques is proposed in this study. In SSG-PSO, a collection of superior solutions is maintained and updated with the evolutionary process, such that each particle can comprehensively learn from the recorded superior solutions. In addition, to maintain the diversity of the particle swarm, SSG-PSO is combined with an individual level based mutation operator, which will be invoked when a particle is trapped in a local optimum (determined by the fitness and position states of the particle), thereby improving the adaptation and flexibility of each individual particle. Moreover, two gradient-based local search techniques, namely, the Broyden–Fletcher–Goldfarb–Shanno (BFGS) and Davidon–Fletcher–Powell (DFP) Quasi–Newton methods, and two derivative-free local search techniques, namely, pattern search and Nelder–Mead simplex search, are incorporated into SSG-PSO. The performances of SSG-PSO and that of its local search enhanced variants are extensively and comparatively studied on a suit of benchmark optimization functions.     

A multi-start evolutionary local search for the two-dimensional loading capacitated vehicle routing problem

This paper addresses an extension of the capacitated vehicle routing problem where customer demand is composed of two-dimensional weighted items (2L-CVRP). The objective consists in designing a set of trips minimizing the total transportation cost with a homogenous fleet of vehicles based on a depot node. Items in each vehicle trip must satisfy the two-dimensional orthogonal packing constraints. A GRASP×ELS algorithm is proposed to compute solutions of a simpler problem in which the loading constraints are transformed into resource constrained project scheduling problem (RCPSP) constraints. We denote this relaxed problem RCPSP-CVRP. The optimization framework deals with RCPSP-CVRP and lastly RCPSP-CVRP solutions are transformed into 2L-CVRP solutions by solving a dedicated packing problem. The effectiveness of our approach is demonstrated through computational experiments including both classical CVRP and 2L-CVRP instances. Numerical experiments show that the GRASP×ELS approach outperforms all previously published methods.     

基于禁忌搜索的启发式算法求解带平衡约束的圆形装填问题

带平衡约束的圆形装填(Packing)问题是一类简化的卫星舱布局优化问题.现提出一个基于禁忌搜索的启发式(TSH)算法对该问题进行求解.算法从任一初始格局出发,应用基于自适应步长的梯度法进行能量极小化.为了使计算能有效地逃离局部极小点的陷阱且避免迂回搜索,算法采用了禁忌搜索的策略.在禁忌搜索的过程中,我们对传统的邻域解、禁忌对象以及当前解接受原则进行了有效的改进.对两组共11个有代表性的算例进行了实算.计算结果表明,TSH算法刷新了其中7个算例的当今国际上的最好纪录,对于其余4个算例,该算法均达到问题的最优解.     

Breakout local search for the multi-objective gate allocation problem

The problem of assigning gates to arriving and departing flights is one of the most important problems in airport operations. We take into account the real multi-criteria nature of the problem by optimizing a total of nine gate allocation objectives that are oriented both on convenience for airport/airline services and passenger comfort. As far as we are aware, this is the largest number of objectives jointly optimized in the GAP literature. Given the complexity of the considered problem, we propose a heuristic approach based on the Breakout Local Search (BLS) framework. BLS is a recent variant of the Iterated Local Search (ILS) with a particular focus on the perturbation strategy. Based on some relevant information on search history, it tries to introduce an appropriate degree of diversification by determining adaptively the number and type of moves for the next perturbation phase. Moreover, we use a new memory-based greedy constructive heuristic to generate a starting point for BLS. Benchmark instances used for our experiments and comparisons are based on information provided by Manchester Airport.     

Iterated local search for the team orienteering problem with time windows

A personalised electronic tourist guide assists tourists in planning and enjoying their trip. The planning problem that needs to be solved, in real-time, can be modelled as a team orienteering problem with time windows (TOPTW). In the TOPTW, a set of locations is given, each with a score, a service time and a time window. The goal is to maximise the sum of the collected scores by a fixed number of routes. The routes allow to visit locations at the right time and they are limited in length. The main contribution of this paper is a simple, fast and effective iterated local search meta-heuristic to solve the TOPTW. An insert step is combined with a shake step to escape from local optima. The specific shake step implementation and the fast evaluation of possible improvements, produces a heuristic that performs very well on a large and diverse set of instances. The average gap between the obtained results and the best-known solutions is only 1.8% and the average computation time is decreased with a factor of several hundreds. For 31 instances, new best solutions are computed.     

Adaptive granular local search heuristic for a dynamic vehicle routing problem

The advance of communication and information technologies based on satellite and wireless networks have allowed transportation companies to benefit from real-time information for dynamic vehicle routing with time windows. During daily operations, we consider the case in which customers can place requests such that their demand and location are stochastic variables. The time windows at customer locations can be violated although lateness costs are incurred. The objective is to define a set of vehicle routes which are dynamically updated to accommodate new customers in order to maximize the expected profit. This is the difference between the total revenue and the sum of lateness costs and costs associated with the total distance traveled. The solution approach makes use of a new constructive heuristic that scatters vehicles in the service area and an adaptive granular local search procedure. The strategies of letting a vehicle wait, positioning a vehicle in a region where customers are likely to appear, and diverting a vehicle away from its current destination are integrated within a granular local search heuristic. The performance of the proposed approach is assessed in test problems based on real-life Brazilian transportation companies.     

An iterated local search heuristic for the split delivery vehicle routing problem

This paper concerns the Split Delivery Vehicle Routing Problem (SDVRP). This problem is a relaxation of the Capacitated Vehicle Routing Problem (CVRP) since the customers׳ demands are allowed to be split. We deal with the cases where the fleet is unlimited (SDVRP-UF) and limited (SDVRP-LF). In order to solve them, we implemented a multi-start Iterated Local Search (ILS) based heuristic that includes a novel perturbation mechanism. Extensive computational experiments were carried out on benchmark instances available in the literature. The results obtained are highly competitive, more precisely, 55 best known solutions were equaled and new improved solutions were found for 243 out of 324 instances, with an average and maximum improvement of 1.15% and 2.81%, respectively.     

A recursive branch-and-bound algorithm for the rectangular guillotine strip packing problem

A heuristic recursive algorithm for the two-dimensional rectangular strip packing problem is presented. It is based on a recursive structure combined with branch-and-bound techniques. Several lengths are tried to determine the minimal plate length to hold all the items. Initially the plate is taken as a block. For the current block considered, the algorithm selects an item, puts it at the bottom-left corner of the block, and divides the unoccupied region into two smaller blocks with an orthogonal cut. The dividing cut is vertical if the block width is equal to the plate width; otherwise it is horizontal. Both lower and upper bounds are used to prune unpromising branches. The computational results on a class of benchmark problems indicate that the algorithm performs better than several recently published algorithms.     

Tree-decomposition based heuristics for the two-dimensional bin packing problem with conflicts

This paper deals with the two-dimensional bin packing problem with conflicts (BPC-2D). Given a finite set of rectangular items, an unlimited number of rectangular bins and a conflict graph, the goal is to find a conflict-free packing of the items minimizing the number of bins used. In this paper, we propose a new framework based on a tree-decomposition for solving this problem. It proceeds by decomposing a BPC-2D instance into subproblems to be solved independently. Applying this decomposition method is not straightforward, since merging partial solutions is hard. Several heuristic strategies are proposed to make an effective use of the decomposition. Computational experiments show the practical effectiveness of our approach.     

Extractive single-document summarization based on genetic operators and guided local search

Due to the exponential growth of textual information available on the Web, end users need to be able to access information in summary form – and without losing the most important information in the document when generating the summaries. Automatic generation of extractive summaries from a single document has traditionally been given the task of extracting the most relevant sentences from the original document. The methods employed generally allocate a score to each sentence in the document, taking into account certain features. The most relevant sentences are then selected, according to the score obtained for each sentence. These features include the position of the sentence in the document, its similarity to the title, the sentence length, and the frequency of the terms in the sentence. However, it has still not been possible to achieve a quality of summary that matches that performed by humans and therefore methods continue to be brought forward that aim to improve on the results. This paper addresses the generation of extractive summaries from a single document as a binary optimization problem where the quality (fitness) of the solutions is based on the weighting of individual statistical features of each sentence – such as position, sentence length and the relationship of the summary to the title, combined with group features of similarity between candidate sentences in the summary and the original document, and among the candidate sentences of the summary. This paper proposes a method of extractive single-document summarization based on genetic operators and guided local search, called MA-SingleDocSum. A memetic algorithm is used to integrate the own-population-based search of evolutionary algorithms with a guided local search strategy. The proposed method was compared with the state of the art methods UnifiedRank, DE, FEOM, NetSum, CRF, QCS, SVM, and Manifold Ranking, using ROUGE measures on the datasets DUC2001 and DUC2002. The results showed that MA-SingleDocSum outperforms the state of the art methods.     

A least wasted first heuristic algorithm for the rectangular packing problem

The rectangular packing problem is to pack a number of rectangles into a single large rectangular sheet so as to maximize the total area covered by the rectangles packed. The paper first presents a least wasted first strategy which evaluates the positions used by the rectangles. Then a random local search is introduced to improve the results and a least wasted first heuristic algorithm (LWF) is further developed to find a desirable solution. Twenty-one rectangular-packing instances are tested by the algorithm developed, the experimental results show that the presented algorithm can achieve an optimal solution within reasonable time and is fairly efficient for dealing the rectangular packing problem. LWF still performs well when it is extended to solve zero-waste and non-zero-waste strip packing instances.     

UnitWalk: A new SAT solver that uses local search guided by unit clause elimination

In this paper we present a new randomized algorithm for SAT, i.e., the satisfiability problem for Boolean formulas in conjunctive normal form. Despite its simplicity, this algorithm performs well on many common benchmarks ranging from graph coloring problems to microprocessor verification. Our algorithm is inspired by two randomized algorithms having the best current worst-case upper bounds ([27,28] and [30,31]). We combine the main ideas of these algorithms in one algorithm. The two approaches we use are local search (which is used in many SAT algorithms, e.g., in GSAT [34] and WalkSAT [33]) and unit clause elimination (which is rarely used in local search algorithms). In this paper we do not prove any theoretical bounds. However, we present encouraging results of computational experiments comparing several implementations of our algorithm with other SAT solvers. We also prove that our algorithm is probabilistically approximately complete (PAC).