Por favor utiliza este link para citar o compartir este documento: http://repositoriodigital.academica.mx/jspui/handle/987654321/9802
Título: Tabu Search-Based Algorithm for Large Scale Crew Scheduling Problems
Autores: 
Palabras clave: SET COVERING; TABU SEARCH; METAHEURISTIC; LAGRANGIAN OPTIMIZATION; PRIMAL-TODUAL
SET COVERING; TABU SEARCH; METAHEURISTIC; LAGRANGIAN OPTIMIZATION; PRIMAL-TODUAL
Fecha de publicación: 10-Sep-2011
Editorial: Facultad de Contaduría y Administración
Descripción: IN THIS PAPER, THE PROBLEM OF FINDING A WORK SCHEDULE FOR AIRLINE CREW MEMBERS IN A GIVEN TIME 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 A COMBINATION OF COMMERCIAL FLIGHTS OR "LEGS" CALLED "PAIRING", IS ASSIGNED TO ONE OR MORE FLIGHTS ENSURING THAT THE WHOLE SET OF FLIGHTS IS COVERED BY CREW MEMBERS. THE CREW SCHEDULING PROBLEM CAN BE MODELED BY USING THE SET COVERING FORMULATION. THIS PAPER PRESENTS A NEW ALGORITHM WHOSE CENTERPIECE IS A PRIMAL-TO-DUAL SCHEME AIMED AT LINKING ANY PRIMAL SOLUTION TO THE DUAL FEASIBLE VECTOR THAT BEST REFLECTS THE QUALITY OF THE PRIMAL SOLUTION. 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 ALGORITHM THAT 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, THE ALGORITHM 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.
IN THIS PAPER, THE PROBLEM OF FINDING A WORK SCHEDULE FOR AIRLINE CREW MEMBERS IN A GIVEN TIME 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 A COMBINATION OF COMMERCIAL FLIGHTS OR "LEGS" CALLED "PAIRING", IS ASSIGNED TO ONE OR MORE FLIGHTS ENSURING THAT THE WHOLE SET OF FLIGHTS IS COVERED BY CREW MEMBERS. THE CREW SCHEDULING PROBLEM CAN BE MODELED BY USING THE SET COVERING FORMULATION. THIS PAPER PRESENTS A NEW ALGORITHM WHOSE CENTERPIECE IS A PRIMAL-TO-DUAL SCHEME AIMED AT LINKING ANY PRIMAL SOLUTION TO THE DUAL FEASIBLE VECTOR THAT BEST REFLECTS THE QUALITY OF THE PRIMAL SOLUTION. 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 ALGORITHM THAT 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, THE ALGORITHM 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.
Other Identifiers: http://revistas.unam.mx/index.php/rca/article/view/4624
Aparece en las Colecciones:Contaduría y Administración

Archivos de este documento:
No hay archivos asociados a este documento.


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.