Exact algorithm and heuristic for the Closest String Problem

The Closest String Problem (CSP) is an NP-hard problem, which arises in computational molecular biology and coding theory. This class of problems is to find a string that minimizes the maximum Hamming distance to a given set of strings. In this paper, we present an exact algorithm called Distance First Algorithm (DFA) for three strings of CSP with alphabet size two. For the general CSP, we design a polynomial heuristic which is a combination of our proposed approximation algorithm LDDA ([10] Liu Xiaolan, Fu Keqiang, Shao Renxiang. Largest distance decreasing algorithm for the Closest String Problem. Journal of Information & Computational Science 2004; 1(2): 287–92) and local search strategies. Numerical results show that the proposed heuristic may obtain a nearly optimal value in a reasonable time for small and large-scale instances of the CSP.     

A parallel multistart algorithm for the closest string problem

In this paper we describe and implement a parallel algorithm to find approximate solutions for the Closest String Problem (CSP). The CSP, also known as Motif Finding problem, has applications in Coding Theory and Computational Biology. The CSP is NP-hard which motivates us to think about heuristics to solve large instances. Several approximation algorithms have been designed for the CSP, but all of them have a poor performance guarantee. Recently some researchers have shown empirically that integer programming techniques can be successfully used to solve moderate-size instances (10–30 strings each of which is 300–800 characters long) of the CSP. However, real-world instances are larger than those tested. In this paper we show how a simple heuristic can be used to find near-optimal solutions to that problem. We implemented a parallel version of this heuristic and report computational experiments on large-scale instances. These results show the effectiveness of our approach.     

A similarity hybrid harmony search algorithm for the Team Orienteering Problem

The Harmony Search (HS) is a metaheuristic algorithm, which is inspired from the composition of music harmonies. The functionality and flexibility of HS contribute to the development of successful methodologies for different kind of scientific problems. The aim of this paper is to propose a variant of the classic HS algorithm in order to provide competitive solutions for the Team Orienteering Problem (TOP). We introduce the Similarity Hybrid Harmony Search (SHHS) algorithm as an alternative and innovative optimization method. The SHHS follows the standard procedure of HS with some modifications and includes a new strategy called “similarity process”. Two versions of the proposed method have been developed, the static version with predefined values for the parameters of the method and the dynamic one with dynamic adjustment of the parameters. The SHHS algorithm is applied to the known benchmark instances of TOP. The dynamic of the algorithm is tested through a complete solution analysis which gives the superiority of the dynamic version compared to the static one. The results of both versions of the proposed algorithm indicate the positive performance against other effective and robust optimization algorithms from the literature.     

Hybridized ant colony algorithm for the Multi Compartment Vehicle Routing Problem

Multi Compartment Vehicle Routing Problem is an extension of the classical Capacitated Vehicle Routing Problem where different products are transported together in one vehicle with multiple compartments. Products are stored in different compartments because they cannot be mixed together due to differences in their individual characteristics. The problem is encountered in many industries such as delivery of food and grocery, garbage collection, marine vessels, etc. We propose a hybridized algorithm which combines local search with an existent ant colony algorithm to solve the problem. Computational experiments are performed on new generated benchmark problem instances. An existing ant colony algorithm and the proposed hybridized ant colony algorithm are compared. It was found that the proposed ant colony algorithm gives better results as compared to the existing ant colony algorithm.     

A heuristic algorithm based on Monte Carlo methods for the Rural Postman Problem

In Routing Problems the aim is to determine a minimum cost traversal over a graph satisfying some specified constraints. Most of them are NP-hard problems and many different heuristic solution algorithms have been proposed. The name Monte Carlo, MC, applies to a set of heuristic procedures with the common feature of using random numbers to simulate a given process. MC approach has not been applied to the framework of Routing Problems in the literature. The purpose of this paper is to demonstrate that MC methods could be useful in implementing heuristic algorithms for Routing Problems. In particular, we design an efficient MC heuristic algorithm for the well known Rural Postman Problem (RPP), for which we have a set of instances with known optimal solution taken from the literature.The Rural Postman Problem (RPP) consists of finding a minimum cost traversal of a specified arc subset of a graph. Given that the RPP is a NP-hard problem, heuristic algorithms are interesting both to handle large size instances and to provide upper bounds that could be used in branch and cut procedures. In this paper we propose a heuristic algorithm for the RPP based on Monte Carlo methods. We simulate a vehicle travelling randomly over the graph, jumping from one node to another on the basis of certain probabilities. Monte Carlo methods provide a simple approach to many different Routing Problems and they are easily implemented in a computer code. The application of this algorithm to a set of RPP instances taken from the literature demonstrates that, using the appropriate probabilities, they are also efficient.     

A heuristic algorithm based on Lagrangian relaxation for the closest string problem

The closest string problem that arises in both computational biology and coding theory is to find a string minimizing the maximum Hamming distance from a given set of strings. This study proposes an efficient heuristic algorithm for this NP-hard problem. The key idea is to apply the Lagrangian relaxation technique to the problem formulated as a mixed-integer programming problem. This enables us to decompose the problem into trivial subproblems corresponding to each position of the strings. Furthermore, a feasible solution can be easily obtained from a solution of the relaxation. Based on this, a heuristic algorithm is constructed by combining a Lagrangian multiplier adjustment procedure and a tabu search. Computational experiments will show that the proposed algorithm can find good approximate solutions very fast.     

A constructive heuristic for the Undirected Rural Postman Problem

This paper describes a constructive heuristic for the well-known Undirected Rural Postman Problem. At each iteration, the procedure inserts a connected component of the required edges and performs a local postoptimization. Computational results on a set of benchmark instances with up to 350 vertices show that the proposed procedure is competitive with the classical Frederickson procedure. Its use is recommended when a high-quality solution is needed in a short amount of time (e.g., in laser plotter applications).     

A GRASP algorithm based new heuristic for the capacitated location routing problem

Abstract

In this paper, the capacitated location-routing problem (CLRP) is studied. CLRP is composed of two hard optimisation problems: the facility location problem and the vehicle routing problem. The objective of CLRP is to determine the best location of multiple depots with their vehicle routes such that the total cost of the solution is minimal. To solve this problem, we propose a greedy randomised adaptive search procedure. The proposed method is based on a new heuristic to construct a feasible CLRP solution, and then a local search-based simulated annealing is used as improvement phase. We have used a new technique to construct the clusters around the depots. To prove the effectiveness of our algorithm, several LRP instances are used. The results found are very encouraging.     

A domain-specific knowledge-based heuristic for the Blocks Relocation Problem

The Blocks Relocation Problem consists in minimizing the number of movements performed by a gantry crane in order to retrieve a subset of containers placed into a bay of a container yard according to a predefined order. A study on the mathematical formulations proposed in the related literature reveals that they are not suitable for its solution due to their high computational burden. Moreover, in this paper we show that, in some cases, they do not guarantee the optimality of the obtained solutions. In this regard, several optimization methods based on the well-known A¹ search framework are introduced to tackle the problem from an exact point of view. Using our A¹ algorithm we have corrected the optimal objective function value of 17 solutions out of 45 instances considered by Caserta et al. (2012) [4]. In addition, this work presents a domain-specific knowledge-based heuristic algorithm to find high-quality solutions by means of short computational times. It is based on finding the most promising positions into the bay where to relocate those containers that are currently located on the next one to be retrieved, in such a way that, they do not require any additional relocation operation in the future. The computational tests indicate the higher effectiveness and efficiency of the suggested heuristic when solving real-world scenarios in comparison with the most competitive approaches from the literature.     

A GRASP/VND heuristic for the phylogeny problem using a new neighborhood structure

A phylogeny is a tree that relates taxonomic units, based on their similarity over a set of characters. The phylogeny problem consists in finding a phylogeny with the minimum number of evolutionary steps. We propose a new neighborhood structure for the phylogeny problem. A greedy randomized adaptive search procedure heuristic based on this neighborhood structure and using variable neighborhood descent for local search is described. Computational results on randomly generated and benchmark instances are reported, showing that the new heuristic is quite robust and outperforms the other algorithms in the literature in terms of solution quality and time‐to‐target value.     

An ILP based heuristic for a generalization of the post-enrollment course timetabling problem

We consider a new timetabling problem arising from a real-world application in a private university in Buenos Aires, Argentina. In this paper we describe the problem in detail, which generalizes the Post-Enrollment Course Timetabling Problem (PECTP), propose an ILP model and a heuristic approach based on this formulation. This algorithm has been implemented and tested on instances obtained from real data, showing that the approach is feasible in practice and produces good quality solutions.     

A Branch-and-Prune algorithm for the Molecular Distance Geometry Problem

The Molecular Distance Geometry Problem consists in finding the positions in of the atoms of a molecule, given some of the inter‐atomic distances. We show that under an additional requirement on the given distances this can be transformed to a combinatorial problem. We propose a Branch‐and‐Prune algorithm for the solution of this problem and report on very promising computational results.     

求解MSA问题的新型单亲遗传算法

多序列联配(MSA)在生物信息学研究中占有重要地位,MSA问题是一个典型的NP问题,遗传算法是求解NP完全问题的一种理想方法。文章针对MSA问题,提出了一种新型单亲遗传算法(PGA),不使用交叉算子,只使用变异和选择算子。并根据群体的多样性自适应调节变异概率,有效消除了算法中的欺骗性条件,使用灾变算子来确保算法的搜索能力。整个算法模拟了自然界进化的周期性,较好地解决了群体的多样性和收敛深度的矛盾。算法的分析和测试表明,该算法是有效的。     

An effective heuristic algorithm for the maximum satisfiability problem

Stochastic local search algorithms (SLS) have been increasingly applied to approximate solutions of the weighted maximum satisfiability problem (MAXSAT), a model for solutions of major problems in AI and combinatorial optimization. While MAXSAT instances have generally a strong intrinsic dependency between their variables, most of SLS algorithms start the search process with a random initial solution where the value of each variable is generated independently with the same uniform distribution. In this paper, we propose a new SLS algorithm for MAXSAT based on an unconventional distribution known as the Bose-Einstein distribution in quantum physics. It provides a stochastic initialization scheme to an efficient and very simple heuristic inspired by the co-evolution process of natural species and called Extremal Optimization (EO). This heuristic was introduced for finding high quality solutions to hard optimization problems such as colouring and partitioning. We examine the effectiveness of the resulting algorithm by computational experiments on a large set of test instances and compare it with some of the most powerful existing algorithms. Our results are remarkable and show that this approach is appropriate for this class of problems.     

A hybrid algorithm for a class of vehicle routing problems

In this work we propose a hybrid algorithm for a class of Vehicle Routing Problems with homogeneous fleet. A sequence of Set Partitioning (SP) models, with columns corresponding to routes found by a metaheuristic approach, are solved, not necessarily to optimality, using a Mixed Integer Programming (MIP) solver, that may interact with the metaheuristic during its execution. Moreover, we developed a reactive mechanism that dynamically controls the dimension of the SP models when dealing with large size instances. The algorithm was extensively tested on benchmark instances of the following Vechicle Routing Problem (VRP) variants: (i) Capacitated VRP; (ii) Asymmetric VRP; (iii) Open VRP; (iv) VRP with Simultaneous Pickup and Delivery; (v) VRP with Mixed Pickup and Delivery; (vi) Multi-depot VRP; (vii) Multi-depot VRP with Mixed Pickup and Delivery. The results obtained were quite competitive with those found by heuristics devoted to specific variants. A number of new best solutions were obtained.     

A GRASP heuristic using path‐relinking and restarts for the Steiner traveling salesman problem

The traveling salesman problem (TSP) is one of the most studied problems in combinatorial optimization. Given a set of nodes and the distances between them, it consists in finding the shortest route that visits each node exactly once and returns to the first. Nevertheless, more flexible and applicable formulations of this problem exist and can be considered. The Steiner TSP (STSP) is a variant of the TSP that assumes that only a given subset of nodes must be visited by the shortest route, eventually visiting some nodes and edges more than once. In this paper, we adapt some classical TSP constructive heuristics and neighborhood structures to the STSP variant. In particular, we propose a reduced 2‐opt neighborhood and we show that it leads to better results in smaller computation times. Computational results with an implementation of a GRASP heuristic using path‐relinking and restarts are reported. In addition, ten large test instances are generated. All instances and their best‐known solutions are made available for download and benchmarking purposes.     

A heuristic and a branch-and-bound algorithm for the Assembly Line Worker Assignment and Balancing Problem

In traditional assembly lines, it is reasonable to assume that task execution times are the same for each worker. However, in Sheltered Work Centres for Disabled this assumption is not valid: some workers may execute some tasks considerably slower or even be incapable of executing them. Worker heterogeneity leads to a problem called the Assembly Line Worker Assignment and Balancing Problem (ALWABP). For a fixed number of workers the problem is to maximize the production rate of an assembly line by assigning workers to stations and tasks to workers, while satisfying precedence constraints between the tasks.This paper introduces new heuristic and exact methods to solve this problem. We present a new MIP model, propose a novel heuristic algorithm based on beam search, as well as a task-oriented branch-and-bound procedure which uses new reduction rules and lower bounds for solving the problem. Extensive computational tests on a large set of instances show that these methods are effective and improve over existing ones.     

An optimization algorithm for the workforce management in a retail chain

This work proposes a scheduling problem for the workforce management in a chain of supermarkets operating in Italy. We focus on determining the ideal mix of full-time and part-time workers which are needed every week to guarantee a satisfactory service level during the check-out operations. The generation of working shifts, to be assigned to retail workers, is subject to several constraints imposed by both labour laws and enterprise bargaining agreements.We present a mathematical formulation of the problem followed by an exact solution approach which relies on the definition of feasible daily working shifts. The number of feasible daily shifts, that are combined to determine feasible weekly shifts, could drastically increase, depending on the selected planning interval. In addition, there may exist additional constraints, that are difficult to incorporate into the mathematical model. For these reasons, a hybrid heuristic, which does not require the generation of all feasible weekly shifts, is proposed in this paper.Using appropriate statistical techniques, a sensitivity analysis is performed to test the design of the hybrid heuristic. Computational tests are carried out by solving several real instances provided by the retail firm. The results obtained by the heuristic are compared both with an exact approach and with the solutions adopted by the retail company, which have been determined by using a naïf approach. Our hybrid heuristic exhibits excellent performance finding optimal or near optimal solutions in a very limited CPU time.     

A hybrid GRASP/VND heuristic for the one-commodity pickup-and-delivery traveling salesman problem

We address in this paper the one-commodity pickup-and-delivery traveling salesman problem, which is characterized by a set of customers, each of them supplying (pickup customer) or demanding (delivery customer) a given amount of a single product. The objective is to design a minimum cost Hamiltonian route for a capacitated vehicle in order to transport the product from the pickup to the delivery customers. The vehicle starts the route from a depot, and its initial load also has to be determined. We propose a hybrid algorithm that combines the GRASP and VND metaheuristics. Our heuristic is compared with other approximate algorithms described in Hernández-Pérez and Salazar-González [Heuristics for the one-commodity pickup-and-delivery traveling salesman problem. Transportation Science 2004;38:245–55]. Computational experiments on benchmark instances reveal that our hybrid method yields better results than the previously proposed approaches.     

Solving the Urban Transit Routing Problem using a particle swarm optimization based algorithm

The Urban Transit Routing Problem (UTRP) comprises an NP-hard problem that deals with the construction of route networks for public transit networks. It is a highly complex and multiply constrained problem, in which the assessment of candidate route networks can be both time consuming and challenging. Except for that, a multitude of potential solutions are usually rejected due to infeasibility. Because of this difficulty, soft computing algorithms can be very effective for its efficient solution. The success of these methods, however, depends mainly on the quality of the representation of candidate solutions, on the efficiency of the initialization procedure and on the suitability of the modification operators used.An optimization algorithm, based on particle swarm optimization, is designed and presented in the current contribution, aiming at the efficient solution of UTRP. Apart from the development of the optimization algorithm, emphasis is also given on appropriate representation of candidate solutions, the route networks in other words, and the respective evaluation procedure. The latter procedure considers not only the quality of service offered to each passenger, but also the costs of the operator. Results are compared on the basis of Mandl's benchmark problem of a Swiss bus network, which is probably the only widely investigated and accepted benchmark problem in the relevant literature. Comparison of the obtained results with other results published in the literature shows that the performance of the proposed soft computing algorithm is quite competitive compared to existing techniques.