Territory-based vehicle routing in the presence of time-window constraints

Territory-based routing approaches (TBRAs) are commonly used to achieve high service consistency, e.g., in the small package shipping industry, but their drawback is a decline in routing flexibility. Consequently, a high percentage of time-definite deliveries, as common in the small package shipping sector, should have a significant negative effect on the solution quality of TBRAs. To the best of our knowledge, no study exists on the magnitude of this effect and the factors that influence it. Therefore, we develop a two-phase TBRA and use it (i) to investigate the design requirements of a TBRA for successfully handling time windows, and (ii) to study the influence of time window constraints on the performance of such an approach. We find that the consideration of geographical aspects in the districting is paramount for generating high-quality territories, whereas explicitly incorporating time window characteristics and historical demand data does not lead to a perceptible improvement of the solution quality. Moreover, the efficiency and feasibility forfeits of our TBRA in comparison to daily route reoptimization (RR) are larger if time windows are present. However, significantly higher consistency improvements compared to RR are achieved for time-constrained problems. This is due to the fact that RR solutions to time-definite problems exhibit lower consistency and thus a higher potential for improvement by using a TBRA, which constitutes an important insight for practitioners.