Planning the workday of bus drivers by a graph list-coloring model

Abstract

In this work, we address the problem of planning the workday of bus drivers in argentinian intercity bus transport companies. In particular, we focus on a company which needs to fulfill roughly 800 trips per day between 3 cities of the Province of Buenos Aires with a stuff of around 200 drivers and 100 buses. Planning consists of assigning one driver to each trip in a way the driver performs all the trips without scheduling conflicts and minimizing the overall amount of overtime among all bus drivers. We model the problem as a particular Graph Coloring Problem and we propose an Integer Linear Programming formulation. Computations experiments show that this formulation outperforms other ones given in the literature for the same problem. In order to address large instances as the one given by the company, we also propose a heuristic algorithm that delivers better solutions than the company actually uses in a reasonably amount of time. The heuristic has two phases where the first one constructs an initial solution and the second one improves the solution iteratively.