Territory-Based Vehicle Routing in the Presence of Time-Window Constraints

M. Schneider, A. Stenger, F Schwahn, D. Vigo

Research output: Contribution to JournalArticleAcademicpeer-review


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.
Original languageEnglish
Pages (from-to)732-751
JournalTransportation Science
Issue number4
Early online date17 Oct 2014
Publication statusPublished - 2015


Dive into the research topics of 'Territory-Based Vehicle Routing in the Presence of Time-Window Constraints'. Together they form a unique fingerprint.

Cite this