Navegando por Autor "Wauters, Tony"
Agora exibindo 1 - 7 de 7
Resultados por página
Opções de Ordenação
Item Analysis of a constructive matheuristic for the traveling umpire problem.(2019) Toffolo, Túlio Ângelo Machado; Wauters, TonyThe Traveling Umpire Problem (TUP) is a combinatorial optimization problem concerning the assignment of umpires to the games of a fixed double roundrobin tournament. The TUP draws inspiration from the real world multi-objective Major League Baseball (MLB) umpire scheduling problem, but is, however, restricted to the single objective of minimizing total travel distance of the umpires. Several hard constraints are employed to enforce fairness when assigning umpires, making it a challenging optimization problem. The present work concerns a constructive matheuristic approach which focuses primarily on large benchmark instances. A decompositionbased approach is employed which sequentially solves Integer Programming (IP) formulations of the subproblems to arrive at a feasible solution for the entire problem. This constructive matheuristic efficiently generates feasible solutions and improves the best known solutions of large benchmark instances of 26, 28, 30 and 32 teams well within the benchmark time limit. In addition, the algorithm is capable of producing feasible solutions for various small and medium benchmark instances competitive with those produced by other heuristic algorithms. The paper also details experiments conducted to evaluate various algorithmic design parameters such as subproblem size, overlap and objective functions.Item Branch-and-bound with decomposition- based lower bounds for the Traveling Umpire Problem.(2016) Toffolo, Túlio Ângelo Machado; Wauters, Tony; Malderen, Sam Van; Berghe, Greet VandenThe Traveling Umpire Problem (TUP) is an optimization problem in which umpires have to be assigned to games in a double round robin tournament. The objective is to obtain a solution with minimum total travel distance over all umpires, while respecting hard constraints on assignments and sequences. Up till now, no general nor dedicated algorithm was able to solve all instances with 12 and 14 teams. We present a novel branch-and-bound approach to the TUP, in which a decomposition scheme coupled with an efficient propagation technique produces the lower bounds. The algorithm is able to generate optimal solutions for all the 12- and 14-team instances as well as for 11 of the 16-team instances. In addition to the new optimal solutions, some new best solutions are presented and other instances have been proven infeasible.Item Exact methods for three-dimensional cutting and packing : a comparative study concerning single container problems.(2019) Silva, Everton Fernandes da; Toffolo, Túlio Ângelo Machado; Wauters, TonyThree-dimensional Cutting and Packing Problems consist of a set of items that must be placed inside one or more larger items (containers). Such problems enforce non-overlapping constraints which ensure that the smaller items being assigned must completely fit inside their respective container. Despite extensive preexisting literature, there is the distinct absence of a study comparing exact methods for threedimensional Cutting and Packing Problems. Therefore, the primary ambition of the present research is to provide a comparative study of the most significant exact methods which have been designed for two variants of this problem class: the Single Large Object Placement Problem and the Single Knapsack Problem. By adapting the selected methods in accordance with the problems being analyzed, a detailed comparison is possible via experimentation using classic benchmarks datasets and newly-generated instances using a Cutting and Packing Generator from the literature. Over 15,000 h of experiments provide information concerning which methods perform best for the considered problems in addition to the scaling behavior and influence of the percentage of the larger item occupancy for each of the tested methods. These results provide further insight concerning performance improvements of existing exact methods and the development of new formulations.Item Heuristics for vehicle routing problems : sequence or set optimization?(2019) Toffolo, Túlio Ângelo Machado; Vidal, Thibaut Victor Gaston; Wauters, TonyWe investigate a structural decomposition for the capacitated vehicle routing problem (CVRP) based on vehicle-to-customer “assignment” and visits “sequencing” decision variables. We show that an heuristic search focused on assignment decisions with a systematic optimal choice of sequences (using Concorde TSP solver) during each move evaluation is promising but requires a prohibitive computational effort. We therefore introduce an intermediate search space, based on the dynamic programming procedure of Balas & Simonetti, which finds a good compromise between intensification and computational efficiency. A variety of speed-up techniques are proposed for a fast exploration: neighborhood reductions, dynamic move filters, memory structures, and concatenation techniques. Finally, a tunneling strategy is designed to reshape the search space as the algorithm progresses. The combination of these techniques within a classical local search, as well as in the unified hybrid genetic search (UHGS) leads to significant improvements of solution accuracy. New best solutions are found for surprisingly small instances with as few as 256 customers. These solutions had not been attained up to now with classic neighborhoods. Overall, this research permits to better evaluate the respective impact of sequence and assignment optimization, proposes new ways of combining the optimization of these two decision sets, and opens promising research perspectives for the CVRP and its variants.Item Multi-machine energy-aware scheduling.(2017) Dooren, David Van Den; Sys, Thomas; Toffolo, Túlio Ângelo Machado; Wauters, TonyThe traditional set of manufacturing scheduling problems concern general and easy-to-measure economic objectives such as makespan and tardiness. The variable nature of energy costs over the course of the day remains mostly ignored by most previous research. This variability should not be considered an added complexity, but rather an opportunity for businesses to minimise their energy bill. More effectively scheduling jobs across multiple machines may result in reduced costs despite fixed consumption levels. To this end, this paper proposes a scheduling approach capable of optimising this largely undefined and, consequently, currently unaddressed situation. The proposed multi-machine energy optimisation approach consists of constructive heuristics responsible for generating an initial solution and a late acceptance hill climbing algorithm responsible for improving this initial solution. The combined approach was applied to the scheduling instances of the ICON challenge on Forecasting and Scheduling [The challenge is organized as part of the EU FET-Open: Inductive Constraint Programming (ICON) project (O’Sullivan et al., ICON challenge on forecasting and scheduling. UCC, University College Cork, ICON, Cork. http://iconchallenge.insight-centre.org/challenge-energy, 2014)] whereupon it was proven superior to all other competing algorithms. This achievement highlights the potential of the proposed algorithm insofar as solving the multi-machine energy-aware optimisation problem (MEOP). The new benchmarks are available for further research.Item Stochastic local search with learning automaton for the swap-body vehicle routing problem.(2018) Toffolo, Túlio Ângelo Machado; Christiaens, Jan; Malderen, Sam Van; Wauters, Tony; Berghe, Greet VandenThis work presents the stochastic local search method for the Swap-Body Vehicle Routing Problem (SB-VRP) that won the First VeRoLog Solver Challenge. The SB-VRP, proposed on the occasion of the challenge, is a generalization of the classical Vehicle Routing Problem (VRP) in which customers are served by vehicles whose sizes may be enlarged via the addition of a swap body (trailer). The inclusion of a swap body doubles vehicle capacity while also increasing its operational cost. However, not all customers may be served by vehicles consisting of two bodies. Therefore swap locations are present where one of the bodies may be temporarily parked, enabling double body vehicles to serve customers requiring a single body. Both total travel time and distance incur costs that should be minimized, while the number of customers visited by a single vehicle is limited both by its capacity and by a maximum travel time. State of the art VRP approaches do not accommodate SB-VRP generalizations well. Thus, dedicated approaches taking advantage of the swap body characteristic are desired. The present paper proposes a stochastic local search algorithm with both general and dedicated heuristic components, a subproblem optimization scheme and a learning automaton. The algorithm improves the best known solution for the majority of the instances proposed during the challenge. Results are also presented for a new set of instances with the aim of stimulating further research concerning the SB-VRP.Item A two-dimensional heuristic decomposition approach to a three-dimensional multiple container loading problem.(2017) Toffolo, Túlio Ângelo Machado; Esprit, Eline; Wauters, Tony; Berghe, Greet VandenEfficient container loading has the potential to considerably reduce logistics and transportation costs. The container loading problem is computationally complex and, despite extensive academic effort, there remains room for algorithm improvement. Real-world problems are not always addressed satisfactorily primarily due to the large number of complex constraints and objectives. The problem addressed by this work is an unsolved multiple container loading problem introduced by Renault on the occasion of the 2014/2015 ESICUP challenge, organized by the EURO Special Interest Group on Cutting and Packing (ESICUP). Renault’s problem requires a large number of different items to be packed into containers of different types and sizes. Items must be grouped into stacks and respect the ‘this side up’ constraint. The primary objective is to minimize the volume of shipped containers. The smallest volume container may be left behind for the next shipment and is excluded from the main objective. Nevertheless, only a limited percentage of each product may be packed into this container. Additionally, a set of secondary objectives is considered. This work presents a decomposition approach embedded in a multi-phase heuristic for the problem. Feasible solutions are generated quickly, and subsequently improved by local search and post-processing procedures. Experiments revealed that the approach generates optimal solutions for two instances, in addition to good quality solutions for those remaining from the Renault set. The algorithmic contribution is, however, not restricted to the Renault instances. Experiments on less constrained container loading instances from the literature demonstrate the approach’s general applicability and competitiveness.