Repository logo

IPS - ESCE – DSI

Permanent URI for this community

http://hdl.handle.net/10400.26/3716

Browse

Browsing IPS - ESCE – DSI by Subject "Column generation"

Now showing 1 - 2 of 2
  • A hybrid metaheuristic for the Bus Driver Rostering Problem
    Publication . Barbosa, Vítor; Respício, A.; Alvelos, F.
    This paper presents a new decomposition model for the Bus Driver Rostering Problem and proposes the hybridization of column generation and genetic algorithms to achieve good quality rosters in short time. The decomposition model is based on the definition of a subproblem for each driver, which is responsible for the creation of valid work-schedules for the rostering period. Column generation is used to obtain an optimal linear solution. This solution and the subproblems' solutions obtained during the column generation are then used by the genetic algorithm to find good quality combinations of drivers' schedules, i.e. good quality rosters. Computational tests show the efficiency and effectiveness of the proposed approach.
    2013-02Conference object Open access Show more
  • A repair operator for decomposable problems’ global solutions
    Publication . Barbosa, Vítor; Respicio, Ana; Alvelos, Filipe
    This paper proposes a new repair operator to be used inside algorithms based on the concept of Search by Column Generation (SearchCol). This concept has revealed to be suitable to address problems represented by models that decompose the problem into several subproblems and in which a global solution can be obtained by combining solutions of the subproblems. SearchCol starts by solving the linear relaxation of the integer programming decomposition model using column generation. Metaheuristics are then used to search for the best global integer solution by combining subproblems’ solutions. The new repair operator intents to fix the invalid solutions but ends up has a generator of new subproblems’ solutions and allows to change the search space as the metaheuristic explores the search space. The success of the repair operator is verified in a SearchCol based evolutionary algorithm to solve a Bus Driver Rostering Problem.
    2016-09Conference object Open access Show more