A tabu search procedure based on a random Roulette diversification for the weighted maximal planar graph problem

An efficient and effective tabu search implementation for the weighted maximal planar graph problem is proposed. The search incorporates a number of novel features including: the introduction of a new set of two-move operators; a move-cache-memory structure for efficiently searching the neighbourhood space; and a random roulette selection from a ranked list of best moves for diversification. The effects of these and other features on solution quality are investigated. Computational results are reported on a set of 100 benchmark instances of sizes varying from 20 to 100 vertices. The results demonstrate that the new probabilistic tabu search algorithm is very competitive with state of the art algorithms in the literature in terms of both solution quality and computational effort.Scope     

Metaheuristics for the waste collection vehicle routing problem with time windows,driver rest period and multiple disposal facilities

In this problem there is a set of waste disposal facilities, a set of customers at which waste is collected and an unlimited number of homogeneous vehicles based at a single depot. Empty vehicles leave the depot and collect waste from customers, emptying themselves at the waste disposal facilities as and when necessary. Vehicles return to the depot empty. We take into consideration time windows associated with customers, disposal facilities and the depot. We also have a driver rest period. The problem is solved heuristically. A neighbour set is defined for each customer as the set of customers that are close, but with compatible time windows. A procedure that attempts to fully utilise a vehicle is used to obtain an initial solution, with this initial solution being improved using an interchange procedure. We present two metaheuristic algorithms using tabu search and variable neighbourhood search that are based around the neighbour sets. We also present a metaheuristic based on variable neighbourhood tabu search, where the variable neighbourhood is searched via tabu search. Computational results are presented for publicly available waste collection problems involving up to 2092 customers and 19 waste disposal facilities, which indicate that our algorithms produce better quality solutions than previous work presented in the literature.     

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.     

Fine-tuning a Tabu Search Algorithm with Statistical Tests

Tabu Search is a metaheuristic that has proven to be very effective for solving various types of combinatorial optimization problems. To achieve the best results with a tabu search algorithm, significant benefits can sometimes be gained by determining preferred values for certain search parameters such as tabu tenures, move selection probabilities, the timing and structure of elite solution recovery for intensification, etc. In this paper, we present and implement some new ideas for fine-tuning a tabu search algorithm using statistical tests. Although the focus of this work is to improve a particular tabu search algorithm developed for solving a telecommunications network design problem, the implications are quite general. The same ideas and procedures can easily be adapted and applied to other tabu search algorithms as well.     

Variable neighborhood search for the linear ordering problem

Given a matrix of weights, the linear ordering problem (LOP) consists of finding a permutation of the columns and rows in order to maximize the sum of the weights in the upper triangle. This NP-complete problem can also be formulated in terms of graphs, as finding an acyclic tournament with a maximal sum of arc weights in a complete weighted graph. In this paper, we first review the previous methods for the LOP and then propose a heuristic algorithm based on the variable neighborhood search (VNS) methodology. The method combines different neighborhoods for an efficient exploration of the search space. We explore different search strategies and propose a hybrid method in which the VNS is coupled with a short-term tabu search for improved outcomes. Our extensive experimentation with both real and random instances shows that the proposed procedure competes with the best-known algorithms in terms of solution quality, and has reasonable computing-time requirements.Variable neighborhood search (VNS) is a metaheuristic method that has recently been shown to yield promising outcomes for solving combinatorial optimization problems. Based on a systematic change of neighborhood in a local search procedure, VNS uses both deterministic and random strategies in search for the global optimum.In this paper, we present a VNS implementation designed to find high quality solutions for the NP-hard LOP, which has a significant number of applications in practice. The LOP, for example, is equivalent to the so-called triangulation problem for input–output tables in economics. Our implementation incorporates innovative mechanisms to include memory structures within the VNS methodology. Moreover we study the hybridization with other methodologies such as tabu search.     

针对移动云计算任务迁移的快速高效调度算法

计算量较大的应用程序由于需要大量的能耗,因此在电池容量有限的移动设备上运行时十分受限。云计算迁移技术是保证此类应用程序在资源有限的设备上运行的主流方法。针对无线网络中应用程序任务图的调度和迁移问题,提出了一种快速高效的启发式算法。该算法将能够迁移到云端的任务都安排在云端完成这种策略作为初始解,通过逐次计算可迁移任务在移动端运行的能耗节省量,依次将节省量最大的任务迁移到移动端,并依据任务间的通讯时间及时更新各个任务的能耗节省量。为了寻找全局最优解,构造了适用于此问题的禁忌搜索算法,给出了相应的编码方法、禁忌表、邻域解以及算法终止准则。构造的禁忌搜索算法以提出的启发式解为初始解进行全局搜索,并实现对启发解的进一步优化。通过 实验 将所提方法与无迁移、随机迁移、饱和迁移3类算法进行对比,结果表明提出的启发式算法能够快速有效地给出能耗更小的解。例如,在宽度为10的任务图上,当深度为8时,无迁移、随机迁移与饱和迁移的能耗分别为5461、3357和2271能量单位,而给出的启发解对应的能耗仅为2111。在此基础上禁忌搜索算法又将其能耗降低到1942, 这进一步说明了提出的启发式算法能够产生高质量的近似解。     

Sequence-dependent group scheduling problem on unrelated-parallel machines

In this research we address a sequence-dependent group scheduling problem on a set of unrelated-parallel machines where the run time of each job differs on different machines. To benefit both producer and customers we attempt to minimize a linear combination of total weighted completion time and total weighted tardiness. Since the problem is shown to be NP-hard, meta-heuristic algorithms based on tabu search are developed to find the optimal/near optimal solution. For some small size yet complex problems, the results from these algorithms are compared to the optimal solutions found by CPLEX. The result obtained in all of these problems is that the tabu search algorithms could find solutions at least as good as CPLEX but in drastically shorter computational time, thus signifying the high degree of efficiency and efficacy attained by the former.     

A survey of local search methods for graph coloring

Tabucol   is a tabu search algorithm that tries to determine whether the vertices of a given graph can be colored with a fixed number k$k$ of colors such that no edge has both endpoints with the same color. This algorithm was proposed in 1987, one year after Fred Glover's article that launched tabu search. While more performing local search algorithms have now been proposed, Tabucol remains very popular and is often chosen as a subroutine in hybrid algorithms that combine a local search with a population based method. In order to explain this unfailing success, we make a thorough survey of local search techniques for graph coloring problems, and we point out the main differences between all these techniques.     

Inserting an Edge into a Planar Graph

Computing a crossing minimum drawing of a given planar graph G augmented by an additional edge e where all crossings involve e, has been a long standing open problem in graph drawing. Alternatively, the problem can be stated as finding a combinatorial embedding of a planar graph G where the given edge e can be inserted with the minimum number of crossings. Many problems concerned with the optimization over the set of all combinatorial embeddings of a planar graph turned out to be NP-hard. Surprisingly, we found a conceptually simple linear time algorithm based on SPQR-trees, that is able to find a solution with the minimum number of crossings.     

Problem difficulty for tabu search in job-shop scheduling

Tabu search algorithms are among the most effective approaches for solving the job-shop scheduling problem (JSP). Yet, we have little understanding of why these algorithms work so well, and under what conditions. We develop a model of problem difficulty for tabu search in the JSP, borrowing from similar models developed for SAT and other NP-complete problems. We show that the mean distance between random local optima and the nearest optimal solution is highly correlated with the cost of locating optimal solutions to typical, random JSPs. Additionally, this model accounts for the cost of locating sub-optimal solutions, and provides an explanation for differences in the relative difficulty of square versus rectangular JSPs. We also identify two important limitations of our model. First, model accuracy is inversely correlated with problem difficulty, and is exceptionally poor for rare, very high-cost problem instances. Second, the model is significantly less accurate for structured, non-random JSPs. Our results are also likely to be useful in future research on difficulty models of local search in SAT, as local search cost in both SAT and the JSP is largely dictated by the same search space features. Similarly, our research represents the first attempt to quantitatively model the cost of tabu search for any NP-complete problem, and may possibly be leveraged in an effort to understand tabu search in problems other than job-shop scheduling.     

Scheduling unrelated parallel machines with sequence-dependent setups

A methodology for minimizing the weighted tardiness of jobs in unrelated parallel machining scheduling with sequence-dependent setups is presented in this paper. To comply with industrial situations, the dynamic release of jobs and dynamic availability of machines are assumed. Recognizing the inherent difficulty in solving industrial-size problems efficiently, six different search algorithms based on tabu search are developed to identify the best schedule that gives the minimum weighted tardiness. To enhance both the efficiency and efficacy of the search algorithms, four different initial solution finding mechanisms, based on dispatching rules, are developed. While there is no evidence of identifying solutions of better quality by employing a specific initial solution finding mechanism, the use of a specific search algorithm led to identifying solutions of better quality or that required lower computation time, but not both. Based on the extensive statistical analysis performed, the search algorithm with short-term memory and fixed tabu list size is recommended for solving small size problems, while that with long-term memory and minimum frequency for solving medium and large size problems, combined with fixed tabu list size for the former and variable tabu list size for the latter.     

Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery

The vehicle routing problem with simultaneous pick-up and delivery is the problem of optimally integrating goods distribution and waste collection, when no precedence constraints are imposed on the order in which the operations must be performed. The purpose of this paper is to present heuristic algorithms to solve this problem approximately in a small amount of computing time. We present and compare constructive algorithms, local search algorithms and tabu search algorithms, reporting on our computational experience with all of them. In particular we address the issue of applying the tabu search paradigm to algorithms based on complex and variable neighborhoods. For this purpose we combine arc-exchange-based and node-exchange-based neighborhoods, employing different and interacting tabu lists. All the algorithms presented in this paper are applicable to problems in which each customer may have either a pick-up demand or a delivery demand as well as to problems in which each customer may require both kinds of operation.     

Algorithms for a shared resource scheduling problem in which some level of conflict is tolerable

In certain shared resource applications, such as file access scheduling for a network of computer users, some level of conflict between the elements of the schedule is tolerable. A scheduling problem of this nature may be modelled as a generalisation of the classical vertex colouring problem for graphs, called the maximum degree graph colouring problem. In this paper we present four algorithmic procedures for solving the maximum degree graph colouring problem. The first two of these algorithms (a simple heuristic and a tabu search metaheuristic) produce approximate solutions, while the other two algorithms are exact. The runtime efficiencies of and the solution qualities produced by these procedures are tested with respect to a number of graph benchmarks from the literature.     

Capacitated Clustering Problems by Hybrid Simulated Annealing and Tabu Search

The capacitated clustering problem (CCP) is the problem in which a given set of weighted objects is to be partitioned into clusters so that the total weight of objects in each cluster is less than a given value (cluster ‘capacity’). The objective is to minimize the total scatter of objects from the ‘centre’ of the cluster to which they have been allocated. A simple constructive heuristic, a R-interchange generation mechanism, a hybrid simulated annealing (SA) and tabu search (TS) algorithm which has computationally desirable features using a new non-monotonic cooling schedule, are developed. A classification of the existing SA cooling schedules is presented. The effects on the final solution quality of the initial solutions, the cooling schedule parameters and the neighbourhood search strategies are investigated. Computational results on randomly generated problems with size ranging from 50 to 100 customers indicate that the hybrid SA/TS algorithm out-performs previous simulated annealing algorithms, a simple tabu search and local descent algorithms.     

Constructive heuristic algorithms for the open shop problem

In this paper we consider constructive heuristic algorithms for the open shop problem with minimization of the schedule length. By means of investigations of the structure of a feasible solution two types of heuristic algorithms are developed: construction of a rank-minimal schedule by solving successively weighted maximum cardinality matching problems and construction of an approximate schedule by applying insertion techniques combined with beam search. All presented algorithms are tested on benchmark problems from the literature. Our computational results demonstrate the excellent solution quality of our insertion algorithm, especially for greater job and machine numbers. For 29 of 30 benchmark problems with at least 10 jobs and 10 machines we improve the best known values obtained by tabu search.     

无向哈密顿图的一个充分必要条件及计算公式

哈密顿图的判定问题是一个NP完全问题,是图论理论中尚未解决的主要问题之一。1968年,Grinberg证明了一个必要条件,提高了判定非哈密顿可平面图的效率,由此产生了很多3-正则3-连通非哈密顿可平面图的研究成果。根据无向哈密顿图的特征,提出了基本圈的分解、合并、单条公共边连通,原子圈等概念。任何一个简单连通无向图G是哈密顿图,当且仅当,哈密顿圈要么其本身就是一个包含所有顶点的原子圈;要么总是可以分解成若干个原子圈,这些原子圈按照某种次序以单条公共边连通。根据这个充分必要条件,推导出了一个必要条件计算公式。它不仅能处理平面图,也能处理非平面图;甚至能处理某些Grinberg条件不能处理的平面图。此外,对一些实际案例的测试结果验证了充分必要条件和计算公式的有效性。     

Semidynamic Algorithms for Maintaining Single-Source Shortest Path Trees

We consider the problem of updating a single-source shortest path in either a directed or an undirected graph, with positive real edge weights. Our algorithms for the incremental problem (handling edge insertions and cost decrements) work for any graph; they have optimal space requirements and query time, but their performances depend on the class of the considered graph. The cost of updates is computed in terms of amortized complexity and depends on the size of the output modifications. In the case of graphs with bounded genus (including planar graphs), graphs with bounded arboricity (including bounded degree graphs), and graphs with bounded treewidth, the incremental algorithms require O(log n) amortized time per vertex update, where a vertex is considered updated if it reduces its distance from the source. For general graphs with n vertices and m edges our incremental solution requires O( log n) amortized time per vertex update. We also consider the decremental problem for planar graphs, providing algorithms and data structures with analogous performances. The algorithms, based on Dijkstra's technique [6], require simple data structures that are really suitable for a practical and straightforward implementation. Received January 1995; revised February 1997.     

NP-completeness of maximum-cut and cycle-covering problems for a planar graph

We consider problems of finding the maximum cut and a cycle covering for a planar graph with edge weights of arbitrary sign. Methods that find the maximum cut in graphs with only positive edge weights are shown to be inapplicable in this case. NP-completeness of the problem is proved.Translated from Kibernetika, No. 1, pp. 13–16, January–February, 1991.     

Using tabu search with ranking candidate list to solve production planning problems with setups

This study considers production planning problems involving multiple products, multiple resources, multiple periods, setup times, and setup costs. It can be formulated as a mixed integer program (MIP). Solving a realistic MIP production planning problem is NP-hard; therefore, we use tabu search methods to solve such a difficult problem. Furthermore, we improve tabu search by a new candidate list strategy, which sorts the neighbor solutions using post-optimization information provided by the final tableau of the linear programming simplex algorithm. A neighbor solution with higher priority in the ranking sequence has a higher probability of being the best neighbor solution of a current solution. According to our experiments, the proposed candidate list strategy tabu search produces a good solution faster than the traditional simple tabu search. This study also suggests that if the evaluation of the entire neighborhood space in a tabu search algorithm takes too much computation and if an efficient and effective heuristic to rank the neighbor solutions can be developed, the speed of tabu search algorithm could be significantly increased by using the proposed candidate list strategy.     

Searching networks with unrestricted edge costs

Best-first and depth-first heuristic search algorithms often assume underlying search graphs with only nonnegative edge costs and attempt to optimize simple objective functions. Applicability of these algorithms to graphs with both positive and negative edge costs is not completely studied. In the paper, two new problems are identified: one in computational geometry and the other in the layout design of very large scale integrated (VLSI) circuits. The former problem relates to a weight-balanced bipartitioning of a given set of points in a plane. The goal of the second problem is to find an area-balanced staircase path in a VLSI floorplan. Formulations of these problems lead to an interesting directed acyclic search graph with positive, zero and negative edge costs and an objective function of general nature. These problems are NP-hard. To solve such general problems optimally, search schemes are proposed. Experimental results reveal the efficacy and versatility of the proposed schemes, the depth-first scheme being the better choice. It is shown that the classical number-partitioning problem can also be formulated in this framework