Metaheuristics for the Order Batching Problem in Manual Order Picking Systems

In manual order picking systems, order pickers walk or drive through a distribution warehouse in order to collect items which are requested by (internal or external) customers. In order to perform these operations efficiently, it is usually required that customer orders are combined into (more substantial) picking orders of limited size. The Order Batching Problem considered in this paper deals with the question of how a given set of customer orders should be combined such that the total length of all tours is minimized which are necessary to collect all items. The authors introduce two metaheuristic approaches for the solution of this problem: the first one is based on Iterated Local Search; the second on Ant Colony Optimization. In a series of extensive numerical experiments, the newly developed approaches are benchmarked against classic solution methods. It is demonstrated that the proposed methods are not only superior to existing methods but provide solutions which may allow distribution warehouses to be operated significantly more efficiently.

Hybrid Variable Neighborhood HyperHeuristics for Exam Timetabling Problems

This paper presents our work on analysing the high level search within a graph based hyperheuristic. The graph based hyperheuristic solves the problem at a higher level by searching through permutations of graph heuristics rather than the actual solutions. The heuristic permutations are then used to construct the solutions. Variable Neighborhood Search, Steepest Descent, Iterated Local Search and Tabu Search are compared. An analysis of their performance within the high level search space of heuristics is also carried out. Experimental results on benchmark exam timetabling problems demonstrate the simplicity and efficiency of this hyperheuristic approach. They also indicate that the choice of the high level search methodology is not crucial and the high level search should explore the heuristic search space as widely as possible within a limited searching time. This simple and general graph based hyperheuristic may be applied to a range of timetabling and optimisation problems.

Hybrid Variable Neighborhood HyperHeuristics for Exam Timetabling Problems

This paper presents our work on analysing the high level search within a graph based hyperheuristic. The graph based hyperheuristic solves the problem at a higher level by searching through permutations of graph heuristics rather than the actual solutions. The heuristic permutations are then used to construct the solutions. Variable Neighborhood Search, Steepest Descent, Iterated Local Search and Tabu Search are compared. An analysis of their performance within the high level search space of heuristics is also carried out. Experimental results on benchmark exam timetabling problems demonstrate the simplicity and efficiency of this hyperheuristic approach. They also indicate that the choice of the high level search methodology is not crucial and the high level search should explore the heuristic search space as widely as possible within a limited searching time. This simple and general graph based hyperheuristic may be applied to a range of timetabling and optimisation problems.

Airport ground movement

Worldwide air traffic tends to increase and for many airports it is no longer an op-tion to expand terminals and runways, so airports are trying to maximize their op-erational efficiency. Many airports already operate near their maximal capacity. Peak hours imply operational bottlenecks and cause chained delays across flights impacting passengers, airlines and airports. Therefore there is a need for the opti-mization of the ground movements at the airports. The ground movement prob-lem consists of routing the departing planes from the gate to the runway for take-off, and the arriving planes from the runway to the gate, and to schedule their movements. The main goal is to minimize the time spent by the planes during their ground movements while respecting all the rules established by the Ad-vanced Surface Movement, Guidance and Control Systems of the International Civil Aviation. Each aircraft event (arrival or departing authorization) generates a new environment and therefore a new instance of the Ground Movement Prob-lem. The optimization approach proposed is based on an Iterated Local Search and provides a fast heuristic solution for each real-time event generated instance granting all safety regulations. Preliminary computational results are reported for real data comparing the heuristic solutions with the solutions obtained using a mixed-integer programming approach.

Boosting the performance of metaheuristics for the MinLA problem using a more discriminating evaluation function

International audience

Formulations and Metaheuristics for combinatorial optimization problems

Combinatorial optimization problems have been strongly addressed throughout history. Their study involves highly applied problems that must be solved in reasonable times. This doctoral Thesis addresses three Operations Research problems: the first deals with the Traveling Salesman Problem with Pickups and Delivery with Handling cost, which was approached with two metaheuristics based on Iterated Local Search; the results show that the proposed methods are faster and obtain good results respect to the metaheuristics from the literature. The second problem corresponds to the Quadratic Multiple Knapsack Problem, and polynomial formulations and relaxations are presented for new instances of the problem; in addition, a metaheuristic and a matheuristic are proposed that are competitive with state of the art algorithms. Finally, an Open-Pit Mining problem is approached. This problem is solved with a parallel genetic algorithm that allows excavations using truncated cones. Each of these problems was computationally tested with difficult instances from the literature, obtaining good quality results in reasonable computational times, and making significant contributions to the state of the art techniques of Operations Research.

Vehicle routing and location routing problems with minimum latency: algorithms and models

Latency can be defined as the sum of the arrival times at the customers. Minimum latency problems are specially relevant in applications related to humanitarian logistics. This thesis presents algorithms for solving a family of vehicle routing problems with minimum latency. First the latency location routing problem (LLRP) is considered. It consists of determining the subset of depots to be opened, and the routes that a set of homogeneous capacitated vehicles must perform in order to visit a set of customers such that the sum of the demands of the customers assigned to each vehicle does not exceed the capacity of the vehicle. For solving this problem three metaheuristic algorithms combining simulated annealing and variable neighborhood descent, and an iterated local search (ILS) algorithm, are proposed. Furthermore, the multi-depot cumulative capacitated vehicle routing problem (MDCCVRP) and the multi-depot k-traveling repairman problem (MDk-TRP) are solved with the proposed ILS algorithm. The MDCCVRP is a special case of the LLRP in which all the depots can be opened, and the MDk-TRP is a special case of the MDCCVRP in which the capacity constraints are relaxed. Finally, a LLRP with stochastic travel times is studied. A two-stage stochastic programming model and a variable neighborhood search algorithm are proposed for solving the problem. Furthermore a sampling method is developed for tackling instances with an infinite number of scenarios. Extensive computational experiments show that the proposed methods are effective for solving the problems under study.

An iterated sample construction with path relinking method: Application to switch allocation in electrical distribution networks

We present a metaheuristic approach which combines constructive heuristics and local searches based on sampling with path relinking. Its effectiveness is demonstrated by an application to the problem of allocating switches in electrical distribution networks to improve their reliability. Our approach also treats the service restoration problem, which has to be solved as a subproblem, to evaluate the reliability benefit of a given switch allocation proposal. Comparisons with other metaheuristics and with a branch-and-bound procedure evaluate its performance. © 2012 Published by Elsevier Ltd.

Nonmonotone hybrid tabu search for inequalities and equalities: an experimental study

The main goal of this paper is to analyze the behavior of nonmono- tone hybrid tabu search approaches when solving systems of nonlinear inequalities and equalities through the global optimization of an appro- priate merit function. The algorithm combines global and local searches and uses a nonmonotone reduction of the merit function to choose the local search. Relaxing the condition aims to call the local search more often and reduces the overall computational e ort. Two variants of a perturbed pattern search method are implemented as local search. An experimental study involving a variety of problems available in the lit- erature is presented.

Heurísticas de pesquisa local para problemas de máquina única

O escalonamento é uma das decisões mais importantes no funcionamento de uma linha de produção. No âmbito desta dissertação foi realizada uma descrição do problema do escalonamento, identificando alguns métodos para a optimização dos problemas de escalonamento. Foi realizado um estudo ao caso do problema de máquina única através do teste de várias instâncias com o objectivo de minimizar o atraso pesado, aplicando uma Meta-Heurística baseada na Pesquisa Local e dois algoritmos baseados no SB. Os resultados obtidos reflectem que os algoritmos baseados no SB apresentaram resultados mais próximos do óptimo, em relação ao algoritmo baseado na PL. Os resultados obtidos permitem sustentar a hipótese de não existirem algoritmos específicos para os problemas de escalonamento. A melhor forma de encontrar uma solução de boa qualidade em tempo útil é experimentar diferentes algoritmos e comparar o desempenho das soluções obtidas.

When is the second local multiplier algebra of a C*-algebra equal to the first?

We discuss necessary as well as sufficient conditions for the second iterated local multiplier algebra of a separable C*-algebra to agree with the first.

Local optima networks of hard combinatorial landscapes

Combinatorial optimization involves finding an optimal solution in a finite set of options; many everyday life problems are of this kind. However, the number of options grows exponentially with the size of the problem, such that an exhaustive search for the best solution is practically infeasible beyond a certain problem size. When efficient algorithms are not available, a practical approach to obtain an approximate solution to the problem at hand, is to start with an educated guess and gradually refine it until we have a good-enough solution. Roughly speaking, this is how local search heuristics work. These stochastic algorithms navigate the problem search space by iteratively turning the current solution into new candidate solutions, guiding the search towards better solutions. The search performance, therefore, depends on structural aspects of the search space, which in turn depend on the move operator being used to modify solutions. A common way to characterize the search space of a problem is through the study of its fitness landscape, a mathematical object comprising the space of all possible solutions, their value with respect to the optimization objective, and a relationship of neighborhood defined by the move operator. The landscape metaphor is used to explain the search dynamics as a sort of potential function. The concept is indeed similar to that of potential energy surfaces in physical chemistry. Borrowing ideas from that field, we propose to extend to combinatorial landscapes the notion of the inherent network formed by energy minima in energy landscapes. In our case, energy minima are the local optima of the combinatorial problem, and we explore several definitions for the network edges. At first, we perform an exhaustive sampling of local optima basins of attraction, and define weighted transitions between basins by accounting for all the possible ways of crossing the basins frontier via one random move. Then, we reduce the computational burden by only counting the chances of escaping a given basin via random kick moves that start at the local optimum. Finally, we approximate network edges from the search trajectory of simple search heuristics, mining the frequency and inter-arrival time with which the heuristic visits local optima. Through these methodologies, we build a weighted directed graph that provides a synthetic view of the whole landscape, and that we can characterize using the tools of complex networks science. We argue that the network characterization can advance our understanding of the structural and dynamical properties of hard combinatorial landscapes. We apply our approach to prototypical problems such as the Quadratic Assignment Problem, the NK model of rugged landscapes, and the Permutation Flow-shop Scheduling Problem. We show that some network metrics can differentiate problem classes, correlate with problem non-linearity, and predict problem hardness as measured from the performances of trajectory-based local search heuristics.

Search schemes for random optimization algorithms that preserve the asymptotic distribution

Markovian algorithms for estimating the global maximum or minimum of real valued functions defined on some domain Omega subset of R-d are presented. Conditions on the search schemes that preserve the asymptotic distribution are derived. Global and local search schemes satisfying these conditions are analysed and shown to yield sharper confidence intervals when compared to the i.i.d. case.

Solving the Task Assignment Problem with a Variable Neighborhood Search

In this paper a variable neighborhood search (VNS) approach for the task assignment problem (TAP) is considered. An appropriate neighborhood scheme along with a shaking operator and local search procedure are constructed specifically for this problem. The computational results are presented for the instances from the literature, and compared to optimal solutions obtained by the CPLEX solver and heuristic solutions generated by the genetic algorithm. It can be seen that the proposed VNS approach reaches all optimal solutions in a quite short amount of computational time.

A Variable Neighborhood Search Approach for Solving the Maximum Set Splitting Problem

This paper presents a Variable neighbourhood search (VNS) approach for solving the Maximum Set Splitting Problem (MSSP). The algorithm forms a system of neighborhoods based on changing the component for an increasing number of elements. An efficient local search procedure swaps the components of pairs of elements and yields a relatively short running time. Numerical experiments are performed on the instances known in the literature: minimum hitting set and Steiner triple systems. Computational results show that the proposed VNS achieves all optimal or best known solutions in short times. The experiments indicate that the VNS compares favorably with other methods previously used for solving the MSSP. ACM Computing Classification System (1998): I.2.8.