Publicação
A structural Lagrangean relaxation for two-duty period bus driver scheduling problems
| dc.contributor.author | Pinto, José Pinto | |
| dc.contributor.author | Pato, Margarida Vaz | |
| dc.date.accessioned | 2025-01-23T15:14:00Z | |
| dc.date.available | 2025-01-23T15:14:00Z | |
| dc.date.issued | 1989 | |
| dc.description.abstract | 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 | pt_PT |
| dc.description.version | info:eu-repo/semantics/publishedVersion | pt_PT |
| dc.identifier.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 | pt_PT |
| dc.identifier.issn | 0377-2217 | |
| dc.identifier.uri | http://hdl.handle.net/10400.5/97586 | |
| dc.language.iso | eng | pt_PT |
| dc.publisher | Elsevier | pt_PT |
| dc.subject | Lagrangean Relaxation | pt_PT |
| dc.subject | Heuristics | pt_PT |
| dc.subject | Generalized Set Covering | pt_PT |
| dc.subject | Network Flows | pt_PT |
| dc.subject | Bus Driver Scheduling | pt_PT |
| dc.title | A structural Lagrangean relaxation for two-duty period bus driver scheduling problems | pt_PT |
| dc.type | journal article | |
| dspace.entity.type | Publication | |
| rcaap.rights | openAccess | pt_PT |
| rcaap.type | article | pt_PT |