Chair: Filipe Alvelos, Universidade do Minho, Portugal
Bus Driver Rostering by Column Generation Metaheuristics
Vítor Barbosa (firstname.lastname@example.org), Filipe Alvelos (email@example.com), Ana Respício (firstname.lastname@example.org)
In the Bus Driver Rostering Problem (BDRP) it is intended to define work schedules for workers such that costs are minimized. This problem has been addressed before by combining column generation and an evolutionary algorithm. In this paper, we show how this approach can be improved by including additional random constraints and limiting the time spent in column generation. Both approaches follow a general framework entitled SearchCol, Metaheuristic search by column generation, recently proposed for decomposable integer programming/ combinatorial optimization problems.
Keywords: Rostering, Column Generation, Evolutionary algorithm
A matheuristic based on column generation for parallel machine scheduling with sequence dependent setup times
Filipe Alvelos (email@example.com), Manuel Lopes (firstname.lastname@example.org), Henrique Lopes (email@example.com)
In this paper we propose a heuristic approach based on column generation (CG) and a general purpose integer programming (GPIP) solver to address a scheduling problem. The problem consists in scheduling independent jobs with given processing times on unrelated parallel machines with sequence-dependent setup times. The objective is to minimize the total weighted tardiness. The proposed matheuristic (MH) takes advantage of the efficiency of CG to define a (restricted) search space which is explored by a GPIP solver. In different iterations, different additional constraints are introduced in CG, allowing the definition of several (restricted) search spaces to be explored by the GPIP solver. Computational results show that the proposed MH can be used to tackle very large instances (e.g. 100 machines and 400 jobs) obtaining better solutions in less time than a state-of-the-art branch-and-price algorithm from the literature.
Keywords: Parallel machine scheduling, Column generation, Matheuristic
SearchCol++: A C++ framework for column generation based algorithms
Filipe Alvelos (firstname.lastname@example.org)
Many integer programming/combinatorial optimization (IP/CO) problems can be addressed by decomposition approaches based on column generation (CG). Examples are routing, packing and cutting, scheduling, and personnel rostering problems. CG solves linear relaxation(s) of an IP/CO decomposition model by, iteratively, optimizing a restricted master problem and subproblems. A restricted master problem is a linear programming model corresponding to the linear relaxation of the decomposition model which does not consider all the variables. The subproblems can be tackled by any appropriate optimization algorithm (e.g. problem specific or branch-and-cut). In this presentation, we describe a C++ computational framework that allows the implementation of CG based algorithms with a minimum effort by a user. In particular SearchCol++ allows the implementation of (i) SearchCol (Metaheuristic search by column generation (Alvelos, Sousa, and Santos, 2013)) algorithms and (ii) branch-and-price (BP) and variants (as beam BP or BP with the application of metaheuristics or a general purpose mixed integer programming solver in the nodes of the tree). In both cases and in a bare implementation, a user only has to code three functions: (i) for calculating the coefficient in the objective function of each subproblem variable (given the dual variables of the global constraints), (ii) for solving the subproblem, and (iii) for defining the column in the restricted master problem associated with a given subproblem solution. All the other components of SearchCol and BP algorithms as branching constraints, metaheuristics, and perturbations are implemented in a problem independent way and do not require any programming by the user – they are controlled through parameters. Currently implemented (meta)heuristics include local search, VNS, tabu search, and simulated annealing.
Keywords: Column generation, SearchCol, Metaheuristics