Optimal driver scheduling with evolutionary approach in urban public transport

The optimal vehicle (VSP) and crew (CSP) scheduling problems solving in urban public transportation involves assigning timetabled trips to daily vehicle tasks, called blocks, and next to daily driver tasks, called duties. The aim is to minimize the number of vehicles and drivers. This maximizes usage of the both assets, makes the schedules more convenient for vehicle operations and drivers, and as a result mitigates possible delays, and fits into the legal requirements for the drivers' working time. The scheduling can be done either sequentially or simultaneously. In the former, vehicles are scheduled first, then drivers based on an already constructed vehicle blocks. Whereas in the latter, vehicles and drivers are scheduled at the same time, thus integrated (VCSP). As for the solution methods for the VCSP the Evolutionary Algorithms (EA) play a crucial role in addressing this complex challenge. Moreover, recent publications point out that metaheuristics, in particular the EA, are widely and successfully used in both the sequential and simultaneous solution approaches. The integrated scheduling of vehicles and rivers requires much longer computational time, which often cannot be accepted in practice for the VSP and CSP are usually solved separately by different institutions, i.e., the public transport authority (PTA) and the public transport operator (PTO), respectively. Alternatively, in the sequential approach, that is less computationally demanding, the influence of a solution of the VSP on a solution of the CSP can also be included. To solve sequentially the CSP taking into account an already solved the VSP and its characteristics (e.g., multiple depots, electric vehicles (EVs)), a specific and original EA is proposed in this paper. The algorithm divides vehicle blocks into pieces of work to be assigned to drivers’ duties. The pieces of work can be composed of the entire vehicle blocks as well as their parts, for the algorithm can divide them according to a set of proposed rules. The algorithm was tested on a real-world databases of public transport systems of the three large Polish cities. The results were compared with those obtained manually by a team of experienced transport planners. The crew schedules obtained using the algorithm were comparable or even better than those prepared manually and reached within significantly shorter time.