A HEURISTIC-PROCEDURE FOR THE CREW ROSTERING PROBLEM

被引:38
作者
BIANCO, L
BIELLI, M
MINGOZZI, A
RICCIARDELLI, S
SPADONI, M
机构
[1] UNIV PESCARA, IST STAT, PESCARA, ITALY
[2] UNIV LAQUILA, DIPARTIMENTO MATEMAT, I-67100 LAQUILA, ITALY
[3] UNIV URBINO, IST SCI ECON, I-61029 URBINO, ITALY
关键词
SCHEDULING; MASS TRANSIT; HEURISTIC; COMBINATORIAL OPTIMIZATION; ROSTERING;
D O I
10.1016/0377-2217(92)90213-S
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
This paper deals with the problem of planning work schedules in a given time horizon so as to evenly distribute the workload among the drivers in a mass transit system. An integer programming formulation of this problem is given. An iterative heuristic algorithm is described which makes use of a lower bound derived from the mathematical formulation. Furthermore, the algorithm at each iteration solves a multilevel bottleneck assignment problem for which a new procedure that gives asymptotically optimal solutions is proposed. Computational results for both the rostering problem and the multilevel bottleneck assignment problem are given.
引用
收藏
页码:272 / 283
页数:12
相关论文
共 17 条
[1]   SCHEDULING A FULL-TIME WORKFORCE TO MEET CYCLIC STAFFING REQUIREMENTS [J].
BAKER, KR .
MANAGEMENT SCIENCE SERIES B-APPLICATION, 1974, 20 (12) :1561-1568
[2]   WORKFORCE ALLOCATION IN CYCLICAL SCHEDULING PROBLEMS - SURVEY [J].
BAKER, KR .
OPERATIONAL RESEARCH QUARTERLY, 1976, 27 (01) :155-167
[3]   WORKFORCE SCHEDULING WITH CYCLIC DEMANDS AND DAY-OFF CONSTRAINTS [J].
BAKER, KR ;
MAGAZINE, MJ .
MANAGEMENT SCIENCE, 1977, 24 (02) :161-167
[4]   CYCLIC SCHEDULING VIA INTEGER PROGRAMS WITH CIRCULAR ONES [J].
BARTHOLDI, JJ ;
ORLIN, JB ;
RATLIFF, HD .
OPERATIONS RESEARCH, 1980, 28 (05) :1074-1085
[5]   A GUARANTEED-ACCURACY ROUND-OFF ALGORITHM FOR CYCLIC SCHEDULING AND SET COVERING [J].
BARTHOLDI, JJ .
OPERATIONS RESEARCH, 1981, 29 (03) :501-510
[6]  
BENNETT BT, 1968, TRANSPORT SCI, V2, P14
[7]  
BODIN L, 1983, COMPUT OPER RES, V10, P63, DOI 10.1016/0305-0548(83)90030-8
[8]  
BODIN L, 1983, COMPUTER OPERATIONS, V10, P144
[9]   NETWORK MODELS FOR VEHICLE AND CREW SCHEDULING [J].
CARRARESI, P ;
GALLO, G .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1984, 16 (02) :139-151
[10]   A MULTI-LEVEL BOTTLENECK ASSIGNMENT APPROACH TO THE BUS DRIVERS ROSTERING PROBLEM [J].
CARRARESI, P ;
GALLO, G .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1984, 16 (02) :163-173