Paper Info
Title
Combined bus and driver scheduling
Abstract
The daily bus and driver scheduling, for all bus companies that operate a non-fixed daily schedule of legs, is a difficult combinatorial problem that must be solved every afternoon. The work of the next day is changing on a daily basis either due to different load requirements on the standard routes or due to additional services and trips that the busses need to perform and the bus companies do wait until late afternoon before solving the scheduling problem. In addition, there exist hard customer requirements on the time required for the solution of the problem. This paper firstly presents a quick heuristic scheduling procedure named QS for the solution of the problem. QS has worked very well in the production environment of several bus companies of Greece. The main algorithms used by QS are minimum cost matching, set partitioning and shortest path. In addition, a column generation procedure named CGQS that uses an LP-solver and the QS process as its integer solution finder is presented. CGQS starts from the solution point of a single QS run and then performs several iterations in which LP problems are solved and new promising shifts are created using the LP dual solution.
Year
DOI
Venue
2002
10.1016/S0305-0548(00)00067-8
Computers & OR
Keywords
Field
DocType
driver scheduling,bus company,QS process,Crew scheduling,solution point,LP problem,difficult combinatorial problem,single QS run,scheduling problem,integer solution finder,LP dual solution,Combinatorial optimization,Crew assignment,daily bus,Combined bus,Column generation
Column generation,Mathematical optimization,Scheduling (computing),Crew scheduling,Combinatorial optimization,Mathematics
Journal
Volume
Issue
ISSN
29
3
Computers and Operations Research
Citations 
PageRank 
References 
7
0.84
2
Authors
2
Name
Order
Citations
PageRank
Christos Valouxis1855.88
Efthymios Housos221914.71