Tabu Search-Based Algorithm for Large Scale Crew Scheduling Problems
Fuente:
Redalyc
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Artículo científico |
| Lenguaje: | en |
| Publicado: |
Universidad Nacional Autónoma de México
2005
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1876424200429764608 |
|---|---|
| author | Marco Caserta |
| author_facet | Marco Caserta |
| contents | Tabu Search-Based Algorithm for Large Scale Crew Scheduling Problems Marco Caserta Administración y Contabilidad primal todual tabu search set covering metaheuristic In this paper, the problem of finding a work schedule for airline crew members in a giventime horizon is tackled. This problem is known in the literature as Airline Crew Scheduling.The objective is to define the minimum cost schedules where each crew, associated to acombination of commercial flights or legs called pairing, is assigned to one or moreflights ensuring that the whole set of flights is covered by crew members. The CrewScheduling Problem can be modeled by using the Set Covering formulation. This paperpresents a new algorithm whose centerpiece is a primal-to-dual scheme aimed at linkingany primal solution to the dual feasible vector that best reflects the quality of the primalsolution. This new mechanism is used to intertwine a tabu search based, primal intensive,scheme with a lagrangian based, dual intensive, scheme to design a primal-dual algorithmthat progressively reduces the gap between upper and lower bound.The algorithm has been tested on benchmark problems from the literature. In this paper,results on real-world airline instances are presented: out of six well-known problems, thealgorithm is able to match the optimal solution for four of them while for the last two,whose optimal solution is not known, a new best known solution is found. 2005 artículo científico 0186-1042 https://www.redalyc.org/articulo.oa?id=39521504 en http://www.redalyc.org/revista.oa?id=395 Contaduría y Administración application/pdf Universidad Nacional Autónoma de México Contaduría y Administración (México) Num.215 |
| format | Artículo científico |
| id | redalyc_39521504 |
| institution | Redalyc |
| language | en |
| publishDate | 2005 |
| publisher | Universidad Nacional Autónoma de México |
| spellingShingle | Tabu Search-Based Algorithm for Large Scale Crew Scheduling Problems Marco Caserta Administración y Contabilidad primal todual tabu search set covering metaheuristic Tabu Search-Based Algorithm for Large Scale Crew Scheduling Problems Marco Caserta Administración y Contabilidad primal todual tabu search set covering metaheuristic In this paper, the problem of finding a work schedule for airline crew members in a giventime horizon is tackled. This problem is known in the literature as Airline Crew Scheduling.The objective is to define the minimum cost schedules where each crew, associated to acombination of commercial flights or legs called pairing, is assigned to one or moreflights ensuring that the whole set of flights is covered by crew members. The CrewScheduling Problem can be modeled by using the Set Covering formulation. This paperpresents a new algorithm whose centerpiece is a primal-to-dual scheme aimed at linkingany primal solution to the dual feasible vector that best reflects the quality of the primalsolution. This new mechanism is used to intertwine a tabu search based, primal intensive,scheme with a lagrangian based, dual intensive, scheme to design a primal-dual algorithmthat progressively reduces the gap between upper and lower bound.The algorithm has been tested on benchmark problems from the literature. In this paper,results on real-world airline instances are presented: out of six well-known problems, thealgorithm is able to match the optimal solution for four of them while for the last two,whose optimal solution is not known, a new best known solution is found. 2005 artículo científico 0186-1042 https://www.redalyc.org/articulo.oa?id=39521504 en http://www.redalyc.org/revista.oa?id=395 Contaduría y Administración application/pdf Universidad Nacional Autónoma de México Contaduría y Administración (México) Num.215 |
| title | Tabu Search-Based Algorithm for Large Scale Crew Scheduling Problems |
| topic | Administración y Contabilidad primal todual tabu search set covering metaheuristic |
| url | https://www.redalyc.org/articulo.oa?id=39521504 |