Search results for " Computer Science"
showing 10 items of 3983 documents
A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows
2010
In this paper, we present an effective memetic algorithm for the vehicle routing problem with time windows (VRPTW). The paper builds upon an existing edge assembly crossover (EAX) developed for the capacitated VRP. The adjustments of the EAX operator and the introduction of a novel penalty function to eliminate violations of the time window constraint as well as the capacity constraint from offspring solutions generated by the EAX operator have proven essential to the heuristic's performance. Experimental results on Solomon's and Gehring and Homberger benchmarks demonstrate that our algorithm outperforms previous approaches and is able to improve 184 best-known solutions out of 356 instance…
Scheduling Multimodal Transportation Systems
2004
Abstract In this paper a Lagrangian based heuristic procedure for scheduling transportation networks is presented. The solution procedure schedules a single line at a time, possibly correcting the previous decisions at each step.
Large multiple neighborhood search for the clustered vehicle-routing problem
2018
Abstract The clustered vehicle-routing problem is a variant of the classical capacitated vehicle-routing problem in which customers are partitioned into clusters, and it is assumed that each cluster must have been served completely before the next cluster is served. This decomposes the problem into three subproblems, i.e., the assignment of clusters to routes, the routing inside each cluster, and the sequencing of the clusters in the routes. The second task requires the solution of several Hamiltonian path problems, one for each possibility to route through the cluster. We pre-compute the Hamiltonian paths for every pair of customers of each cluster. We present a large multiple neighborhood…
A comparison of column-generation approaches to the Synchronized Pickup and Delivery Problem
2015
Abstract In the Synchronized Pickup and Delivery Problem (SPDP), user-specified transportation requests from origin to destination points have to be serviced by a fleet of homogeneous vehicles. The task is to find a set of minimum-cost routes satisfying pairing and precedence, capacities, and time windows. Additionally, temporal synchronization constraints couple the service times at the pickup and delivery locations of the customer requests in the following way: a request has to be delivered within prespecified minimum and maximum time lags (called ride times) after it has been picked up. The presence of these ride-time constraints severely complicates the subproblem of the natural column-…
Edge Orientation and the Design of Problem-Specific Crossover Operators for the OCST Problem
2012
In the Euclidean optimal communication spanning tree problem, the edges in optimal trees not only have small weights but also point with high probability toward the center of the graph. These characteristics of optimal solutions can be used for the design of problem-specific evolutionary algorithms (EAs). Recombination operators of direct encodings like edge-set and NetDir can be extended such that they prefer not only edges with small distance weights but also edges that point toward the center of the graph. Experimental results show higher performance and robustness in comparison to EAs using existing crossover strategies.
On the Bias and Performance of the Edge-Set Encoding
2009
The edge-set encoding of trees directly represents trees as sets of their edges. Nonheuristic operators for edge-sets manipulate trees' edges without regard for their weights, while heuristic operators consider edges' weights when including or excluding them. In the latter case, the operators generally favor edges with lower weights, and they tend to generate trees that resemble minimum spanning trees. This bias is strong, which suggests that evolutionary algorithms (EAs) that employ heuristic operators will succeed when optimum solutions resemble minimum spanning trees (MSTs) but fail otherwise. The one-max tree problem is a scalable test problem for trees where the optimum solution can be…
A novel technique for stochastic root-finding: Enhancing the search with adaptive d-ary search
2017
The most fundamental problem encountered in the field of stochastic optimization, is the Stochastic Root Finding (SRF) problem where the task is to locate an unknown point x∗ for which g(x∗) = 0 for a given function g that can only be observed in the presence of noise [15]. The vast majority of the state-of-the-art solutions to the SRF problem involve the theory of stochastic approximation. The premise of the latter family of algorithms is to oper ate by means of so-called “small-step”processesthat explorethe search space in a conservative manner. Using this paradigm, the point investigated at any time instant is in the proximity of the point investigated at the previous time instant, render…
Context-Independent Scatter and Tabu Search for Permutation Problems
2005
In this paper, we develop a general-purpose heuristic for permutations problems. The procedure is based on the scatter-search and tabu-search methodologies and treats the objective-function evaluation as a black box, making the search algorithm context-independent. Therefore, our main contribution consists of the development and testing of a procedure that uses no knowledge from the problem context to search for the optimal solution. We perform computational experiments with four well-known permutation problems to study the efficiency and effectiveness of the proposed method. These experiments include a comparison with two commercially available software packages that are also based on met…
Incremental bipartite drawing problem
2001
Abstract Layout strategies that strive to preserve perspective from earlier drawings are called incremental. In this paper we study the incremental arc crossing minimization problem for bipartite graphs. We develop a greedy randomized adaptive search procedure (GRASP) for this problem. We have also developed a branch-and-bound algorithm in order to compute the relative gap to the optimal solution of the GRASP approach. Computational experiments are performed with 450 graph instances to first study the effect of changes in grasp search parameters and then to test the efficiency of the proposed procedure. Scope and purpose Many information systems require graphs to be drawn so that these syst…
Heuristics for the bandwidth colouring problem
2010
The bandwidth colouring problem consists of assigning a colour to each vertex of a graph, so that the absolute value of the difference between the colours of adjacent vertices is at least the value of the weight of the associated edge. This problem generalises the classical vertex colouring problem and different heuristics have recently been proposed to obtain high quality solutions. In this paper we describe both memory-based and memory-less methods to solve the bandwidth colouring problem. In particular we propose new constructive and improvement methods based on tabu search and GRASP. Comparison of our results with previously reported instances and existing heuristics indicate that the m…