A multi-period vehicle routing problem with driver consistency and arrival-time diversification

We study a Multi-Period Vehicle Routing Problem that integrates driver consistency and arrival-time diversification. Driver consistency requires each customer to be served by the same vehicle across all service periods, while arrival-time diversification enforces temporal separation between visits in different periods. We first propose a Mixed-Integer Linear Programming formulation and an exact Logic-Based Benders Decomposition implemented through a Branch-and-Check scheme, where a multi-period VRP with driver consistency is handled in the master problem and arrival-time diversification is addressed in the subproblem. Building on this structure, we develop a matheuristic that exploits the subproblem in an efficient and targeted manner. As arrival-time diversification checks are computationally expensive, we propose a feasibility check procedure over a restricted search space. Computational results show that the branch-and-check approach solves medium-scale instances to optimality, while the matheuristic achieves near-optimal solutions in significantly shorter computation times. Lastly, the impact of arrival-time diversification is examined and managerial insights are derived.