We address the electric autonomous dial-a-ride problem (E-ADARP), a challenging extension of the dial-a-ride problem with the goal of finding minimum-cost routes serving given transportation requests with a fleet of electric and autonomous vehicles (EAVs). Special emphasis lies on the minimization of user excess ride time under consideration of the charging requirements of the EAVs, while operational constraints have to be satisfied. We propose a novel large neighborhood search (LNS) approach for the E-ADARP together with two alternatives for handling the charging of the EAVs, the scheduling, and route evaluation. One deals with these challenges separately using dedicated LNS operators and a forward labeling algorithm, and the other provides a combined approach with on-the-fly charging stop insertion during route evaluation. The performance of the algorithms is evaluated on various configurations of two common benchmark sets as well as some very large-scale instances. Results show that especially the approach with the on-the-fly insertion almost consistently outperforms former state-of-the-art techniques on the common benchmark instances, finding many new best known solutions. For this best performing approach, multiple variants of a more advanced destroy operator for the underlying LNS are investigated. This enhancement can yield significantly improved performance, especially on the very large instances, as illustrated by further empirical results.

This paper studies the Dynamic Electric Dial-A-Ride Problem (DEDARP), which is a combinatorial optimisation problem that has applications in real-world ridesharing services with electric vehicles. In addition to the challenges from classical scheduling and route planning, we consider here the extra challenge of making real-time dispatching decisions in dynamic environments with new requests arriving over time and selecting proper times for the vehicles to recharge. To solve DEDARP effectively, we propose a Genetic Programming Hyper-Heuristic (GPHH) that evolves heuristics/policies to dispatch vehicles in real time. We have developed a simulation process that generates a solution for any given instance by two policies, one for vehicle allocation and the other for request allocation, and design fitness evaluations based on the simulation. Moreover, we propose a multi-tree GP to evolve these two policies simultaneously, which makes use of advanced terminals to comprehensively represent the state. Experimental results on a wide range of instances show that GPHH can evolve effective policies that make significantly better real-time dispatching decisions than human-designed policies based on prior knowledge.

This paper introduces a hybrid algorithm that integrates the Construct, Merge, Solve and Adapt (CMSA) metaheuristic with Column Generation (CG) to solve the Variable-Sized Bin Packing Problem (VSBPP). The VSBPP, which requires packing items of varying sizes into bins of different types and costs, is a core combinatorial optimization problem with applications in logistics and resource allocation. Our approach builds upon a previously proposed CMSA-based framework by incorporating a column generation procedure to strengthen the linear programming relaxation and generate improved patterns. In each iteration, heuristic solution construction and merging phases produce a pool of feasible packing patterns. These are then used in a linear programming master problem, from which dual values are extracted and used to solve a knapsack pricing subproblem. This identifies new patterns (columns) with negative reduced cost to be added to the model. Finally, an integer programming phase refines the solution using a reduced subinstance. The algorithm is evaluated on benchmark instances and compared with both the previously published standalone CMSA approach and a standalone column generation method. Experimental results show that the combined CMSA-COLGEN approach consistently outperforms both baselines in terms of solution quality and robustness, particularly on larger and more complex instances.

This article considers the longest common square subsequence (LCSqS) problem, a variant of the longest common subsequence (LCS) problem in which solutions must be square strings. A square string can be expressed as the concatenation of a string with itself. The LCSqS problem has applications in bioinformatics, for discovering internal similarities between molecular structures. We propose a metaheuristic approach, a biased random key genetic algorithm (BRKGA) hybridized with a beam search (BS) from the literature. Our approach is based on reducing the LCSqS problem to a set of promising LCS problems. This is achieved by cutting each input string into two parts first and then evaluating such a transformed instance by solving the LCS problem for the obtained overall set of strings. The task of the BRKGA is, hereby, to find a set of good cut points for the input strings. For this purpose, the search is carefully biased by problem-specific greedy information. For each cut point vector, the resulting LCS problem is approximately solved by the existing BS approach. The proposed algorithm is evaluated against a previously proposed state-of-the-art variable neighborhood search (VNS) on random uniform instances from the literature, new nonuniform instances, and a real-world instance set consisting of DNA strings. The results underscore the importance of our work, as our novel approach outperforms former state-of-the-art with statistical significance. Particularly, they evidence the limitations of the VNS when solving nonuniform instances, for which our method shows superior performance.

We consider the electric autonomous dial-a-ride problem (E-ADARP), a challenging extension of the dial-a-ride problem with the goal of finding minimum cost routes serving given transportation requests with a fleet of electric and autonomous vehicles (EAVs). Special emphasis lies on the minimization of user excess ride time under consideration of the charging requirements of the EAVs while constraints regarding, for example, user ride times and time windows have to be satisfied. We propose a novel large neighborhood search (LNS) approach for the E-ADARP employing the concept of battery-restricted fragments for route representation and efficient cost computations. For the charging of the EAVs, the scheduling, and route evaluation, we introduce two approaches where one deals with these challenges separately and one provides a combined approach. The first approach uses dedicated LNS operators and a forward labeling algorithm whereas the latter employs a novel route evaluation procedure for inserting charging stops on-the-fly as needed. The performance of our LNS-based algorithms is evaluated on common benchmark instances and results show that especially the approach with the on-the-fly insertion almost consistently outperforms former state-of-the-art techniques, finding new best-known solutions for many instances.

The traveling tournament problem is a well-known sports league scheduling problem famous for its practical hardness. Given an even number of teams with symmetric distances between their venues, a double round-robin tournament has to be scheduled minimizing the total travel distances over all teams. We consider the most common constrained variant without repeaters and a streak limit of three, for which we study a beam search approach based on a state-space formulation guided by heuristics derived from different lower bound variants. We solve the arising capacitated vehicle routing subproblems either exactly for small- to medium-sized instances up to 18 teams or heuristically also for larger instances up to 24 teams. In a randomized variant of the search, we employ random team ordering and add small amounts of Gaussian noise to the nodes' guidance for diversification when multiple runs are performed. This allows for a simple yet effective parallelization of the beam search. A final comparison is done on the NL, CIRC, NFL, and GALAXY benchmark instances with 12 to 24 teams, for which we report a mean gap difference to the best known feasible solutions of 1.2% and five new best feasible solutions.

The shortest common supersequence problem (SCSP) is a well-known NP-hard problem with many applications, in particular in data compression, computational molecular biology, and text editing. It aims at finding for a given set of input strings a shortest string such that every string from the set is a subsequence of the computed string. Due to its NP-hardness, many approaches have been proposed to tackle the SCSP heuristically. The currently best-performing one is based on beam search (BS). In this paper, we present a novel heuristic (AEL) for guiding a BS, which approximates the expected length of an SCSP of random strings, and embed the proposed heuristic into a multilevel probabilistic beam search (MPBS). To overcome the arising scalability issue of the guidance heuristic, a cut-off approach is presented that reduces large instances to smaller ones. The proposed approaches are tested on two established sets of benchmark instances. MPBS guided by AEL outperforms the so far leading method on average on a set of real instances. For many instances new best solutions could be obtained.

Inspired by the recent success of parallelized exact methods to solve difficult scheduling problems, we present preliminary results of a general parallel beam search framework for combinatorial optimization problems. Beam search is a constructive metaheuristic traversing a search tree layer by layer while keeping in each layer a bounded number of promising nodes to consider many partial solutions in parallel. We propose a variant which is suitable for intra-node parallelization by multithreading with data parallelism. For sufficiently large problem instances and beam widths our work-in-progress implementation in the JIT-compiled Julia language admits promising speed-ups over 30x on 32 cores with uniform memory access for the Permutation Flow Shop Scheduling (PFSP) problem with flowtime objective.

Public bike sharing systems require some kind of rebalancing to avoid too many rental stations of running empty or entirely full, which would make the system ineffective and annoy customers. Most frequently, a fleet of vehicles with trailers is used for this purpose, moving bikes among the stations. Previous works considered different objectives and modeled the underlying routing problem in different ways, but they all allow an arbitrary number of bikes to be picked up at some stations and delivered to other stations, just limited by the vehicles’ capacities. Observations in practice, however, indicate that in larger well‐working bike sharing systems drivers almost never pickup or deliver only few bikes, but essentially always approximately full vehicle loads. Many stations even require several visits with full loads. Due to budgetary reasons, typically only just enough drivers and vehicles are employed to achieve a reasonable balance most of the time, but basically never an ideal one where single bikes play a substantial role. Consequently, we investigate here a simplified problem model, in which only full vehicle loads are considered for movement among the rental stations. This restriction appears to have only a minor impact on the achieved quality of the rebalancing in practice but eases the modeling substantially. More specifically, we formulate the rebalancing problem as a selective unit‐capacity pickup and delivery problem with time budgets on a bipartite graph and present a compact mixed integer linear programming model, a logic‐based Benders decomposition and a variant thereof, namely branch‐and‐check for it. For the general case, instances with up to 70 stations, and for the single‐vehicle case instances with up to 120 stations are solved to proven optimality. A comparison to leading metaheuristic approaches considering flexible vehicle loads indicates that indeed the restriction to full loads has only a very small impact on the finally achieved balance in typical scenarios of Citybike Wien. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 69(3), 270–289 2017

The most strings with few bad columns problem is an NP-hard combinatorial optimization problem from the bioinformatics field. This paper presents the first integer linear programming model for this problem. Moreover, a simple greedy heuristic and a more sophisticated extension, namely a greedy-based pilot method, are proposed. Experiments show that, as expected, the greedy-based pilot method improves over the greedy strategy. For problem instances of small and medium size the best results were obtained by solving the integer linear programming model by CPLEX, while the greedy-based pilot methods scales much better to large problem instances.

Abstract We consider a rather generic class of network design problems in which a set or subset of given terminal nodes must be connected to a dedicated root node by simple paths and a variety of resource and/or quality of service constraints must be respected. These extensions of the classical Steiner tree problem on a graph can be well modeled by a path formulation in which individual variables are used for all feasible paths. To solve this formulation in practice, branch‐and‐price is used. It turns out, however, that a naive implementation of column generation suffers strongly from certain degeneracies of the pricing subproblem, leading to excessive running times. After analyzing these computational problems, we propose two methods to accelerate and stabilize column generation by using alternative dual‐optimal solutions. The resulting branch‐and‐price approach is practically tested on the rooted delay‐constrained Steiner tree problem and a quota‐constrained version of it. Results indicate that the proposed methods in general speed‐up the solution process dramatically, far more than a piecewise linear stabilization to which we compare. Furthermore, our branch‐and‐price approach exhibits on most test instances a better performance than a state‐of‐the‐art branch‐and‐cut approach based on layered graphs. As the new stabilization technique utilizing alternative dual‐optimal solutions is generic in the sense that it easily adapts to the inclusion of a large variety of further constraints and different objective functions, the proposed method is highly promising for a large class of network design problems. © 2012 Wiley Periodicals, Inc. NETWORKS, 2013

We consider the recently proposed concept of enhancing an evolutionary algorithm (EA) with a complete solution archive. It stores evaluated solutions during the optimization in order to detect duplicates and to efficiently transform them into yet unconsidered solutions. For this approach we introduce the so-called bounding extension in order to identify and prune branches in the trie-based archive which only contain inferior solutions. This extension enables the EA to concentrate the search on promising areas of the solution space. Similarly to the classical branch-and-bound technique, bounds are obtained via primal and dual heuristics. As an application we consider the generalized minimum spanning tree problem where we are given a graph with nodes partitioned into clusters and exactly one node from each cluster must be connected in the cheapest way. As the EA uses operators based on two dual representations, we exploit two corresponding tries that complement each other. Test results on TSPlib instances document the strength of this concept and that it can compete with the leading metaheuristics for this problem in the literature.

In this paper we present the application of an evolution strategy to the problem of detecting multi-planet transit events in photometric time-data series. Planetary transits occur when a planet regularly eclipses its host star, reducing stellar luminosity. The transit method is amongst the most successful detection methods for exoplanet and is presently performed by space telescope missions.

We study the multidimensional knapsack problem, present some theoretical and empirical results about its structure, and evaluate different integer linear programming (ILP)-based, metaheuristic, and collaborative approaches for it. We start by considering the distances between optimal solutions to the LP relaxation and the original problem and then introduce a new core concept for the multidimensional knapsack problem (MKP), which we study extensively. The empirical analysis is then used to develop new concepts for solving the MKP using ILP-based and memetic algorithms. Different collaborative combinations of the presented methods are discussed and evaluated. Further computational experiments with longer run times are also performed to compare the solutions of our approaches to the best-known solutions of another so-far leading approach for common MKP benchmark instances. The extensive computational experiments show the effectiveness of the proposed methods, which yield highly competitive results in significantly shorter run times than do previously described approaches.

Abstract We consider the generalized minimum edge‐biconnected network problem where the nodes of a graph are partitioned into clusters and exactly one node from each cluster is required to be connected in an edge‐biconnected way. Instances of this problem appear, for example, in the design of survivable backbone networks. We present different variants of a variable neighborhood search approach that utilize different types of neighborhood structures, each of them addressing particular properties as spanned nodes and/or the edges between them. For the more complex neighborhood structures, we apply efficient techniques—such as a graph reduction—to essentially speed up the search process. For comparison purposes, we use a mixed integer linear programming formulation based on multi‐commodity flows to solve smaller instances of this problem to proven optimality. Experiments on such instances indicate that the variable neighborhood search is also able to identify optimal solutions in the majority of test runs, but within substantially less time. Tests on larger Euclidean and random instances with up to 1,280 nodes, which could not be solved to optimality by mixed integer programming, further document the efficiency of the variable neighborhood search. In particular, all proposed neighborhood structures are shown to contribute significantly to the search process. © 2010 Wiley Periodicals, Inc. NETWORKS, 2010

The bounded diameter minimum spanning tree problem is an NP-hard combinatorial optimization problem arising, for example, in network design when quality of service is of concern. There exist various exact and metaheuristic approaches addressing this problem, whereas fast construction heuristics are primarily based on Prim’s minimum spanning tree algorithm and fail to produce reasonable solutions in particular on large Euclidean instances. A method based on hierarchical clustering to guide the construction process of a diameter constrained tree is presented. Solutions obtained are further refined using a greedy randomized adaptive search procedure. Based on the idea of clustering we also designed a new neighborhood search for this problem. Especially on large Euclidean instances with a tight diameter bound the results are excellent. In this case the solution quality can also compete with that of a leading metaheuristic, whereas the computation only needs a fraction of the time. Categories and Subject Descriptors

In this work, we present two new approaches based on variable neighborhood search (VNS) and ant colony optimization (ACO) for the reconstruction of cross cut shredded text documents. For quickly obtaining initial solutions, we consider four different construction heuristics. While one of them is based on the well known algorithm of Prim, another one tries to match shreds according to the similarity of their borders. Two further construction heuristics rely on the fact that in most cases the left and right edges of paper documents are blank, i.e. no text is written on them. Randomized variants of these construction heuristics are applied within the ACO. Experimental tests reveal that regarding the solution quality the proposed ACO variants perform better than the VNS approaches in most cases, while the running times needed are shorter for VNS. The high potential of these approaches for reconstructing cross cut shredded text documents is underlined by the obtained results.

The consensus tree problem arises in the domain of phylogenetics and seeks to find for a given collection of trees a single tree best representing it. Usually, such a tree collection is obtained by biologists for a given taxa set either via different phylogenetic inference methods or multiple applications of a non-deterministic procedure. There exist various consensus methods which often have the drawback of being very strict, limiting the resulting consensus tree in terms of its resolution and/or precision. A reason for this typically is the coarse granularity of the tree metric used. To find fully resolved (binary) consensus trees of high quality, we consider the fine-grained TreeRank similarity measure and extend a previously presented evolutionary algorithm (EA) to a memetic algorithm (MA) by including different variants of local search using neighborhoods based on moves of single taxa as well as subtrees. Furthermore, we propose a variable neighborhood search (VNS) with an embedded variable neighborhood descent (VND) based on the same neighborhood structures. Finally sequential and intertwined combinations of the EA and MA with the VNS/VND are investigated. We give results on real and artificially generated data indicating in particular the benefits of the hybrid methods.

The Railway Traveling Salesman Problem (RTSP) is a practical extension of the classical traveling salesman problem considering a railway network and train schedules. We are given a salesman who has to visit a number of cities to carry out some business. He starts and ends at a specified home city, and the required time for the overall journey, including waiting times, shall be minimized. In this paper, we present two transformation schemes to reformulate the RTSP as either a classical asymmetric or symmetric Traveling Salesman Problem (TSP). Using these transformations, established algorithms for solving the TSP can be used to attack the RTSP as well. Tests using the branch-and-cut TSP solver from the Concorde library show that this transformation is efficient and, thus, is highly competitive compared to so far existing approaches for solving the RTSP directly.

We consider the Bounded Diameter Minimum Spanning Tree problem and describe four neighbourhood searches for it. They are used as local improvement strategies within a variable neighbourhood search (VNS), an evolutionary algorithm (EA) utilising a new encoding of solutions, and an ant colony optimisation (ACO). We compare the performance in terms of effectiveness between these three hybrid methods on a suite of popular benchmark instances, which contains instances too large to solve by current exact methods. Our results show that the EA and the ACO outperform the VNS on almost all used benchmark instances. Furthermore, the ACO yields most of the time better solutions than the EA in long-term runs, whereas the EA dominates when the computation time is strongly restricted.

Many graph problems seek subgraphs of minimum weight that satisfy a set of constraints. Examples include the minimum spanning tree problem (MSTP), the degree-constrained minimum spanning tree problem (d-MSTP), and the traveling salesman problem (TSP). Low-weight edges predominate in optimum solutions to such problems, and the performance of evolutionary algorithms (EAs) is often improved by biasing variation operators to favor these edges. We investigate the impact of biased edge-exchange mutation. In a large-scale empirical investigation on Euclidean and uniform random instances, we describe the distributions of edges in optimum solutions of the MSTP, the d-MSTP, and the TSP in terms of the edges' weight-based ranks. We approximate these distributions by exponential functions and derive approximately optimal probabilities for selecting edges to be incorporated into candidate solutions during mutation. A theoretical analysis of the expected running time of a (1+1)-EA on nondegenerate instances of the MSTP shows that when using the derived probabilities for edge selection in mutation, the (1+1)-EA is asymptotically as fast as a classical implementation of Kruskal's minimum spanning tree algorithm. In experiments on the MSTP, d-MSTP, and the TSP, we compare the new edge-selection strategy to four alternative methods. The results of a (1+1)-EA on instances of the MSTP support the theory and indicate that the new strategy is superior to the other methods in practice. On instances of the d-MSTP, a more sophisticated EA with a larger population and unbiased recombination performs better with the new biased mutation than with alternate mutations. On the TSP, the advantages of weight-biased mutation are generally smaller, because the insertion of a specific new edge into a tour requires the insertion of a second dependent edge as well. Although we considered Euclidean and uniform random instances only, we conjecture that the same biasing toward low-weight edges also works well on other instance classes structured in different ways.

Our main aim is to provide guidelines and practical help for the design of appropriate representations and operators for evolutionary algorithms (EAs). For this purpose, we propose techniques to obtain a better understanding of various effects in the interplay of the representation and the operators. We study six different representations and associated variation operators in the context of a steady-state evolutionary algorithm for the multidimensional knapsack problem. Four of them are indirect decoder-based techniques, and two are direct encodings combined with different initialization, repair, and local improvement strategies. The complex decoders and the local improvement and repair strategies make it practically impossible to completely analyze such EAs in a fully theoretical way. After comparing the general performance of the chosen EA variants for the multidimensional knapsack problem on two benchmark suites, we present a hands-on approach for empirically analyzing important aspects of initialization, mutation, and crossover in an isolated fashion. Static, inexpensive measurements based on randomly created solutions are performed in order to quantify and visualize specific properties with respect to heuristic bias, locality, and heritability. These tests shed light onto the complex behavior of such EAs and point out reasons for good or bad performance. In addition, the proposed measures are also examined during actual EA runs, which gives further insight into dynamic aspects of evolutionary search and verifies the validity of the isolated static measurements. All measurements are described in a general way, allowing for an easy adaption to other representations and problems.

The fundamental design choices in an evolutionary algorithm (EA) are its representation of candidate solutions and the operators that will act on that representation. We propose representing spanning trees in EAs for network design problems directly as sets of their edges and we describe initialization, recombination, and mutation operators for this representation. The operators offer locality, heritability, and computational efficiency. Initialization and recombination depend on an underlying random spanning-tree algorithm. Three choices for this algorithm, based on the minimum spanning-tree algorithms of Prim and Kruskal and on random walks, respectively, are examined analytically and empirically. We demonstrate the usefulness of the edge-set encoding in an EA for the NP-hard degree-constrained minimum spanning-tree problem. The algorithm's operators are easily extended to generate only feasible spanning trees and to incorporate local, problem-specific heuristics. Comparisons of this algorithm to others that encode candidate spanning trees via the Blob Code, with network random keys, and as strings of weights indicate the superiority of the edge-set encoding, particularly on larger instances.

This paper describes an ant colony system (ACS) for labeling point features. A pre-processing step reduces the search space in a safe way. The ACS applies local improvement and masking, a technique that focuses the optimization on critical regions. Empirical results indicate that the ACS reliably identifies high-quality solutions which are in many cases better than those of a state-of-the-art genetic algorithm for point-feature labeling.

The representation of candidate solutions and the variation operators are fundamental design choices in an evolutionary algorithm (EA). This paper proposes a novel representation technique and suitable variation operators for the degree-constrained minimum spanning tree problem. For a weighted, undirected graph G(V, E), this problem seeks to identify the shortest spanning tree whose node degrees do not exceed an upper bound d/spl ges/2. Within the EA, a candidate spanning tree is simply represented by its set of edges. Special initialization, crossover, and mutation operators are used to generate new, always feasible candidate solutions. In contrast to previous spanning tree representations, the proposed approach provides substantially higher locality and is nevertheless computationally efficient; an offspring is always created in O(|V|) time. In addition, it is shown how problem-dependent heuristics can be effectively incorporated into the initialization, crossover, and mutation operators without increasing the time-complexity. Empirical results are presented for hard problem instances with up to 500 vertices. Usually, the new approach identifies solutions superior to those of several other optimization methods within few seconds. The basic ideas of this EA are also applicable to other network optimization tasks.

This paper presents different variants of weight-coding in a genetic algorithm (GA) for solving the multi-constraint knapsack problem (MKP). In this coding, a chromosome is a vector of weights associated with the items of the MKP. The phenotype is obtained by using the weights to generate a modified version of the original problem and applying a decoding heuristic to it. Four techniques of biasing the original problem with weights are discussed. Two well working decoding heuristics, one based on surrogate relaxation and the other based on Lagrangian relaxation, are introduced. The different weight-coding variants are experimentally compared to each other using a steady-state GA. Furthermore, the influence of the biasing strength, a strategy parameter of the codings, is investigated. In general, the GA found solutions being substantially better than those obtained by applying heuristics to the MKP directly.