Search results for "heuristics"
showing 10 items of 191 documents
Greedy randomized adaptive search procedure with exterior path relinking for differential dispersion minimization
2015
We propose several new hybrid heuristics for the differential dispersion problem, the best of which consists of a GRASP with sampled greedy construction with variable neighborhood search for local improvement. The heuristic maintains an elite set of high-quality solutions throughout the search. After a fixed number of GRASP iterations, exterior path relinking is applied between all pairs of elite set solutions and the best solution found is returned. Exterior path relinking, or path separation, a variant of the more common interior path relinking, is first applied in this paper. In interior path relinking, paths in the neighborhood solution space connecting good solutions are explored betwe…
An ILS-Based Metaheuristic for the Stacker Crane Problem
2012
[EN] In this paper we propose a metaheuristic algorithm for the Stacker Crane Problem. This is an NP-hard arc routing problem whose name derives from the practical problem of operating a crane. Here we present a formulation and a lower bound for this problem and propose a metaheuristic algorithm based on the combination of a Multi-start and an Iterated Local Search procedures. Computational results on a large set of instances are presented.
Due Dates and RCPSP
2006
Due dates are an essential feature of real projects, but little effort has been made in studying the RCPSP with due dates in the activities. This paper tries to bridge this gap by studying two problems: the TardinessRCPSP, in which the objective is total tardiness minimization and the DeadlineRCPSP, in which the due dates are strict (deadlines) and the objective is makespan minimization. The first problem is NP-hard and the second is much harder, since finding a feasible solution is already NP-hard. This paper has three objectives: Firstly to compare the performance on both problems of well-known RCPSP heuristics - priority rules, sampling procedures and metaheuristics - with new versions w…
A Multiple Surrogate Assisted Decomposition-Based Evolutionary Algorithm for Expensive Multi/Many-Objective Optimization
2019
Many-objective optimization problems (MaOPs) contain four or more conflicting objectives to be optimized. A number of efficient decomposition-based evolutionary algorithms have been developed in the recent years to solve them. However, computationally expensive MaOPs have been scarcely investigated. Typically, surrogate-assisted methods have been used in the literature to tackle computationally expensive problems, but such studies have largely focused on problems with 1–3 objectives. In this paper, we present an approach called hybrid surrogate-assisted many-objective evolutionary algorithm to solve computationally expensive MaOPs. The key features of the approach include: 1) the use of mul…
A comparison of different solution approaches to the vehicle scheduling problem in a practical case
2000
Abstract The Vehicle Scheduling Problem (VSP) consists in assigning a set of scheduled trips to a set of vehicles, satisfying a set of constraints and optimizing an objective function. A wide literature exists for the VSP, but usually not all the practical requirements of the real cases are taken into account. In the present paper a practical case is studied, and for it a traditional method is tailored and two innovative heuristics are developed. As the problem presents a multicriteria nature, each of the three algorithms adopts a different approach to multicriteria optimization. Scalarization of the different criteria is performed by the traditional algorithm. A lexicographic approach is f…
Using a TSP heuristic for routing order pickers in warehouses
2010
In this paper, we deal with the sequencing and routing problem of order pickers in conventional multi-parallel-aisle warehouse systems. For this NP-hard Steiner travelling salesman problem (TSP), exact algorithms only exist for warehouses with at most three cross aisles, while for other warehouse types literature provides a selection of dedicated construction heuristics. We evaluate to what extent reformulating and solving the problem as a classical TSP leads to performance improvements compared to existing dedicated heuristics. We report average savings in route distance of up to 47% when using the LKH (Lin-Kernighan-Helsgaun) TSP heuristic. Additionally, we examine if combining problem-sp…
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…
The Rural Postman Problem on mixed graphs with turn penalties
2002
In this paper we deal with a problem which generalizes the Rural Postman Problem defined on a mixed graph (MRPP). The generalization consists of associating a non-negative penalty to every turn as well as considering the existence of forbidden turns. This new problem fits real-world situations more closely than other simpler problems. A solution tour must traverse all the requiring service arcs and edges of the graph while not making forbidden turns. Its total cost will be the sum of the costs of the traversed arcs and edges together with the penalties associated with the turns done. The Mixed Rural Postman Problem with Turn Penalties (MRPPTP) consists of finding such a tour with a total mi…
Selecting Genetic Operators to Maximise Preference Satisfaction in a Workforce Scheduling and Routing Problem
2017
The Workforce Scheduling and Routing Problem (WSRP) is a combinatorial optimisation problem that involves scheduling and routing of workforce. Tackling this type of problem often requires handling a considerable number of requirements, including customers and workers preferences while minimising both operational costs and travelling distance. This study seeks to determine effective combinations of genetic operators combined with heuristics that help to find good solutions for this constrained combinatorial optimisation problem. In particular, it aims to identify the best set of operators that help to maximise customers and workers preferences satisfaction. This paper advances the understand…
A GRASP ALGORITHM FOR THE CONTAINER LOADING PROBLEM WITH MULTI-DROP CONSTRAINTS
2015
This paper studies a variant of the container loading problem in which to the classical geometric constraints of packing problems we add other conditions appearing in practical problems, the multi-drop constraints. When adding multi-drop constraints, we demand that the relevant boxes must be available, without rearranging others, when each drop-off point is reached. We present first a review of the different types of multi-drop constraints that appear in literature. Then we propose a GRASP algorithm that solves the different types of multi-drop constraints and also includes other types of realistic constraints such as full support of the boxes and load bearing strength. The computational re…