Two genetic algorithms for solving the uncapacitated single allocation p-hub median problem

This paper deals with the Uncapacitated Single Allocation p-Hub Median Problem (USApHMP). Two genetic algorithm (GA) approaches are proposed for solving this NP-hard problem. New encoding schemes are implemented with appropriate objective functions. Both approaches keep the feasibility of individuals by using specific representation and modified genetic operators. The numerical experiments were carried out on the standard ORLIB hub data set. Both methods proved to be robust and efficient in solving USApHMP with up to 200 nodes and 20 hubs. The second GA approach achieves all previously known optimal solutions and achieves the best-known solutions on large-scale instances.     

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.     

The prize-collecting generalized minimum spanning tree problem

We introduce the prize-collecting generalized minimum spanning tree problem. In this problem a network of node clusters needs to be connected via a tree architecture using exactly one node per cluster. Nodes in each cluster compete by offering a payment for selection. This problem is NP-hard, and we describe several heuristic strategies, including local search and a genetic algorithm. Further, we present a simple and computationally efficient branch-and-cut algorithm. Our computational study indicates that our branch-and-cut algorithm finds optimal solutions for networks with up to 200 nodes within two hours of CPU time, while the heuristic search procedures rapidly find near-optimal solutions for all of the test instances.     

Heuristic method for a mixed capacitated arc routing problem: A refuse collection application

The capacitated arc routing problem (CARP) is known to be NP-hard. The aim of this paper is to present a new heuristic method to generate feasible solutions to an extended CARP on mixed graphs, inspired by the household refuse collection problem in Lisbon. Computational experience was done to compare the method with some well-known existing heuristics, generalised for a different extended CARP by Lacomme et al. [Fast algorithm for general arc routing problems, Presented at IFORS 2002 Conference, Edinburgh, UK], namely, the Path-Scanning, the Augment-Merge and the Ulusoy’s algorithms. The results reveal a good performance of the proposed heuristic method. Generally providing a good use of the vehicles capacity, the resulting sets of feasible trips may also be considered good. The test instances involve more than 300 randomly generated test problems with dimensions of up to 400 nodes and 1220 links.     

A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces

Given a set of rectangular pieces and a container of fixed width and variable length, the two-dimensional strip packing problem (2D-SPP) consists of orthogonally placing all the pieces within the container, without overlapping, such that the overall length of the layout is minimised. Until now mainly heuristics, for example genetic algorithms (GA), were proposed for the 2D-SPP which use encoded solutions that are manipulated by standard operators. In this paper a GA for the 2D-SPP is suggested that works without any encoding of solutions. Rather fully defined layouts are manipulated as such by means of specific genetic operators. Two additional constraints, namely the orientation constraint and the guillotine constraint, can be taken into account. The GA is subjected to a comprehensive test using benchmark instances with up to 5000 pieces. Compared to eleven competing methods from the literature the GA performs best.     

Single row facility layout problem using a permutation-based genetic algorithm

In this paper, a permutation-based genetic algorithm (GA) is applied to the NP-hard problem of arranging a number of facilities on a line with minimum cost, known as the single row facility layout problem (SRFLP). The GA individuals are obtained by using some rule-based as well as random permutations of the facilities, which are then improved towards the optimum by means of specially designed crossover and mutation operators. Such schemes led the GA to handle the SRFLP as an unconstrained optimization problem. In the computational experiments carried out with large-size instances of sizes from 60 to 80, available in the literature, the proposed GA improved several previously known best solutions.     

Steiner tree packing revisited

The Steiner tree packing problem (STPP) in graphs is a long studied problem in combinatorial optimization. In contrast to many other problems, where there have been tremendous advances in practical problem solving, STPP remains very difficult. Most heuristics schemes are ineffective and even finding feasible solutions is already NP-hard. What makes this problem special is that in order to reach the overall optimal solution non-optimal solutions to the underlying NP-hard Steiner tree problems must be used. Any non-global approach to the STPP is likely to fail. Integer programming is currently the best approach for computing optimal solutions. In this paper we review some ??classical?? STPP instances which model the underlying real world application only in a reduced form. Through improved modelling, including some new cutting planes, and by employing recent advances in solver technology we are for the first time able to solve those instances in the original 3D grid graphs to optimimality.     

物流服务供应链订单分配优化及其遗传算法

针对物流服务供应链订单分配问题中,物流服务集成商通常会按照所分配的订单价值向分包商收取一定比例交易费用的特点,设定交易费用为交易额的线性函数,构建了新的物流服务供应链订单分配优化混合整数规划模型,其优化目标为最小化交易费用、采购费用、短缺服务与延迟供给的物流能力数量。鉴于问题的NP-hard特性,设计了相应的遗传算法,并结合基于优先权的启发式规则避免了大量非法初始解的出现。实验算例表明所建立的模型能够反映物流服务供应链订单分配过程中的线性交易费用因素,其所设计的算法能够在可接受的时间内获得质量较高的满意解,并且对于大规模订单分配优化问题,遗传算法的求解时间与求解结果要优于LINGO软件。     

Telecommunication Link Restoration Planning with Multiple Facility Types

To ensure uninterrupted service, telecommunication networks contain excess (spare) capacity for rerouting (restoring) traffic in the event of a link failure. We study the NP-hard capacity planning problem of economically installing spare capacity on a network to permit link restoration of steady-state traffic. We present a planning model that incorporates multiple facility types, and develop optimization-based heuristic solution methods based on solving a linear programming relaxation and minimum cost network flow subproblems. We establish bounds on the performance of the algorithms, and discuss problem instances that nearly achieve these worst-case bounds. In tests on three real-world problems and numerous randomly-generated problems containing up to 50 nodes and 150 edges, the heuristics provide good solutions (often within 0.5% of optimality) to problems with single facility type, in equivalent or less time than methods from the literature. For multi-facility problems, the gap between our heuristic solution values and the linear programming bounds are larger. However, for small graphs, we show that the optimal linear programming value does not provide a tight bound on the optimal integer value, and our heuristic solutions are closer to optimality than implied by the gaps.     

A random-key genetic algorithm for the generalized traveling salesman problem

The generalized traveling salesman problem is a variation of the well-known traveling salesman problem in which the set of nodes is divided into clusters; the objective is to find a minimum-cost tour passing through one node from each cluster. We present an effective heuristic for this problem. The method combines a genetic algorithm (GA) with a local tour improvement heuristic. Solutions are encoded using random keys, which circumvent the feasibility problems encountered when using traditional GA encodings. On a set of 41 standard test problems with symmetric distances and up to 442 nodes, the heuristic found solutions that were optimal in most cases and were within 1% of optimality in all but the largest problems, with computation times generally within 10 seconds. The heuristic is competitive with other heuristics published to date in both solution quality and computation time.     

Extensive Testing of a Hybrid Genetic Algorithm for Solving Quadratic Assignment Problems

A robust search algorithm should ideally exhibit reasonable performance on a diverse and varied set of problems. In an earlier paper Lim et al. (Computational Optimization and Applications, vol. 15, no. 3, 2000), we outlined a class of hybrid genetic algorithms based on the k-gene exchange local search for solving the quadratic assignment problem (QAP). We follow up on our development of the algorithms by reporting in this paper the results of comprehensive testing of the hybrid genetic algorithms (GA) in solving QAP. Over a hundred instances of QAP benchmarks were tested using a standard set of parameters setting and the results are presented along with the results obtained using simple GA for comparisons. Results of our testing on all the benchmarks show that the hybrid GA can obtain good quality solutions of within 2.5% above the best-known solution for 98% of the instances of QAP benchmarks tested. The computation time is also reasonable. For all the instances tested, all except for one require computation time not exceeding one hour. The results will serve as a useful baseline for performance comparison against other algorithms using the QAP benchmarks as a basis for testing.     

Integer programming formulations for the minimum weighted maximal matching problem

Given an undirected graph, the problem of finding a maximal matching that has minimum total weight is NP-hard. This problem has been studied extensively from a graph theoretical point of view. Most of the existing literature considers the problem in some restricted classes of graphs and give polynomial time exact or approximation algorithms. On the contrary, we consider the problem on general graphs and approach it from an optimization point of view. In this paper, we develop integer programming formulations for the minimum weighted maximal matching problem and analyze their efficacy on randomly generated graphs. We also compare solutions found by a greedy approximation algorithm, which is based on the literature, against optimal solutions. Our results show that our integer programming formulations are able to solve medium size instances to optimality and suggest further research for improvement.     

Competitive Memetic Algorithms for Arc Routing Problems

The Capacitated Arc Routing Problem or CARP arises in applications like waste collection or winter gritting. Metaheuristics are tools of choice for solving large instances of this NP-hard problem. The paper presents basic components that can be combined into powerful memetic algorithms (MAs) for solving an extended version of the CARP (ECARP). The best resulting MA outperforms all known heuristics on three sets of benchmark files containing in total 81 instances with up to 140 nodes and 190 edges. In particular, one open instance is broken by reaching a tight lower bound designed by Belenguer and Benavent, 26 best-known solutions are improved, and all other best-known solutions are retrieved.     

Using genetic algorithms for the coordinated scheduling problem of a batching machine and two-stage transportation

This paper considers a coordinated scheduling problem. For the first-stage transportation there is a crane available to transport the product from the warehouse to a batching machine. For the second-stage transportation there is a vehicle available to deliver the completed jobs from the machine shop floor to the customer. The coordinated scheduling problem of production and transportation deals with sequencing the transportation of the jobs and combining them into batches to be processed. The problem of minimizing the sum of the makespan and the total setup cost was proven by Tang and Gong [1] to be strongly NP-hard. This paper proposes two genetic algorithm (GA) approaches for this scheduling problem, with different result representations. The experimental results demonstrate that a regular GA and a modified GA (MGA) can find near-optimal solutions within an acceptable amount of computational time. Among the two proposed metaheuristic approaches, the MGA is superior to the GA both in terms of computing time and the quality of the solution.     

The carving-width of generalized hypercubes

The carving-width of a graph is the minimum congestion of routing trees for the graph. We determine the carving-width of generalized hypercubes: Hamming graphs, even grids, and tori. Our results extend the result of Chandran and Kavitha [L.S. Chandran, T. Kavitha, The carvingwidth of hypercubes, Discrete Math. 306 (2006) 2270-2274] that determines the carving-width of hypercubes.     

Semidefinite programming approach for the quadratic assignment problem with a sparse graph

The matching problem between two adjacency matrices can be formulated as the NP-hard quadratic assignment problem (QAP). Previous work on semidefinite programming (SDP) relaxations to the QAP have produced solutions that are often tight in practice, but such SDPs typically scale badly, involving matrix variables of dimension \(n^2\) where n is the number of nodes. To achieve a speed up, we propose a further relaxation of the SDP involving a number of positive semidefinite matrices of dimension \(\mathcal {O}(n)\) no greater than the number of edges in one of the graphs. The relaxation can be further strengthened by considering cliques in the graph, instead of edges. The dual problem of this novel relaxation has a natural three-block structure that can be solved via a convergent Alternating Direction Method of Multipliers in a distributed manner, where the most expensive step per iteration is computing the eigendecomposition of matrices of dimension \(\mathcal {O}(n)\). The new SDP relaxation produces strong bounds on quadratic assignment problems where one of the graphs is sparse with reduced computational complexity and running times, and can be used in the context of nuclear magnetic resonance spectroscopy to tackle the assignment problem.     

Minimizing cyclic cutwidth of graphs using a memetic algorithm

Cyclic cutwidth minimization problem (CCMP) consists of embedding a graph onto a circle such that the maximum cutwidth in a region is minimized. It is an NP-complete problem and for some classes of graphs, exact results of cyclic cutwidth have been proved in literature. However, no algorithm has been reported for general graphs. In this paper, a memetic algorithm is proposed for CCMP in which we have designed six construction heuristics in order to generate a good initial population and also local search is employed to improve the solutions in each generational phase. The algorithm achieves optimal results for the classes of graphs with known exact results. Extensive experiments have also been conducted on some classes of graphs for which exact results are not known such as the complete split graph, join of hypercubes, toroidal meshes, cone graph and some instances of Harwell-Boeing graphs which are a subset of public domain Matrix Market library. Trends observed in the experimental results for some of the classes of graphs have led to conjectures for cyclic cutwidth.     

Antibandwidth and cyclic antibandwidth of meshes and hypercubes

The antibandwidth problem consists of placing the vertices of a graph on a line in consecutive integer points in such a way that the minimum difference of adjacent vertices is maximised. The problem was originally introduced in [J.Y.-T. Leung, O. Vornberger, J.D. Witthoff, On some variants of the bandwidth minimisation problem, SIAM Journal of Computing 13 (1984) 650-667] in connection with the multiprocessor scheduling problems and can also be understood as a dual problem to the well-known bandwidth problem, as a special radiocolouring problem or as a variant of obnoxious facility location problems. The antibandwidth problem is NP-hard, there are a few classes of graphs with polynomial time complexities. Exact results for nontrivial graphs are very rare. Miller and Pritikin [Z. Miller, D. Pritikin, On the separation number of a graph, Networks 19 (1989) 651-666] showed tight bounds for the two-dimensional meshes and hypercubes. We solve the antibandwidth problem precisely for two-dimensional meshes, tori and estimate the antibandwidth value for hypercubes up to the third-order term. The cyclic antibandwidth problem is to embed an n-vertex graph into the cycle C_n, such that the minimum distance (measured in the cycle) of adjacent vertices is maximised. This is a natural extension of the antibandwidth problem or a dual problem to the cyclic bandwidth problem. We start investigating this invariant for typical graphs and prove basic facts and exact results for the same product graphs as for the antibandwidth.     

Performance of a genetic algorithm for the graph partitioning problem

The performance of the genetic algorithm (GA) for the graph partitioning problem (GPP) is investigated by comparison with standard heuristics on well-known benchmark graphs. In general, there is a case where a practical performance of a conventional genetic approach, which performs only simple operations without a local search strategy, is not sufficient. However, it is known that a combination of GA and local search can produce better solutions. From this practice, we incorporate a simple local search algorithm into the GA. In particular, the search ability of the GA is compared with standard heuristics such as multistart local search and simulated annealing, which use the same neighborhood structure of the simple local search, for solving the GPP. Experimental results show that the GA performs better than its competitors.