Portal de Periódicos da CAPES

A structural lagrangean relaxation for two-duty period bus driver scheduling problems

1989; Elsevier BV; Volume: 39; Issue: 2 Linguagem: Inglês

10.1016/0377-2217(89)90194-x

1872-6860

José M. P. Paixão, Margarida Vaz Pato,

Vehicle Dynamics and Control Systems

The two-duty period bus driver scheduling problem is a particular case of the generalized set covering problem, min }cTx: Ax ⩾ b, 0 ⩽ x ⩽ hand integer{ where, each colum 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 new lagrangean relaxation approach which, combined with greedy heuristics, yield a reasonably good and fast procedure for tackling real life problems.