Utilize este identificador para referenciar este registo:
https://hdl.handle.net/1822/53269
Título: | A column generation based heuristic for a bus driver rostering problem |
Autor(es): | Barbosa, Vítor Respício, Ana Alvelos, Filipe Pereira e |
Palavras-chave: | Rostering Column generation Heuristic |
Data: | 1-Jan-2015 |
Editora: | Springer Verlag |
Revista: | Lecture Notes in Artificial Intelligence (subseries of Lecture Notes in Computer Science) |
Resumo(s): | The Bus Driver Rostering Problem (BDRP) aims at determining optimal work-schedules for the drivers of a bus company, covering all work duties, respecting the Labor Law and the regulation, while minimizing company costs. A new decomposition model for the BDRP was recently proposed and the problem was addressed by a metaheuristic combining column generation and an evolutionary algorithm. This paper proposes a new heuristic, which is integrated in the column generation, allowing for the generation of complete or partial rosters at each iteration, instead of generating single individual work-schedules. The new heuristic uses the dual solution of the restricted master problem to guide the order by which duties are assigned to drivers. The knowledge about the problem was used to propose a variation procedure which changes the order by which a new driver is selected for the assignment of a new duty. Sequential and random selection methods are proposed. The inclusion of the rotation process results in the generation of rosters with better distribution of work among drivers and also affects the column generation performance. Computational tests assess the proposed heuristic ability to generate good quality rosters and the impact of the distinct variation procedures is discussed. |
Tipo: | Artigo em ata de conferência |
URI: | https://hdl.handle.net/1822/53269 |
ISBN: | 9783319234847 |
DOI: | 10.1007/978-3-319-23485-4_16 |
ISSN: | 0302-9743 |
Arbitragem científica: | yes |
Acesso: | Acesso restrito UMinho |
Aparece nas coleções: |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
A Column Generation Based Heuristic for a Bus Driver Rostering Problem.pdf Acesso restrito! | 746,7 kB | Adobe PDF | Ver/Abrir |