Constrained circles packing test problems: all the optimal solutions known

Taking a satellite module layout design as engineering background, this paper gives constrained test problems for an unequal circle packing whose optimal solutions are all given. Given a circular container D with radius R, the test problem can be constructed in the following steps. First, M=217 circles are packed into D without overlaps by ‘packing with a tangent circle’ to get the values of radii and centroid coordinates of the circles, which are expressed by R. Then the 217 circles are arranged in descending sequence of radius and are divided into 23 groups according to the radius. Finally, seven test problems are constructed according to the circles of q=1, 2, …, 7 groups. The optimal solution to the test problems as well as its optimality and uniqueness proof are also presented. The experimental results show that the test problems can effectively evaluate performances of different evolutionary algorithms.     

A hybrid data mining heuristic to solve the point‐feature cartographic label placement problem

A clean map visualization requires the fewest possible overlaps and depends on how labels are attached to point features. In this paper, we address the cartographic label placement variant problem whose objective is to label a set of points maximizing the number of conflict‐free points. Thus, we propose a hybrid data mining heuristic to solve the point‐feature cartographic label placement problem based on a clustering search (CS) heuristic, a state‐of‐the‐art method for this problem. Although several works have investigated the combination of data mining and multistart metaheuristics, this is the first time data mining has been used to improve CS and simulated annealing based heuristics. Computational experiments showed that the proposed hybrid heuristic was able to reach better cost solutions than the original strategy, with the same time effort. The proposed heuristic also could find almost all known optimal solutions and improved most of the best results for the set of large instances reported so far in the literature.     

求解不等圆Packing问题的一个启发式算法

求解具有NP难度的圆形packing问题具有很高的理论与实用价值.现提出一个启发式方法,求解了货运中常遇到的矩形区域内的不等圆packing问题.此算法首先将待布局圆按半径大小降序排列,然后用占角动作来逐个放置.通过试探性地放入一个或多个待布局圆,给出了占角动作的度以及更全局的有限枚举策略来评价占角动作的优度.在放置每一个圆时,以贪心的方式选取当前具有最大优度的占角动作来放置.最后用测试算例验证了算法的高效性.     

A new heuristic branching scheme for the crew pairing problem with base constraints

Airline crew scheduling is typically performed in two steps : crew pairing followed by crew assignment. The crew pairing problem (CPP) finds a set of pairings (sequences of flights separated by connections or rests starting and ending at the same crew base) that covers a set of flights at minimum cost. The crew assignment problem consists of assigning the crew members to these pairings to create their individual schedules. The main downside of this sequential approach is that the pairings generated in the first step are not all suitable for the crew assignment step, yielding poor-quality solutions. This paper studies an extension of the CPP that includes additional constraints limiting the total worked time at each crew base. This problem, called the CPP with base constraints (CPPBC), is designed to improve the coupling of the two scheduling steps. To solve the CPPBC, we develop four branch-and-price heuristics: three of them rely on known heuristic branching schemes, the other introduces a new branching method, called retrospective branching. This branching scheme is designed to detect and revise poor branching decisions made earlier in the search tree, without backtracking. We tested and compared these four heuristics on real-world datasets. Our results show that the algorithm with retrospective branching yields, most of the times, better-quality solutions than the other tested methods.     

面向布局优化问题的多量子态量子进化算法及其应

针对演化算法在求解带平衡约束的圆形布局问题上所出现的早熟现象,提出一种有利于保持种群多样性的多量子态量子进化算法,并结合高效的定位定序启发式方法进行求解。为了高效优化布局顺序,在量子进化算法的基础上：引入多量子态编码和基于平均收敛概率的收敛标准以提高求解速度;引入基于禁忌策略和启发信息的观测方法,使其所得到的n进制解为互不相同的整数串,同时保证优先布局质量大、半径大的小圆;引入动态量子进化策略,有效地引导种群向最优个体进化。在定位规则中引入定位概率函数提高解的精度,数值实验结果表明,该算法能够有效求解带平衡约束的圆形布局问题。     

Reformulation descent applied to circle packing problems

Several years ago classical Euclidean geometry problems of densest packing of circles in the plane have been formulated as nonconvex optimization problems, allowing to find heuristic solutions by using any available NLP solver. In this paper we try to improve this procedure. The faster NLP solvers use first order information only, so stop in a stationary point. A simple switch from Cartesian coordinates to polar or vice versa, may destroy this stationarity and allow the solver to descend further. Such formulation switches may of course be iterated. For densest packing of equal circles into a unit circle, this simple feature turns out to yield results close to the best known, while beating second order methods by a time-factor well over 100.This technique is formalized as a general reformulation descent (RD) heuristic, which iterates among several formulations of the same problem until local searches obtain no further improvement. We also briefly discuss how RD might be used within other metaheuristic schemes.     

Optimal Packing Configuration Design with Finite-Circle Method

The Finite-circle Method (FCM) is further developed to solve 2D and 3D packing optimization problems with system compactness and moment of inertia constraints here. Instead of using the real geometrical shape as in existing solutions, we approximate the components and the design domain with circles of variant radii. Such approximation makes it possible to transform the original problem into a basic packing problem of FCM approximated components. Meanwhile, the overlapping between different components can be easily avoided by limiting the distance between corresponding circles in terms of their radii. With this formulation, the FCM provides a general and systematic approach and makes gradient-based optimization algorithms applicable. Furthermore, FCM has been extended to 3D packing problems by simply replacing circles with spheres in this paper. Several examples designing the compactness and moment of inertia of the component systems are presented to show the effect of FCM.     

A Best-first Branch-and-bound Algorithm for Orthogonal Rectangular Packing Problems

In this paper we discuss the problem of packing a set of small rectangles (pieces) in an enclosing final rectangle. We present first a best-first branch-and-bound exact algorithm and second a heuristic approach in order to solve exactly and approximately this problem. The performances of the proposed approaches are evaluated on several randomly generated problem instances. Computational results show that the proposed exact algorithm is able to solve small and medium problem instances within reasonable execution time. The derived heuristic performs very well in the sense that it produces high-quality solutions within small computational time.     

Optimal scheduling of emergency roadway repair and subsequent relief distribution

Emergency roadway repair and relief distribution planning following a natural disaster has traditionally been done manually and separately, based on the decision-maker's experience, disregarding the interrelationship between emergency roadway repair and relief distribution from the system perspective, which may yield inferior solutions. Hence, in this research we consider minimizing the length of time required for both emergency roadway repair and relief distribution, as well as the related operating constraints, to develop a model, for planning emergency repair and relief distribution routes and schedules within a limited time. We construct a time–space network for emergency repair and another for relief distribution. A number of operational constraints are set between these two networks according to real constraints. Our model is a multi-objective, mixed-integer, multiple-commodity network flow problem. We adopt the weighting method and develop a heuristic to efficiently solve this problem in practice. To evaluate our model and the solution algorithm, we perform a case study. The results show the model and the solution algorithm could be useful in practice.     

An adaptive large neighborhood search for the discrete and continuous Berth allocation problem

The Berth Allocation Problem (BAP) consists of assigning ships to berthing positions along a quay in a port. The choice of where and when the ships should move is the main decision to be made in this problem. Considering the berthing positions, there are restrictions related to the water depth and the size of the ships among others. There are also restrictions related to the berthing time of the ships which are modeled as time windows. In this work the ships are represented as rectangles to be placed into a space ×time area, avoiding overlaps and satisfying time window constraints. We consider discrete and continuous models for the BAP and we propose an Adaptive Large Neighborhood Search heuristic to solve the problem. Computational experiments indicate that the proposed algorithm is capable of generating high-quality solutions and outperforms competing algorithms for the same problem. In most cases the improvements are statistically significant.     

The multi-period incremental service facility location problem

In this paper we introduce the multi-period incremental service facility location problem where the goal is to set a number of new facilities over a finite time horizon so as to cover dynamically the demand of a given set of customers. We prove that the coefficient matrix of the allocation subproblem that results when fixing the set of facilities to open is totally unimodular. This allows to solve efficiently the Lagrangean problem that relaxes constraints requiring customers to be assigned to open facilities. We propose a solution approach that provides both lower and upper bounds by combining subgradient optimization to solve a Lagrangean dual with an ad hoc heuristic that uses information from the Lagrangean subproblem to generate feasible solutions. Numerical results obtained in the computational experiments show that the obtained solutions are very good. In general, we get very small percent gaps between upper and lower bounds with little computation effort.     

A Tabu Search Algorithm for application placement in computer clustering

This paper presents and analyzes a model for the problem of placing applications on computer clusters (APP). In this problem, organizations requesting a set of software applications have to be assigned to computer clusters such that the costs of opening clusters and installing the necessary applications are minimized. This problem is related to known OR problems such as the multiproduct facility location problem and the generalized bin packing problem. We show that APP is NP-hard, and then propose a simple Tabu Search heuristic to solve it. The performance of the Tabu Search heuristic is assessed via extensive computational experiments, which indicate the promise of the proposed Tabu Search.     

An evolutionary approach for configuring economical packet switched computer networks

The topological design of computer networks essentially consists in finding a network topology which minimizes the communication costs, taking into account some constraints such as performance and quality of service. This optimization problem is well known as difficult to solve, such that only heuristic methods are usually recommended and used. These methods are incremental in the sense that they take a starting topology as input solution and perturb it in order to produce a better solution. In this paper, we propose an evolutionary approach, based on the genetic algorithm paradigm, for solving this problem. Simulation results confirm the appropriateness and efficiency of this approach which yields solutions of very good quality for moderate size networks.     

Adaptive beam search lookahead algorithms for the circular packing problem

This paper addresses the circular packing problem (CPP), which consists in packing n circles C_i, each of known radius r_i, i∈N={1, …, n}, into the smallest containing circle C. The objective is to determine the radius r of C as well as the coordinates (x_i, y_i) of the center of C_i, i∈N. CPP is solved using two adaptive algorithms that adopt a binary search to determine r, and a beam search to check the feasibility of packing n circles into C when the radius is fixed at r. A node of level ?, ?=1, …, n, of the beam search tree corresponds to a partial packing of ? circles of N into C. The potential of each node of the tree is assessed using a lookahead strategy that, starting with the partial packing of the current node, assigns each unpacked circle to its maximum hole degree position. The beam search stops either when the lookahead strategy identifies a feasible packing or when it has fathomed all nodes. The computational tests on a set of benchmark instances show the effectiveness of the proposed adaptive algorithms.     

Layout optimization for the objects located within a rotating vessel — a three-dimensional packing problem with behavioral constraints

This paper studies the layout optimization problem of the simplified vessel of satellite which moves spirally. It is a three-dimensional packing problem with dynamical equilibrium constraints, and is known as NP-hard problem. A solution strategy for such a problem is proposed and corresponding heuristic algorithms are presented in this paper. Numerical examples are illustrated to verify the effectiveness of the proposed algorithms.Scope and purposeHow to cut garments out of cloth, how to cut or stamp pieces from steel plate, and how to put objects into a container, etc., without overlaps and with high utility of materials of space, all these belong to cutting and packing problems without constraints. These are old problems initiated scores of years ago, the planar versions of which have been studied extensively and most of them have been solved satisfactorily. But there is a lot of work to be done for the three-dimensional ones. Suppose we put objects into a rotating vessel or container, we must additionally consider dynamical equilibrium demands and some other specified features. This is a three-dimensional packing problem with behavioral contraints, which is often encountered in many high technological fields, such as satellites, spacecrafts, rotating vessels and underwater suspended engineerings, etc. This paper studies such a problem and proposes a solution strategy and algorithms.     

An integer programming column generation principle for heuristic search methods

There is an increasing interest in integrating column generation and heuristic approaches to efficiently solve large‐scale discrete optimisation problems. We contribute in this direction. Based on the insights from Lagrangian duality theory, we present an auxiliary problem that can be used for finding near‐optimal solutions to a discrete column‐oriented model. The structure of this auxiliary problem makes it suitable for being addressed with a heuristic search method involving column generation. To this end, we suggest a large neighbourhood search strategy where the repair step is to solve a column generation type subproblem. The suggested search strategy and mathematical models involved need to be tailored to the problem structure. To illustrate important design options and computational behaviour, four applications are studied: bin packing, generalised assignment, a resource allocation problem and the fixed‐charge transportation problem.     

A distance-limited continuous location-allocation problem for spatial planning of decentralized systems

We introduce a new continuous location-allocation problem where the facilities have both a fixed opening cost and a coverage distance limitation. The problem has wide applications especially in the spatial planning of water and/or energy access networks where the coverage distance might be associated with the physical loss constraints. We formulate a mixed integer quadratically constrained problem (MIQCP) under the Euclidean distance setting and present a three-stage heuristic algorithm for its solution: In the first stage, we solve a planar set covering problem (PSCP) under the distance limitation. In the second stage, we solve a discrete version of the proposed problem where the set of candidate locations for the facilities is formed by the union of the set of demand points and the set of locations in the PSCP solution. Finally, in the third stage, we apply a modified Weiszfeld’s algorithm with projections that we propose to incorporate the coverage distance component of our problem for fine-tuning the discrete space solutions in the continuous space. We perform numerical experiments on three example data sets from the literature to demonstrate the performance of the suggested heuristic method.     

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.     

Packing unequal circles using formulation space search

In this paper we present a heuristic algorithm for the problem of packing unequal circles in a fixed size container such as the unit circle, the unit square or a rectangle. We view the problem as being one of scaling the radii of the unequal circles so that they can all be packed into the container. Our algorithm is composed of an optimisation phase and an improvement phase. The optimisation phase is based on the formulation space search method whilst the improvement phase creates a perturbation of the current solution by swapping two circles. The instances considered in this work can be categorised into two: instances with large variations in radii and instances with small variations in radii. We consider six different containers: circle, square, rectangle, right-angled isosceles triangle, semicircle and circular quadrant. Computational results show improvements over previous work in the literature.     

A coarse-to-fine quasi-physical optimization method for solving the circle packing problem with equilibrium constraints

This paper addresses an important extension of the circle packing problem (CPP), the circle packing problem with equilibrium constraints (CPPEC). It considers the dense packing of n circular disks in a large circular container at the same time satisfying the equilibrium constraints. Under the industrial background of the layout design on satellite modules, this NP-hard global optimization problem is important in both theory and practice. We introduce two new quasi-physical models for solving CPPEC in this paper. One is to mimic the elastic movement driven by repelling forces from extruded disks, the other is to simulate a whole translation movement of the disks driven by a pulling force from an imaginative elastic rope connecting the centroid of the disks and the center of the container. Then, inspired by the coarse-to-fine control strategy in the manufacture industry, we propose a coarse-to-fine quasi-physical (CFQP) optimization method that adopts the two quasi-physical models for the quasi-physical descent procedure and combines a basin hopping with tabu method for the search procedure. In this way, not only could CFQP take into account the diversity of the search space to facilitate the global search, but it also does fine search to find the corresponding local minimum in a promising local area. Experiments were on two sets of 11 representative test instances. Computational results showed that CFQP achieved new and better results on four instances, at the same time it matched the current best records on the other six (accurate to 0.0001). Moreover, CFQP resulted in smaller equilibrium deviations than that of others published in the literature. In addition, we generated 34 new CPPEC instances basing on the CPP benchmarks, and provided computational results on the two sets of 34 new CPPEC instances, and the container radii obtained are close to the published results on CPP.