The conference is now over!

Soon, there will be some photos available...

CIO Springer TAP Compal BES FCT
SB4 Heuristics

Chair: Mariona Vilà, Universitat Politècnica de Catalunya, Spain
Room 3.1.10


Constructive Matheuristic for the Rectilinear Packing Problem

Marisa Oliveira (, A. Miguel Gomes (, Eduarda Pinto Ferreira (
In this work we intend to solve rectilinear packing (RP) problems using mathematical models combined with heuristic approaches. In the RP problems the pieces to place have rectilinear shapes (pieces with 90 or 270 interior angles) and the objective is to minimize the area of the enclosing rectangle which contains, without overlap, all the pieces. To tackle this problem we propose a hybrid approach that builds solutions iteratively. Each subset of pieces to place is obtained by heuristic rules that are based on the size of the pieces. In each iteration, the relative positions between pairs of pieces previously placed are fixed, while the new pieces have free relative positions.

Keywords: Rectilinear Packing Problem, Heuristic, Cutting and packing


A heuristic for the time-dependent Vehicle Routing Problem with Time Windows

Christophe Duhamel (, Vincent Huart (, Sylvain Perron (, Gilles Caporossi (
We consider the Time-Dependent Vehicle Routing Problem (TDVRPTW), a generalization of the Vehicle Routing Problem with Time Windows (VRPTW) where the travel time between any pair of clients can vary over the time. Its purpose is to better handle the dynamic nature of the travel time, especially in urban areas where traffic congestion can have a significant impact on the transportation. We propose a heuristic based on column generation and on Variable Neighborhood Descent (VND) for solving the TDVRPTW. Several neighborhoods are used to identify improving columns each iteration of the column generation process. Those columns are then stored in a shared pool. In the same time, the integer master problem is solved and its solution is then improved by the VND. Both total distance and number of vehicle criteria are considered. Numerical results are then presented to show the interest of our approach.

Keywords: Time dependent VRP, Column generation, Heuristic


A hybrid genetic algorithm for the one-dimensional minimax bin-packing problem with bin size constraints

Mariona Vilà (, Jordi Pereira (
In this paper, the one-dimensional minimax bin-packing problem with bin size constraints is studied. Among other applications, this problem is used in test-splitting, which consists in assigning several sets of questions into different questionnaires so that every one of these questionnaires contains one question from each one of the original sets. Questions have a weight associated, which typically corresponds to a measure of their difficulty, and the objective is to split the questions among the questionnaires in such a way that the weights are distributed as evenly as possible. We propose a hybrid genetic algorithm for solving this problem, which is then tested on a benchmark set of practically-sized instances. The results show its efficiency in solving large size instances from the literature.

Keywords: Bin-packing, Test-splitting, Combinatorial Optimisation