Vehicle scheduling for rental-with-driver services

In this paper, we introduce a new vehicle scheduling problem (VSP) with driver consistency faced by rental-with-driver companies. A weekly time-horizon is considered and a set of potential customers, each one associated with a list of required tasks, is assumed. The company can choose to accept or reject a customer, but if accepted, all required tasks must be performed by the same driver. A profit is associated with each customer. The goal is to maximize the company's total profit, by respecting a list of daily and the weekly drivers’ workload limitations imposed by drivers’ contracts. We propose a mathematical formulation of the problem and design an exact solution method based on the combinatorial Benders cuts approach. A computational study based on several sets of instances reveals that the proposed solution method strongly outperforms the straightforward MIP approach. A deep analysis of the impact of different parameters is presented. Finally, we provide a measure of the cost of consistency, expressed as the loss of profit necessary to guarantee driver consistency. Results indicate that, for instance, if task durations are long, consistency can be achieved for almost no cost. However, if task durations are short, the loss of profit is below 6%. This provides an important managerial insight for companies offering luxury services, where the perceived quality of a service is key to its success.