Simultaneous vehicle and driver scheduling: a case study in a limousine rental company

In this paper, we address a driver–vehicle scheduling problem in a limousine rental company. Given a set of trips to be covered, the goal consists in finding a driver–vehicle schedule that serves the maximum workload and optimizes several economic objectives while satisfying a set of imperative constraints. In this context, we propose a simultaneous scheduling of drivers and vehicles. The problem is modeled using the notion of partial consistent assignment. The solution approach is composed of two phases: the first one is based on constraint programming techniques and leads to the construction of an initial solution, improved in a second phase by a Simulated Annealing algorithm. Significant gains on the resulting solutions are systematically obtained in terms of quality, operational costs and elaboration time, compared to the current practice in the company.