| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 627.76 KB | Adobe PDF |
Authors
Advisor(s)
Abstract(s)
The two-duty period bus driver scheduling problem is a particular case of the generalized set covering problem, min {cTx : Ax ⩾ b, 0 ⩽ x ⩽h and integer) where, each column of the boolean matrix A consists of at most two strings of consecutive ones. Such a denomination for the problem is due to several real life applications, in particular for bus crew scheduling. In this paper, we present a 'structural' lagrangean relaxation and penalties for improving the bounds on the optimum for the problem. Two other lagrangean relaxation approaches, previously reported in the literature, are considered too. A computational study relative to these relaxations was carried out with both randomly generated test problems and real life cases from Rodoviária Nacional, a large mass transport operator in Portugal. The results reported in the paper evidence a better performance for the lagrangean relation approach wich combined with greedy heuristics, yeld a reasonably good and fast procedure for tackling real life problems
Description
Keywords
Lagrangean Relaxation Heuristics Generalized Set Covering Network Flows Bus Driver Scheduling
Pedagogical Context
Citation
Paixão, José Pinto and Margarida Vaz Pato .(1989). “A structural Lagrangean relaxation for two-duty period bus driver scheduling problems”, European Journal of Operational Research, Volume 39: pp. 213-222. 1989
Publisher
Elsevier