Loading...
2 results
Search Results
Now showing 1 - 2 of 2
- The crew timetabling problem: an extension of the crew scheduling problemPublication . Gomes, Marta Castilho; Cavique, Luís; Themido, IsabelIn some urban transportation companies driving periods are short when compared with the total duty time, leading to long non-driving periods that can be used as cover time. This paper presents the Crew Timetabling Problem, an extension of the Crew Scheduling Problem in which crew timetables are obtained by levelling the cover crew resources. An objective function for this problem is proposed in order to balance the number of driving and cover crews. A Lisbon Underground case study is used to illustrate The Crew Timetabling Problem. The problem is represented in a multigraph and solved by a tabu search-based heuristic.
- A heuristic for the stability number of a graph based on convex quadratic programming and tabu searchPublication . Cavique, Luís; Luz, Carlos J.Recently, a characterization of the Lov´asz theta number based on convex quadratic programming was established. As a consequence of this formulation, we introduce a new upper bound on the stability number of a graph that slightly improves the theta number. Like this number, the new bound can be characterized as the minimum of a function whose values are the optimum values of convex quadratic programs. This paper is oriented mainly to the following question: how can the new bound be used to approximate the maximum stable set for large graphs? With this in mind we present a two-phase heuristic for the stability problem that begins by computing suboptimal solutions using the new bound definition. In the second phase a multi-start tabu search heuristic is implemented. The results of applying this heuristic to some DIMACS benchmark graphs are reported.