Abstract This paper investigates the construction of routes over multiple days while maintaining driver consistency, which requires that the multi-day service of each customer be provided by as few different drivers as possible over a planning horizon. Furthermore, if one customer is assigned to different drivers over multiple days, it is desirable that services are provided by one driver on as many days as possible. To optimize this driver consistency, a new quantitative measure of driver consistency is defined. In the proposed vehicle routing problem with driver consistency, driver consistency is modeled in the objective function. Another contribution is that we model the vehicle routing problem with driver consistency considering uncertainties in customer demands, travel times, and service times. Uncertain programming models for the considered problem are developed utilizing uncertainty theory. A hybrid algorithm with large neighborhood search and simulated annealing is designed to address the proposed NP-hard problem. Computational experiments are conducted on several datasets to highlight the performance of the proposed approach and the models. The impacts of uncertainty and the trade-off between the total travel time and driver consistency are also analyzed to reveal some managerial insights. Our analysis shows that uncertainty has negative impacts on minimizing total travel time while can improve driver consistency in some cases; Remarkable reduction in the total travel time can be achieved with little damage on driver consistency; However, totally focusing on minimizing total travel time comes at the price of sacrificing driver consistency drastically.

Highlights • A new quantitative driver consistency measure is defined. • Uncertain demand, service and travel time are studied in the VRP with consistency. • A hybrid algorithm with simulated annealing and large neighborhood search is designed. • Analysis of trade-off between total travel time and driver consistency is discussed.