An evolution-based tabu search approach to codebook design

This paper presents an evolution-based tabu search approach (ETSA) to design codebooks with smaller distortion values in vector quantization. In the ETSA, there is no need for users to determine the size of a tabu memory and to specifically define a set of tabu restrictions and a set of aspiration criteria. During iterations, only the best solution visited is memorized as a tabu point in the search space and the distance from each trial solution to the tabu point is an important factor in the fitness evaluation. In population competition, the new fitness function plays the roles of the tabu restrictions and the aspiration criteria. Based on the new fitness function and a parallel evolutionary mechanism, the ETSA can prevent premature convergence and eventually find a good solution. Seven grayscale images are used to test the performance of the ETSA. Experimental results show that the ETSA performs better than several existing algorithms in terms of the distortion and robustness measures.     

A branch and price algorithm for the pharmacy duty scheduling problem

Pharmacy Duty Scheduling (PDS) is the activity of assigning pharmacies to days during a planning horizon with the purpose of serving society outside regular working hours. In Turkey, pharmacies are retailers who operate during the working hours in weekdays. However, demand for medicine at nights, at the weekends and on holidays must be satisfied by allocating times to pharmacies to open at these times. The problem is a multi-period p-median problem with the additional problem specific constraints, and it is NP-Hard. In this study, we develop a branch-and-price algorithm to solve the PDS to optimality. We decompose the problem into single period problems and apply column generation on the decomposed problem. We propose several enhancements on the algorithm and conduct computational tests on randomly generated instances to compare the performance of the developed algorithm with the state-of-art general purpose solver. The branch-and-price algorithm outperforms the state-of-art general purpose solver.     

On the one-dimensional stock cutting problem in the paper tube industry

The one-dimensional cutting stock problem (1D-CSP) is one of the representative combinatorial optimization problems which arises in many industrial applications. Although the primary objective of 1D-CSP is to minimize the total length of used stock rolls, the efficiency of cutting processes has become more important in recent years. The crucial bottleneck of the cutting process often occurs at handling operations in semiautomated manufacturers such as those in the paper tube industry. To reduce interruptions and errors at handling operations in the paper tube industry, we consider a variant of 1D-CSP that minimizes the total length of used stock rolls while constraining (C1) the number of setups of each stock roll type, (C2) the combination of piece lengths occurring in open stacks simultaneously, and (C3) the number of open stacks. For this problem, we propose a generalization of the cutting pattern called the “cutting group,” which is a sequence of cutting patterns that satisfies the given upper bounds of setups of each stock roll type and open stacks. To generate good cutting groups, we decompose the 1D-CSP into a number of auxiliary bin packing problems. We develop a tabu search algorithm based on a shift neighborhood that solves the auxiliary bin packing problems by the first-fit decreasing heuristic algorithm. Experimental results show that our algorithm improves the quality of solutions compared to the existing algorithm used in a paper tube factory.     

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 tabu search heuristic for the concentrator location problem

The concentrator location problem (CLP) is a classical problem in the network design literature. Given a set of candidate locations and the concentrator capacities, the problem is to answer the following related questions. How many concentrators should be used? Where should they be located? Which users are to be assigned to each concentrator? A Lagrangian relaxation is used to obtain lower bounds for this problem. The Lagrangian relaxation is complemented by a tabu search (TS) metaheuristic. Computational results are given for a set of randomly generated problems and for test problems available in the literature. The tabu search heuristic (TSH) is shown to be competitive with other solution procedures available for the problem.     

A tabu search with an oscillation strategy for the discriminant analysis problem

This article proposes a tabu search approach to solve a mathematical programming formulation of the linear classification problem, which consists of determining an hyperplane that separates two groups of points as well as possible in ?^m. The tabu search approach proposed is based on a non-standard formulation using linear system infeasibility. The search space is the set of bases defined on the matrix that describes the linear system. The moves are performed by pivoting on a specified row and column. On real machine learning databases, our approach compares favorably with implementations based on parametric programming and irreducible infeasible constraint sets. Additional computational results for randomly generated instances confirm that our method provides a suitable alternative to the mixed integer programming formulation that is solved by a commercial code when the number of attributes m increases.     

Defining tabu list size and aspiration criterion within tabu search methods

An investigation to explicitly define two key elements in tabu search methods is attempted. In this study a functional representation of the tabu list size is presented and a softer aspiration criterion is put forward. Experiments are conducted on a set of p-median problems.Scope and purposeTabu search is a metaheuristic that proved successful in finding good solutions to difficult combinatorial problems that were hard to find otherwise. In this study, we attempt to help the user in the choice of some of the parameters used in this type of heuristics. We based our analysis on the tabu list size and on an implementation on how to define the aspiration criterion. This added information can be valuable to those users who apply these methods in a near systematic manner without relying heavily on experimentations. As an example we used a simple location problem to test the usefulness of these ideas.     

A branch-and-price algorithm for the multi-activity multi-task shift scheduling problem

The multi-activity multi-task shift scheduling problem requires the assignment of interruptible activities and uninterruptible tasks to a set of employees in order to satisfy a demand function. In this paper, we consider the personalized variant of the problem where the employees have different qualifications, preferences, and availabilities. We present a branch-and-price algorithm to solve this problem. The pricing subproblems in column generation are formulated with context-free grammars that are able to model complex rules in the construction of feasible shifts for an employee. We present results for a large set of instances inspired by real cases and show that this approach is sufficiently flexible to handle different classes of problems.     

A tabu search algorithm for order acceptance and scheduling

We consider a make-to-order production system, where limited production capacity and order delivery requirements necessitate selective acceptance of the orders. Since tardiness penalties cause loss of revenue, scheduling and order acceptance decisions must be taken jointly to maximize total revenue. We present a tabu search algorithm that solves the order acceptance and scheduling problem on a single machine with release dates and sequence dependent setup times. We analyze the performance of the tabu search algorithm on an extensive set of test instances with up to 100 orders and compare it with two heuristics from the literature. In the comparison, we report optimality gaps which are calculated with respect to bounds generated from a mixed integer programming formulation. The results show that the tabu search algorithm gives near optimal solutions that are significantly better compared to the solutions given by the two heuristics. Furthermore, the run time of the tabu search algorithm is very small, even for 100 orders. The success of the proposed heuristic largely depends on its capability to incorporate in its search acceptance and scheduling decisions simultaneously.     

METAHEURISTICS FOR HANDLING TIME INTERVAL COVERAGE CONSTRAINTS IN NURSE SCHEDULING

The problem of finding a high quality timetable for personnel in a hospital ward has been addressed by many researchers, personnel managers, and schedulers over a number of years. Nevertheless, automated nurse rostering practice is not common yet in hospitals. Many head nurses are currently spending several days per month on constructing their rosters by hand. In recent years, the emergence of larger and more constrained problems has presented a real challenge because finding good quality solutions can lead to a higher level of personnel satisfaction and to flexible organizational procedures. Compared to many industrial situations (where personnel schedules normally consist of stable periodic morning-day-night cycles) health care institutions often require more flexibility in terms of hours and shift types. The motivation for the research presented in this paper has been provided by real-world hospital administrators/schedulers and the approach that we describe has been implemented in over 40 hospitals in Belgium. This paper consists of two main contributions: modeling the real-world situation more accurately than has previously been done in the literature; and presenting and evaluating an efficient and effective tabu search procedure to solve these problems (as represented in the real-world model).

The approach described in this paper concentrates on an advanced representation of the daily personnel requirements of healthcare institutions. We introduce time interval personnel requirements. Instead of formulating the requirements as a number of personnel needed per shift type for each day of the planning period, time interval requirements allow for the representation of the personnel requirements per day in terms of the start and end times of personnel attendance. This formulation enables the provision of a greater choice of shift work and part-time work and reduces the amount of unproductive time because it enables the shifts to be split and combined. We present an algorithmic approach to handle this new formulation. We also set up a series of experiments which indicate that, not only does this approach take into account the requests and requirements of hospital schedulers, but it also generates higher quality schedules when compared with earlier approaches. The obtained results are better in the sense that various specific real-world soft constraints can be satisfied by scheduling appropriate shift type combinations, whereas in the shift type approach, fixed shift types restricted the solution space.     

The task assignment problem for unrestricted movement between workstation groups

The purpose of this paper is to investigate the problem of assigning tasks to workers during their daily shifts. For a homogeneous workforce, a given set of workstation groups, and a corresponding demand for labor, the objective is to develop a disaggregated schedule for each worker that minimizes the weighted sum of transitions between workstation groups. In the formulation of the problem, each day is divided into 48 1/2-hour time periods and a multi-commodity network is constructed in which each worker corresponds to a unique commodity and each node represents a workstation group-time period combination. Lunch breaks and idle time are also included in the model. Initial attempts to solve large instances with a commercial code indicated a need for a more practical approach. This led to the development of a reduced network representation in which idle periods are treated implicitly, and a sequential methodology in which the week is decomposed into 7 daily problems and each solved in turn. To gain more computational efficiency, a tabu search procedure was also developed. All procedures were tested using data obtained from a U.S. Postal Service mail processing and distribution center. Depending on the labor category, anywhere from 3 to 28 workstation groups and up to 311 full-time and part-time workers had to be scheduled together. The results were mixed. While small problems could be solved to near-optimality with the integer programming approaches, tabu search was the best alternative for the very large instances. However, the excessive number of swaps needed to gain marginal improvements, undermined its effectiveness.Combining the two provided a good balance in most cases. This work was supported in part by the National Science Foundation under grant # DMI-0218701.     

Local search techniques for a routing-packing problem

We propose a complex real-world problem in logistics that integrates routing and packing aspects. It can be seen as an extension of the Three-Dimensional Loading Capacitated Vehicle Routing Problem (3L-CVRP) introduced by Gendreau, Iori, Laporte, and Martello (2006). The 3L-CVRP consists in finding a set of routes that satisfies the demand of all customers, minimizes the total routing cost, and guarantees a packing of items that is feasible according to loading constraints. Our problem formulation includes additional constraints in relation to the stability of the cargo, to the fragility of items, and to the loading and unloading policy. In addition, it considers the possibility of split deliveries, so that each customer can be visited more than once. We propose a local search approach that considers the overall problem in a single stage. It is based on a composite strategy that interleaves simulated annealing with large-neighborhood search. We test our solver on 13 real-world instances provided by our industrial partner, which are very diverse in size and features. In addition, we compare our solver on benchmarks from the literature of the 3L-CVRP showing that our solver performs well compared to other approaches proposed in the literature.     

Lower and upper bounds for a two-level hierarchical location problem in computer networks

In this paper a two-level hierarchical model for the location of concentrators and routers in computers networks is presented. Given a set of candidate locations and the capacities of concentrators and routers the problem is to determine how many concentrators and routers should be used, where they should be located and which users to assign to each concentrator and which concentrators to allocate to each router. A Lagrangean relaxation is used to provide lower bounds for this problem, which are tentatively strengthened by incomplete optimization through the use of CPLEX. A tabu search meta-heuristic is then developed. Computational experiments are performed using a set of randomly generated problems.     

OVRP_GELS: solving open vehicle routing problem using the gravitational emulation local search algorithm

In open vehicle routing problem (OVRP), after delivering service to the last customer, the vehicle does not necessarily return to the initial depot. This type of problem originally defined about thirty years ago and still is an open issue. In real life, the OVRP is similar to the delivering newspapers and consignments. The problem of service delivering to a set of customers is a particular open VRP with an identical fleet for transporting vehicles that do not necessarily return to the initial depot. Contractors which are not the employee of the delivery company use their own vehicles and do not return to the depot. Solving the OVRP means to optimize the number of vehicles, the traveling distance and the traveling time of a vehicle. In time, several algorithms such as tabu search, deterministic annealing and neighborhood search were used for solving the OVRP. In this paper, a new combinatorial algorithm named OVRP_GELS based on gravitational emulation local search algorithm for solving the OVRP is proposed. We also used record-to-record algorithm to improve the results of the GELS. Several numerical experiments show a good performance of the proposed method for solving the OVRP when compared with existing techniques.

     

求解不等圆Packing问题的带全局变换禁忌搜索算法

圆形Packing问题考察如何将N个半径任意给定的圆形物体互不嵌入地置入一个半径尽可能小的圆形容器内.圆形Packing问题是个经典的NP难度问题,具有重要的理论价值和广泛的应用背景.本文将拟物算法与禁忌搜索相结合,辅以跳离局部陷阱的全局变换策略,得到求解二维不等圆Packing问题的带全局变换禁忌搜索算法GP-TS.拟物算法用于连续优化,可从任一初始格局收敛至局部最优格局;禁忌搜索在禁忌规则和特赦准则的约束下不断地将当前格局替换为其邻域中的最优格局;若禁忌搜索所得格局不满足约束条件,则执行全局变换策略,在不完全破坏当前格局结构的前提下跳离局部陷阱,然后进行新一轮的禁忌搜索,直至满足终止条件为止.数字实验结果表明,GP-TS能在可接受的计算时间内改进多个国际公开算例的已知最优解.     

A mixed integer linear program and tabu search approach for the complementary edge covering problem

In this paper we study a complementary edge covering problem (CECP) as a variant of the total edge covering problem (TECP) which has application in the area of facility location. Unlike TECP, the partial cover of an edge through vertices is allowed in CECP such that in a feasible solution the entire edge will be covered. We propose a new mixed integer linear formulation for the problem. A number of size reduction rules are proposed which speed up getting optimal solution(s). Since the CECP is NP-Hard, a solution method based on tabu search is designed to search for optimal or near-optimal solutions. Computational experiments are carried out to evaluate effectiveness of the proposed mathematical formulation and the modified tabu search algorithm. Results justify that the proposed mathematical model can solves problems with up to 40 vertices and 456 edges optimally. Our computational efforts signify that the proposed tabu search is very effective and can find high quality solutions for larger problems in reasonable amount of time.     

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

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

Emergency facility location under random network damage: Insights from the Istanbul case

Damage to infrastructure, especially to highways and roads, adversely affects accessibility to disaster areas. Predicting accessibility to demand points from the supply points by a systematic model would lead to more effective emergency facility location decisions. To this effect, we model the spatial impact of the disaster on network links by random failures with dependency such that failure of a link induces failure of nearby links that are structurally more vulnerable. For each demand point, a set of alternative paths is generated from each potential supply point so that the shortest surviving path will be used for relief transportation after the disaster. The objective is to maximize the expected demand coverage within a specified distance over all possible network realizations. To overcome the computational difficulty caused by extremely large number of possible outcomes, we propose a tabu search heuristic that evaluates candidate solutions over a sample of network scenarios. The scenario generation algorithm that represents the proposed distance and vulnerability based failure model is the main contribution of our study. The tabu search algorithm is applied to Istanbul earthquake preparedness case with a detailed analysis comparing solutions found in no link failure, independent link failure, and dependent link failure cases. The results show that incorporating dependent link failures to the model improves the covered demand percentages significantly.     

A new heuristic algorithm for the circular packing problem with equilibrium constraints

The circular packing problem with equilibrium constraints is an optimization problem about simplified satellite module layout design.A heuristic algorithm based on tabu search is put forward for solving this problem.The algorithm begins from a random initial configuration and applies the gradient method with an adaptive step length to search for the minimum energy configuration.To jump out of the local minima and avoid the search doing repeated work,the algorithm adopts the strategy of tabu search.In the pr...     

An effective hybrid algorithm for the problem of packing circles into a larger containing circle

Simulated annealing is a powerful stochastic search method, but it still has the disadvantage of blind search. Tabu search (TS) which can prevent cycling and enhance diversification, is an adaptive strategy based on tabu list. By reasonably combining simulated annealing with TS, an effective hybrid algorithm for the problem of packing circles into a larger containing circle is presented. Based on a special neighborhood and tabu strategy, some benchmark problem instances can be well solved by the presented hybrid algorithm, and the computational results can compete with the best literature results.